fork download
copy 
  1. #include <boost/heap/fibonacci_heap.hpp>
  2. #include <boost/heap/priority_queue.hpp>
  3. #include <boost/heap/binomial_heap.hpp>
  4. #include <boost/heap/d_ary_heap.hpp>
  5. #include <queue>
  6. #include <chrono>
  7. #include <iostream>
  8.  
  9. using namespace std;
  10. using namespace std::chrono;
  11.  
  12. const int NUM_ITER = 100000;
  13.  
  14. template<class T>
  15. void test(const char *name)
  16. {
  17. 	T pq;
  18.  
  19. 	auto ts = system_clock::now();
  20.     for(int i=0; i<NUM_ITER; i++){
  21.         pq.push(rand());
  22.     }
  23.     for(int i=0; i<NUM_ITER; i++){
  24.         pq.pop();
  25.     }
  26.     double ts1 = duration_cast<nanoseconds>(system_clock::now() - ts).count();
  27.     cout << name << " " << ts1/(double)NUM_ITER << " ns\n";
  28. }
  29.  
  30. template<class T>
  31. void test_mod(const char *name)
  32. {
  33. 	T pq;
  34.  
  35. 	std::vector<typename T::handle_type> handles;
  36. 	handles.reserve(NUM_ITER);
  37.  
  38. 	auto ts = system_clock::now();
  39.     for(int i=0; i<NUM_ITER; i++){
  40.         handles.push_back(pq.push(rand()));
  41.     }
  42.     for(int i=0; i<NUM_ITER; i++){
  43.     	pq.update(handles[i], rand());
  44.     }
  45.     for(int i=0; i<NUM_ITER; i++){
  46.         pq.pop();
  47.     }
  48.     double ts1 = duration_cast<nanoseconds>(system_clock::now() - ts).count();
  49.     cout << name << " " << ts1/(double)NUM_ITER << " ns\n";
  50. }
  51.  
  52.  
  53. int main(){
  54.     std::priority_queue<int> pq;
  55.     std::priority_queue<int, std::deque<int> > pqd;
  56.     boost::heap::priority_queue<int> bpq;
  57.     boost::heap::fibonacci_heap<int> bfh;
  58.     boost::heap::binomial_heap<int> bbh;
  59.  
  60.  
  61.     cout << "NUM_ITER:" << NUM_ITER << "\n";
  62.  
  63.     test<std::priority_queue<int>>("std::priority_queue<int>");
  64.     test<std::priority_queue<int, std::deque<int> >>("std::priority_queue<int, std::deque<int> >");
  65.     test<boost::heap::priority_queue<int>>("boost::heap::priority_queue<int>");
  66.     test<boost::heap::fibonacci_heap<int>>("boost::heap::fibonacci_heap<int>");
  67.     test<boost::heap::binomial_heap<int>>("boost::heap::binomial_heap<int>");
  68.     test<boost::heap::d_ary_heap<int, boost::heap::arity<8>>>("boost::heap::d_ary_heap<int, boost::heap::arity<8>>");
  69.  
  70.     cout << "\n with mutablity:" << std::endl;
  71.  
  72.     test_mod<boost::heap::fibonacci_heap<int>>("boost::heap::fibonacci_heap<int>");
  73.     test_mod<boost::heap::binomial_heap<int>>("boost::heap::binomial_heap<int>");
  74.     test_mod<boost::heap::d_ary_heap<int, boost::heap::arity<8>, boost::heap::mutable_<true>>>("boost::heap::d_ary_heap<int, boost::heap::arity<8>, boost::heap::mutable_<true>>");
  75. }
  76.  
Success #stdin #stdout 0.41s 12368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NUM_ITER:100000
std::priority_queue<int> 108.225 ns
std::priority_queue<int, std::deque<int> > 168.768 ns
boost::heap::priority_queue<int> 104.049 ns
boost::heap::fibonacci_heap<int> 470.975 ns
boost::heap::binomial_heap<int> 894.402 ns
boost::heap::d_ary_heap<int, boost::heap::arity<8>> 165.522 ns

 with mutablity:
boost::heap::fibonacci_heap<int> 539.535 ns
boost::heap::binomial_heap<int> 1048.48 ns
boost::heap::d_ary_heap<int, boost::heap::arity<8>, boost::heap::mutable_<true>> 353.256 ns
https://ideone.com/WewlkX
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!