I'm currently writing some Elixir algorithms that are quite computationally expensive. The most-used datastructure is a multi-set of (finite) integer ranges. Modifying this data structure takes up around 80% of the execution time in
remove, so it's time to see if there's something better out there. I'm spending around 1400 clock cycles per
remove, so there should be some margin for improvement.
The current model, called
Domain, is a fully persistent immutable ordered linked-list of
[low, high) pairs, normalized so that for any time two ranges overlap, the first one is the longest. Touching ranges are also joined. Most domains consist of less than 100 ranges, but some consist of up to 10k ranges. The current data structure is chosen because it was easy to work with, avoiding premature optimization.
Domain datastructure represents a multiset of integers. Internally representing ranges as
[low, high) pairs is just an optimization. Since some domains cover many million of numbers, I don't think a multiset would be fast enough to be viable.
A range is a set of
b-a unique integers
a <= x < b, distinct from every previously defined range, with
b-a as large as possible.
The operations supported right now are
insert(a,b)union of two domains, keeping duplicates
n-1copies of each present integer removed.
after(a,n)domain of everything in
aequal to or greater than
before(a,n)domain of everything in
aequal to or smaller than
minlen(a,l)domain of all ranges in
awith a cardinality of at least
lsmallest integers removed from each range.
llargest integers removed from each range.
contains?(a,p)does the domain
acontain a specified integer
ba subset of domain
lowest(a)what's the lowest integer in the domain?
highest(a)what's the highest integer in the domain?
The most common use-case is to modify the structure a small bit at a time, from smallest value to biggest. Since inserts might modify the whole structure, the lists are almost always rebuilt completely right now. Changing the access pattern to bulk inserts and deletions is not feasible.
The second most common use-case is intersection between multiple (3+) domains, currently implemented as repeatedly calling the binary intersection function.
- Is there a standard name of this data structure?
- Is there a more efficient format? If so, which one(s)?
- Would a tree be faster than a linked-list? With or without rebalancing?