Optimal Arrays

Overview

This Rust crate implements a resizable array as described in the paper Resizable Arrays in Optimal Time and Space by Andrej Brodnik et. al., published in 1999.

• Online ISBN 978-3-540-48447-9
• https://doi.org/10.1137/23M1575792

This data structure supports push and pop operations and does not support inserts or removes at other locations within the array. One exception is the swap/remove operation (similar to the DeleteRandom operation described in the paper) which will retrieve a value from a specified index, overwrite that slot with the value at the end of the array, decrement the count, and return the retrieved value.

This is part of a collection of similar data structures:

• Extensible Arrays
  • Similar O(√N) space overhead and similar O(1) running time for most operations
  • Slower than Optimal Arrays for repeated pushes but faster for ordered/random access
• Optimal Arrays (Tarjan and Zwick)
  • O(rN^1/r) space overhead and similar O(1) running time for most operations
  • Copying during grow/shrink adds significant time to overall performance
• Segment Array
  • Grows geometrically like Vec, hence O(N) space overhead
  • Faster than Optimal Arrays for repeated pushes and ordered/random access

Memory Usage

Compared to the Vec type in the Rust standard library, this data structure will have substantially less unused space, on the order of O(√N). The index block contributes to the overhead of this data structure, and that is on the order of O(√N). This data structure will grow and shrink as needed. That is, as push() is called, new data blocks will be allocated to contain the new elements. Meanwhile, pop() will deallocate data blocks as they become empty.

Examples

A simple example copied from the unit tests.

let inputs = [
    "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
];
let mut arr: OptimalArray<String> = OptimalArray::new();
for item in inputs {
    arr.push(item.to_owned());
}
for (idx, elem) in arr.iter().enumerate() {
    assert_eq!(inputs[idx], elem);
}

Supported Rust Versions

The Rust edition is set to 2024 and hence version 1.85.0 is the minimum supported version.

Troubleshooting

Memory Leaks

Finding memory leaks with Address Sanitizer is fairly easy and seems to work best on Linux. A Docker container with bash access and Rust nightly installed can be found in the containers directory.

cd containers
docker compose build --pull
docker compose run leaktest
sh leak.sh

If no problems were detected, a single line of output will appear. When done, clean up the docker artifacts.

exit
docker compose down

References

• [1]: Resizable Arrays in Optimal Time and Space (1999)