最小堆与std :: priority_queue是我的瓶颈 [英] Min heap with std::priority_queue is my bottleneck
问题描述
替代标题:
用比 std :: priority_queue c>。
grpof给了我:
时间秒秒通话S /呼叫S /调用名称结果
84.12 105.54 105.54 320000 0.00 0.00 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i
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'的一部分混淆了我,因为它是在我的项目的类/文件中不再使用
which I believe is my only std::priority_queue
used in the project. The 'Division_Euclidean_space' part confuses me, since it's a class/file not used any more in my project.
下面是我使用完全相同:
Here is what I use exactly:
/**
* 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;
我使用第一个元素作为比较键。
I use the first element as the key for comparison.
和作为一个可以在我的回购看,我只创建一个 Min_heap
,我使用它分为两部分:
and as one can see in my repo, I create only one Min_heap
and I use it in two parts:
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();
...
}
我觉得如果我更换这个数据结构与其他东西,我的项目可能会运行一点更快(超级好极了)。任何想法?
I feel that if I replace this data structure with something else, my project may run a bit faster (super duper great). Any ideas?
我推动项目在堆中一段时间,然后我弹出一个,我可能会推动其他项目,等等。
I push items in the heap for a while, then I pop one and I will probably push other items do and so on. Most of the times I stop with another condition, not when the heap gets empty.
推荐答案
http://demangler.com 将该函数转换为:(缩进为我)
http://demangler.com translated that function into: (indented by me)
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)
< t知道 nn
是什么,但我想它比优先级队列操作更多。
I don't know what nn
does, but I suppose it does a lot more than priority queue operations.
这篇关于最小堆与std :: priority_queue是我的瓶颈的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!