C ++：使用更大的比较器可以提高性能

Question

我正在向网上分级系统提交我的算法问题解决方案，首先，解决方案超过了时间限制，大约需要4秒左右。

我完全确定复杂性是正确的，所以我开始优化我的部分代码并没有发生什么大事，直到我发现一些非常奇怪的东西。

我正在使用成对的优先级队列，我选择实现自己的比较器

struct Comparator{  
  bool operator()(pair<int, int> node1, pair<int, int> node2){  
      return node1.second < node2.second;  
  }  
}; 

当我把它改为greater库的<algorithm>比较器时，性能得到了显着提升;解决方案通过，它只需要约300毫秒。

额外信息：我使用优先级队列来实现Dijkstra的“调整”版本。队列声明是：priority_queue<pair<int, int>, vector<pair<int, int>>, Comparator> q;，我改为：priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;。

我真的很好奇为什么会这样。对我来说，比较器应该做的非常简单，我想不出更有效的方法。

任何帮助将不胜感激 ：）

Answer 1

有几件事可能导致性能差异：

struct Comparator{  
  bool operator()(pair<int, int> node1, pair<int, int> node2){  
      return node1.second < node2.second;  
  }  
}; 

与std::greater

1. 自定义比较器按值获取对象，std::greater通过引用获取它们。我怀疑这会产生超过10％的影响。
2. std::greater比较node2.first < node1.first，如果node2.first != node1.first，否则它是node2.second < node1.second。这种比较与Comparator完全不同，node1.second < node2.second比较了std::greater。 由于比较结果不同，您的代码会经历完全不同的路径。通过不同的路径可以对大O的复杂性和性能产生深远的影响。这很可能是导致差异的真正原因。

有关std::pair::operator<的参考，请查看lhs.first<rhs.first正在做的事情：

如果true，返回qazxsw poi。否则，如果qazxsw poi，返回qazxsw poi。否则，如果rhs.first<lhs.first，返回false。否则，返回lhs.second<rhs.second。