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

Question

替代标题:

实施分堆的东西更快的比std::priority_queue.

---

grpof给了我:

时间秒秒呼叫s /呼叫s /呼叫名称
84.12 105.54 105.54 320000 0.00 0.00 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKStvectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i

我相信这是我std::priority_queue在项目中唯一使用的.'Division_Euclidean_space'部分让我困惑,因为它是我的项目中不再使用的类/文件.

这是我使用的完全:

/**
 * 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;

我使用第一个元素作为比较的关键.

正如我在回购中看到的那样,我只创建了一个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,但我认为它比优先级队列操作做得更多.