使用std :: priority_queue推送最小堆是瓶颈 [英] Pushing in min heap with std::priority_queue is the bottleneck
问题描述
作为最小堆的速度比std::priority_queue快?
Something faster than std::priority_queue as a min heap?
原始问题是此处.您可以使用 demangler 来解析grpof生成的名称.在那里的用户的帮助下，我得出了一个结论，在这里，这段代码(我希望执行的次数比执行弹出操作的次数还要多):
The original question is here. You can resolve the names generated by grpof with the demangler. With the help of the users there, I came to a conclusion, where this block of code (that I expect to get executed much more times than I will perform a pop):
/**
* 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;
...
void nn(..) { // the core function of my project
if(...) {
branch.push(std::make_tuple(new_dist, other_child_i, tree_i));
}
}
似乎是我项目的瓶颈(我思考)，正如我在调用此代码后所看到的那样:
seems to be the bottleneck of my project (I think), as I can see after calling this:
gprof -q_ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i geraf gmon.out > analysis.txt
得到了:
granularity: each sample hit covers 2 byte(s) for 0.01% of 125.47 seconds
index % time self children called name
1967195 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i [2]
105.54 0.09 320000/320000 Auto_random_kd_forest<float>::Auto_random_kd_forest(unsigned int&, unsigned int&, std::string const&, unsigned int, std::string const&, int, float, std::vector<std::vector<std::pair<float, int>, std::allocator<std::pair<float, int> > >, std::allocator<std::vector<std::pair<float, int>, std::allocator<std::pair<float, int> > > > >&, Params*, int) (1)
[2] 84.2 105.54 0.09 320000+1967195 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i [2]
0.08 0.00 1967195/2031195 void std::__push_heap<__gnu_cxx::__normal_iterator<std::tuple<float, int, int>*, std::vector<std::tuple<float, int, int>, std::allocator<std::tuple<float, int, int> > > >, int, std::tuple<float, int, int>, std::greater<std::tuple<float, int, int> > >(__gnu_cxx::__normal_iterator<std::tuple<float, int, int>*, std::vector<std::tuple<float, int, int>, std::allocator<std::tuple<float, int, int> > > >, int, int, std::tuple<float, int, int>, std::greater<std::tuple<float, int, int> >) [9]
0.01 0.00 12000/12000 _ZNSt6vectorISt5tupleIJfiiEESaIS1_EE19_M_emplace_back_auxIJS1_EEEvDpOT_ [11]
1967195 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i [2]
-----------------------------------------------
0.00 0.00 64000/2031195 _ZSt13__adjust_heapIN9__gnu_cxx17__normal_iteratorIPSt5tupleIJfiiEESt6vectorIS3_SaIS3_EEEEiS3_St7greaterIS3_EEvT_T0_SC_T1_T2_ (10)
0.08 0.00 1967195/2031195 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i [2]
[9] 0.1 0.09 0.00 2031195 void std::__push_heap<__gnu_cxx::__normal_iterator<std::tuple<float, int, int>*, std::vector<std::tuple<float, int, int>, std::allocator<std::tuple<float, int, int> > > >, int, std::tuple<float, int, int>, std::greater<std::tuple<float, int, int> > >(__gnu_cxx::__normal_iterator<std::tuple<float, int, int>*, std::vector<std::tuple<float, int, int>, std::allocator<std::tuple<float, int, int> > > >, int, int, std::tuple<float, int, int>, std::greater<std::tuple<float, int, int> >) [9]
-----------------------------------------------
0.01 0.00 12000/12000 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i [2]
[11] 0.0 0.01 0.00 12000 _ZNSt6vectorISt5tupleIJfiiEESaIS1_EE19_M_emplace_back_auxIJS1_EEEvDpOT_ [11]
我要推送的项目比弹出的要多.在链接的问题中，我显示了与堆相关的代码.我们可以假设堆永远不会为空.我不确定分发情况.
I am pushing way more items than I pop. In the question I linked I show the code that is relative with my heap. We can assume that the heap never gets empty. I am not sure about the distribution.
推荐答案
在Wiki上查看堆比较:
See the heap comparison on the wiki:
http://en.wikipedia.org/wiki/Heap_(data_structure)
最快可获得的是斐波那契堆. AFAIK STL优先级队列只是一个二进制堆. 您可以使用 boost 斐波那契堆的实现. 这也是SO中的问题，其中显示了增强堆.
The fastest you can get is Fibonacci heap. AFAIK the STL priority queue is just a binary heap. You could improve on speed by using the boost implementation of the fibonacci heap. Also here is a question from SO showing the usage of the boost heap.
值得一提的是，维基百科中显示的数据是堆的理论比较. STL实现是二进制堆，因为对于小大小的堆，它通常比斐波那契堆快得多.总结斐波那契堆信息的一个很好的问题是此处.
The thing worth mentioning is that the data shown in the wikipedia is theoretical comparison of heaps. The STL implementation is the binary heap because it is usually much faster then fibonacci heap for heaps of small size. The nice question summarising the fibonacci heap information is here.
这篇关于使用std :: priority_queue推送最小堆是瓶颈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
