时间戳

首页 > 解决方案 > C++：使用更大的比较器实现意外的性能提升

c++ - C++：使用更大的比较器实现意外的性能提升

问题描述

我正在将算法问题的解决方案提交给在线评分系统，起初，解决方案超过了时间限制，大约需要 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;。

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

任何帮助将不胜感激 ：）

标签： c++operator-keyword

解决方案

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

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。

    由于比较结果不同，您的代码会经历完全不同的路径。经历不同的路径会对大 O 复杂性和性能产生深远的影响。这很可能是造成差异的真正原因。

有关std::greater查看std::pair::operator<正在执行的操作的参考：

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

推荐阅读