Background
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 insert
and remove
, so it's time to see if there's something better out there. I'm spending around 1400 clock cycles per insert
or remove
, so there should be some margin for improvement.
Current implementation
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.
The 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 x
, a <= x < b
, distinct from every previously defined range, with b-a
as large as possible.
The operations
The operations supported right now are
insert(a,b)
union of two domains, keeping duplicatesremove(a,b)
a
minusb
intersection(a,b)
ncov(a,n)
a
withn-1
copies of each present integer removed.after(a,n)
domain of everything ina
equal to or greater thann
before(a,n)
domain of everything ina
equal to or smaller thann
minlen(a,l)
domain of all ranges ina
with a cardinality of at leastl
.trunc_start(a,l)
a
with thel
smallest integers removed from each range.trunc_end(a,l)
a
with thel
largest integers removed from each range.
Queries:
contains?(a,p)
does the domaina
contain a specified integerp
?covers?(a,b)
is domainb
a subset of domaina
?lowest(a)
what's the lowest integer in the domain?highest(a)
what's the highest integer in the domain?
Behaviour
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.
Questions
- 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?