package varray
Install
Dune Dependency
Authors
Maintainers
Sources
md5=1adc5c68c7b65f43ab6436400ea2647b
sha512=0899d2db1692c8800320991492744dd3d9a297c40d1842cf3fcd29aa4da66c713127c315886c4b1f915725f5e28953bcbbbc2534c234a25227eeae86f5ffc08c
Description
- O(1) constant time for random access
arr.(i)and updatesarr.(i) <- v - O(1) amortized for
push_frontandpop_front,push_backandpop_backto add or remove an element to the start or the end - O(sqrt N) for
insert_at arr i xanddelete_at arr ito insert or delete an element anywhere else
This datastructure was invented by Goodrich and Kloss and is described in their paper "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences".
Published: 24 Nov 2023
README
This library provides an implementation of variable sized arrays, which are also called resizable arrays, dynamic arrays or even "vectors" in C++ and "ArrayList" in Java. Just like an array, accessing any element by its index is constant time, but one can also efficiently insert and delete at any location (with the array resizing automatically to meet the need).
Following the above paper, the family of tiered vectors yields a nice compromise between random access and resizing:
Module Circular |
|
|
| Memory overhead |
|---|---|---|---|---|
Circular | O(1) | O(1) amortized | O(N) | O(N) |
Root(Circular) | O(1) | O(1) amortized | O(√N) | O(√N) |
Rootk-1(Circular) | O(k) | O(k) amortized | O(k2 × k√N) | O(Nk-1 / k) |
In other words, each instantiation of the Root functor leads to slower random access into the array, but it also makes insertion and deletion faster!
"You can expect the following constant factors on random access:
Array | Circular | Root | Root2 | Root3 | Root4 | Root5 | |
|---|---|---|---|---|---|---|---|
get | 1x | 3x | 8x | 17x | 27x | 31x | 33x |
set | 1x | 2x | 4x | 8x | 12x | 14x | 15x |
The memory usage is competitive:
push_front,push_backand their respectivepop, are amortized constant time, since they frequently need to allocate small chunks of O(k√N) up to O(k k√N) memory as the varray grows or shrinks.- The growth strategy is incremental: the worst case slowdown following a resize is also O(k k√N) which is unobtrusive for k>1. There is no "stop the world while every elements is moved to a larger array".
- The amount of memory used for bookkeeping and allocated in anticipation of a growth is pretty tight. In particular for k=2, the O(√N) memory overhead is optimal if random access and
push_backare to be O(1).
If you only care about fast random access and resizing at the right end with {push,pop}_back, then the pre-existing libraries provide smaller constant factors : (in alphabetical order) BatDynArray from Batteries, CCVector from Containers, RES as a standalone library or even vector as a single module.