元组的 C++ priority_queue 很慢

Question

我需要用 C++ 处理动态排序的事件列表。每个事件由 3 个变量组成：时间（用于对列表进行排序）和其他 2 个。我按事件处理数据事件，取出排序列表中的第一个（具有较低时间变量），对其进行处理，然后将其从列表中删除。在处理事件的过程中，我还必须将其他人添加到可以在任何位置添加的列表中。

我尝试使用由 tuple (std::priority_queue<tuple<double, int, int>, std::vector<tuple<double, int, int>>, greater<tuple<double, int, int>>>) 组成的 prioriy_queue，double 的值是用于对列表进行排序的时间变量，整数是其他有用的变量加工。这行得通，它保留了一个按时间排序的列表，我可以轻松添加新事件并删除第一个事件，我只需要访问第一个事件（时间值较低）。

但这需要很多时间。我的程序花费的大部分时间都用于向我的列表中添加和删除项目。除了优先队列还有其他选择吗？使用 tuple<double, int, int> 可能不是最好的方法，应该影响很大，还有其他选择吗？

Answer 1

std::priority_queue 的所有意图都是堆，lg2 N 推入和弹出。请注意，对于一百万项，这将是 20KM，K 小常量，M 内存访问。单核内存使用 8MB，因此是时候升级到 CPU，让 L3 至少可以访问那么多内存了。

这可以通过一些努力改进到 lg lg N（Thorup 等价物），但可能会有更简单的选择。

如果有很多时间冲突，则元组不是正确的结构。

类似

struct item {
  double time;
  int first, second;

  operator>(const item & other) const {
    return time > other.time;
  }
};

using pQueue = std::priority_queue<item, std::vector<item>, std::greater<item>>;

这应该使用 operator> 否则使用 lampda 作为比较器。

如果您将新项作为一个组插入，您可以考虑使用 Leonardo 堆来获得额外的编程乐趣。

另一种可能性是在前 128 个元素上使用 std::partial_sort，其余的不排序，插入新元素时检查排序数组中的最大值，看它是否需要包含在顶部在其他人中得分或仅 emplace_back。当最高分为空时，创建一个新的 std::partial_sort。在这种情况下，使用 std::deque 而不是 std::vector 可能更好，因为 O(1) 的 pop_front 更好。必须做一些额外的簿记工作。

元组的 C++ priority_queue 很慢

C++ priority_queue of tuple is slow

c++

priority-queue