PersistentArrays.jl
Fat node implementation of a persistent array, which in this case is just stored as an array of arrays. This datastructure is ideal when you need to store multiple versions of an array, but the elements in the array are rarely changing.
Usage:
Please see the test cases for common usage here.
Complexity:
Summary Table of method complexity per element selected.
Method | Complexity |
---|---|
setindex!(a, x, i...) |
O(m) |
getindex(a, i...) |
O(1) |
update!(a, x, v, i...) |
O(mlog(m)) |
lookup(a, v, i...) |
O(log(m)) |
The space complexity is O(n x m) where n is the number of elements and m is the number of versions. This worst case scenario could occur if all elements in the array change for every version.