Priority Queue Text push and pop Timing Test

Description

This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into a container using push , then removes them using pop . It measures the average time for push as a function of the number of values.

(The test was executed with priority_queue_text_push_pop_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; Figures NBRG, NBRM, and NBRL show the results for the native priority queues and pb_ds's pairing queues in g++, msvc++, and local, respectively.

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

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

  1. n_pq_vector- std::priority_queue adapting std::vector
  2. n_pq_deque- std::priority_queue adapting std::deque
  3. thin_heap- priority_queue with Tag = thin_heap_tag
  4. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  5. binomial_heap- priority_queue with Tag = binomial_heap_tag
  6. binary_heap- priority_queue with Tag = binary_heap_tag
  7. pairing_heap- priority_queue with Tag = pairing_heap_tag
no image
NPM: Native tree and pb ds priority queue push and pop 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. thin_heap- priority_queue with Tag = thin_heap_tag
  4. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  5. binomial_heap- priority_queue with Tag = binomial_heap_tag
  6. pairing_heap- priority_queue with Tag = pairing_heap_tag
  7. binary_heap- priority_queue with Tag = binary_heap_tag
no image
NPL: Native tree and pb ds priority queue push and pop timing test - local
no image
NBRG: Native tree and pb ds pairing priority queue push and pop timing test - g++

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

  1. n_pq_vector- std::priority_queue adapting std::vector
  2. n_pq_deque- std::priority_queue adapting std::deque
  3. pairing_heap- priority_queue with Tag = pairing_heap_tag
no image
NBRM: Native tree and pb ds pairing priority queue push and pop 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. pairing_heap- priority_queue with Tag = pairing_heap_tag
no image
NBRL: Native tree and pb ds pairing priority queue push and pop timing test - local

Observations

These results are very similar to Priority Queue Text push Timing Test. As stated there, pairing heaps (priority_queue with Tag = pairing_heap_tag) are most suited for push and pop sequences of non-primitive types such as strings. Observing these two tests, one can note that a pairing heap outperforms the others in terms of push operations, but equals binary heaps (priority_queue with Tag = binary_heap_tag) if the number of push and pop operations is equal. As the number of pop operations is at most equal to the number of push operations, pairing heaps are better in this case. See Priority Queue Random Integer push and pop Timing Test for a case which is different.

Priority-Queue Performance Tests::Observations discusses this further and summarizes.