std::priority_queue 的最小堆是我的瓶颈

Question

备选标题：

使用比 std::priority_queue.

更快的东西来实现最小堆

grpof 给了我：

time seconds seconds calls s/call s/call name
84.12 105.54 105.54 320000 0.00 0.00 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i

我相信这是我在项目中唯一使用的 std::priority_queue。 'Division_Euclidean_space' 部分让我感到困惑，因为它是 class/file 在我的项目中不再使用的部分。

以下是我使用的确切内容：

/**
 * Min_heap is actually a std::priority_queue,
 * with std::greater as a parameter.
 */
typedef std::priority_queue<std::tuple<float, int, int>,
    std::vector<std::tuple<float, int, int> >,
    std::greater<std::tuple<float, int, int> > > Min_heap;

我以第一个元素为key进行比较

正如大家在我的 repo 中看到的那样，我只创建了一个 Min_heap 并将其分两部分使用：

if(...) {
  branch.push(std::make_tuple(new_dist, other_child_i, tree_i));
}

和

while (branch.size()) {
  std::tie(new_mindist, node_i, tree_i) = branch.top();
  branch.pop();
  ...
}

我觉得如果我用其他东西替换这个数据结构，我的项目可能运行会快一点（超级棒）。有什么想法吗？

我将项目压入堆中一段时间，然后弹出一个，我可能会压入其他项目，依此类推。大多数时候我会在另一个条件下停止，而不是在堆变空时。

Answer 1

http://demangler.com 将该函数翻译成：（由我缩进）

RKD<Division_Euclidean_space<float> >::nn(
  unsigned int,
  std::vector<float, std::allocator<float> > const&,
  float const&,
  std::vector<std::pair<float, int>, std::allocator<std::pair<float, int> > >&,
  int&,
  int,
  unsigned int*,
  std::priority_queue<std::tuple<float, int, int>,
                      std::vector<std::tuple<float, int, int>,
                                  std::allocator<std::tuple<float, int, int> > >,
                      std::greater<std::tuple<float, int, int> > >&,
  float const&,
  unsigned int const&,
  std::vector<float, std::allocator<float> > const&,
  std::vector<float, std::allocator<float> > const&,
  int)

我不知道 nn 做了什么，但我想它做的不仅仅是优先级队列操作。

std::priority_queue 的最小堆是我的瓶颈

Min heap with std::priority_queue is my bottleneck

c++

performance

stl

gprof