AVL Array |
Get the latest
|
- Simple test
- NPSV example
The code listed in
simpletest.cpp
is 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 list
vector
deque
avl_array
Final element 10000
1
0
0
0
17825
15000
3
0
0
0
23360
22500
8
0
1
0
6148
33750
26
2
1
0
7020
50625
118
3
4
0
14041
75937
>120 1
6
9
1
31946
113905
NA
15
20
1
13288
170857
NA
39
48
1
32266
256285
NA
>120 2
>120 3
3
29099
384427
NA
NA
NA
4
2097
576640
NA
NA
NA
7
17736
864960
NA
NA
NA
12
16371
1297440
NA
NA
NA
19
23998
1946160
NA
NA
NA
30
10100
2919240
NA
NA
NA
50
19130
4378860
NA
NA
NA
84
20558
6568290
NA
NA
NA
>120 4
NA
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.cpp
is 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.