SourceForge.net Logo

AVL Array

Get the latest
version via bzr


Examples

Page contents

Simple test
NPSV example

Simple test

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 after 83% inserted
2: Aborted after 100% inserted, 54% removed
3: Aborted after 100% inserted, 55% removed
4: Aborted after 100% 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 seconds
INITIAL_SIZE: 10000 elements
Random seed: 1161729471

NPSV example

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 from int, 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.