package varray

  1. Overview
  2. Docs
Resizable arrays with fast insertion/deletion

Install

Dune Dependency

Authors

Maintainers

Sources

varray-0.1.tbz
sha256=69a22c87d9eb4cd27ddd74b24d9fd6fe4e3ec28781012f6eb99203a9fb78e167
sha512=c5c2292a1eff693d8f10a7b398b1924b17ab3d7b84788f94e689460106df5f41f7bba3e0e30b51f9faaba88db7b502448f4850c344a4765bfd2e37da7fe7f460

Description

  • O(1) constant time for random access arr.(i) and updates arr.(i) <- v
  • O(1) amortized for push_front and pop_front, push_back and pop_back to add or remove an element to the start or the end
  • O(sqrt N) for insert_at arr i x and delete_at arr i to 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: 10 Apr 2022

README

README.md

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).

Online Documentation

Following the above paper, the family of tiered vectors yields a nice compromise between random access and resizing:

Module Circular get, set {push,pop}_{back,front} insert_at, pop_at 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_back and their respective pop, 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_back are 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.

Dependencies (2)

  1. ocaml >= "4.08"
  2. dune >= "2.8"

Dev Dependencies (2)

  1. odoc with-doc
  2. monolith with-test

Used by

None

Conflicts

None

OCaml

Innovation. Community. Security.