|
|
AVL Array |
Get the latest
|
- Simple test
- NPSV example
The code listed in
simpletest.cppis rough, simple test. It shows that AVL Arrays outperform vector and list under very particular conditions. AVL Arrays are the best choice in cases where both kinds of operations (random access and insert/erase at any point) are performed frequently in highly populated containers.The test consists in populating a container by inserting random numbers in random positions, and then removing elements from random positions until only one remains. The final element is shown as a proof that all containers execute the same operations. The next table shows some results:
Results (times in seconds) of
simpletest.cpp
Size listvectordequeavl_arrayFinal element 1000010001782515000300023360225008010614833750262107020506251183401404175937>120 169131946113905NA1520113288170857NA3948132266256285NA>120 2>120 3329099384427NANANA42097576640NANANA717736864960NANANA12163711297440NANANA19239981946160NANANA30101002919240NANANA50191304378860NANANA84205586568290NANANA>120 4NA
1: Aborted after83%inserted2: Aborted after100%inserted,54%removed3: Aborted after100%inserted,55%removed4: Aborted after100%inserted,35%removed
Results obtained with:
- Compiler: Dev-C++ 4.9.9.0 (Project configured for best optimizations and no debug)
- Processor: Pentium 4 Mobile running at 1.59 GHz
- RAM: 512 MB
MAX_TIME: 120 secondsINITIAL_SIZE: 10000 elements- Random seed: 1161729471
The code listed in
npsvexample.cppis an example of the experimental feature "Non-Proportional Sequence View" (NPSV). This feature exploits, in a more general form, the same principle that AVL Array uses for indexing the sequence with natural numbers.The difference is that in the normal sequence view every element counts as 1, while in the NPSV each element can count as a 'width' that can be changed. The position of every element is the sum of the widths of the previous elements in the sequence order. Negative widths are forbidden, but zero width is allowed.
When an element has zero width, the next one seems to be in the same position from the NPSV point of view. In these cases the lookup at this shared position always returns the first element of the 'same position' group.
The type of the width is a parameter of the avl_array template, providing a lot of possibilities: unsigned, double, or any class providing some overloaded operators
=,+,-,+=,-=,==,!=,>,<,<=,>=and a conversion fromint, which will be used for 0 and 1.The output of the program is shown in comments along the code.
Revised 19 May, 2010
Copyright © Universidad de Alcalá 2006. See accompanying license.