Priority Queue Text join Timing Test

Description

This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into two containers, then merges the containers. It uses join for pb_ds's priority queues; for the STL's priority queues, it successively pops values from one container and pushes them into the other. The test measures the average time as a function of the number of values.

(The test was executed with priority_queue_text_join_timing_test thirty_years_among_the_dead_preproc.txt 200 200 2100)

Purpose

The test checks the effect of different underlying data structures (see Design::Priority Queues::Implementations).

Results

Figures NPG, NPM, and NPL show the results for the native priority queues and pb_ds 's priority queues in g++, msvc, and local, respectively.

no image
NPG: Native tree and pb ds priority queue push timing test - g++

In the above figure, the names in the legends have the following meaning:

  1. n_pq_deque- std::priority_queue adapting std::deque
  2. n_pq_vector- std::priority_queue adapting std::vector
  3. binary_heap- priority_queue with Tag = binary_heap_tag
  4. thin_heap- priority_queue with Tag = thin_heap_tag
  5. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  6. pairing_heap- priority_queue with Tag = pairing_heap_tag
  7. binomial_heap- priority_queue with Tag = binomial_heap_tag
no image
NPM: Native tree and pb ds priority queue push timing test - msvc++

In the above figure, the names in the legends have the following meaning:

  1. n_pq_deque- std::priority_queue adapting std::deque
  2. n_pq_vector- std::priority_queue adapting std::vector
  3. binary_heap- priority_queue with Tag = binary_heap_tag
  4. thin_heap- priority_queue with Tag = thin_heap_tag
  5. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  6. pairing_heap- priority_queue with Tag = pairing_heap_tag
  7. binomial_heap- priority_queue with Tag = binomial_heap_tag
no image
NPL: Native tree and pb ds priority queue push timing test - local

Observations

In this test the node-based heaps perform join in either logarithmic or constant time. The binary heap requires linear time, since the well-known heapify algorithm [clrs2001] is linear.

It would be possible to apply the heapify algorithm to the STL containers, if they would support iteration (which they don't). Barring iterators, it is still somehow possible to perform linear-time merge on a std::vector-based STL priority queue, using top() and size() (since they are enough to expose the underlying array), but this is impossible for a std::deque-based STL priority queue. Without heapify, the cost is super-linear.