This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into a container using insert . It measures the average time for insert as a function of the number of values inserted.
(The test was executed with tree_text_insert_timing_test thirty_years_among_the_dead_preproc.txt 200 200 2100)
The test checks the effect of different underlying data structures.
Figures NNTG, NVTG, and NPTG show the results for the native tree and pb_ds's node-based trees, the native tree and pb_ds's vector-based trees, and the native tree andpb_ds's PATRICIA-trie, respectively, in g++; Figures NNTM, NVTM, and NPTM show the same in msvc++; Figures NNTL, NVTL, and NPTL show the same in local.
In the above figure, the names in the legends have the following meaning:
In the above figure, the names in the legends have the following meaning:
In the above figure, the names in the legends have the following meaning:
In the above figure, the names in the legends have the following meaning:
In the above figure, the names in the legends have the following meaning:
In the above figure, the names in the legends have the following meaning:
Observing Figure NNTG , for this setting, a splay tree, ( tree with Tag = splay_tree_tag ) does not do well. This was covered in Tree-Based and Trie-Based Text find Find Timing Test . The two red-black trees perform better.
Observing Figure NVTG, an ordered-vector tree ( tree with Tag = ov_tree_tag) performs abysmally. Inserting into this type of tree has linear complexity [ austern00noset].
Observing Figure NPTG , A PATRICIA trie ( trie with Tag = pat_trie_tag ) has abysmal performance, as well. This is not that surprising, since a large-fan-out PATRICIA trie works like a hash table with collisions resolved by a sub-trie. Each time a collision is encountered, a new "hash-table" is built A large fan-out PATRICIA trie, however, doe does well in look-ups (see Tree-Based and Trie-Based Text find Find Timing Test ). It is possibly beneficial to semi-static settings, therefore.
Observations::Tree-Like-Based Container Types summarizes some observations on tree-based and trie-based containers.