2
$\begingroup$

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 duplicates
  • remove(a,b) a minus b
  • intersection(a,b)
  • ncov(a,n) a with n-1 copies of each present integer removed.
  • after(a,n) domain of everything in a equal to or greater than n
  • before(a,n) domain of everything in a equal to or smaller than n
  • minlen(a,l) domain of all ranges in a with a cardinality of at least l.
  • trunc_start(a,l) a with the l smallest integers removed from each range.
  • trunc_end(a,l) a with the l largest integers removed from each range.

Queries:

  • contains?(a,p) does the domain a contain a specified integer p?
  • covers?(a,b) is domain b a subset of domain a?
  • 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?
Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Maybe Interval trees do what you want? $\endgroup$
    – adrianN
    Aug 2, 2016 at 12:17
  • $\begingroup$ 0. Do you need a persistent immutable data structure? If so, which flavor of persistence are you looking for? 1. You say the data structure is just a multiset of integers, but then some of your operations are defined in terms of ranges. Is it possible to rephrase them in terms of the multiset instead of in terms of ranges? 2. Does "after" mean "greater than"? Does "lowest" mean "smallest"? Does "front-to-back" mean "starting with the lowest number and iterating over them in increasing order"? Can you rephrase? $\endgroup$
    – D.W. ♦
    Aug 2, 2016 at 19:17
  • 1
    $\begingroup$ You are contradicting yourself. In a multi-set of integer ranges, you can't join ranges. Do you mean a multi-set of integers, where usually not a single integer but a whole range of integers is added / removed / tested etc.? It looks like you are looking for just a multiset of integers, optimised for integers occurringg in ranges. $\endgroup$
    – gnasher729
    Aug 2, 2016 at 21:51
  • $\begingroup$ @gnasher729 yes, a multiset of integers where integers are usually inserted/removed a whole range at a time, i.e. a multiset of integers, optimized for integers occouring in ranges. $\endgroup$
    – Filip Haglund
    Aug 2, 2016 at 22:03
  • $\begingroup$ If that's what you meant, then you need to edit the question, because that's not what the question says. As gnasher729 says, you are contradicting yourself: you say one thing in the question, another thing in the comments, and the two conflict with each other. I suggest you try rephrasing all of your operations in terms of a multiset of integers. If you have a multiset of integers, things like "covered by n ranges" or "remove the first l units from each range" are not well-defined/meaningful. $\endgroup$
    – D.W. ♦
    Aug 3, 2016 at 20:25

2 Answers 2

Reset to default
2
$\begingroup$

I would suggest looking at interval trees and segment trees. A natural representation is that the data structure contains a union of non-overlapping ranges $[l,u]$ with a multiplicity $m$; the intended meaning is that each integer in the range $l,l+1,l+2,\dots,u$ occurs in the domain with multiplicity $m$ (i.e., appears $m$ times), and the invariant is that the multiplicity of all integers within a single range is the same.

We can't tell you whether a tree would be faster in your application; that's workload-dependent, so the only way to tell is to try it and benchmark it and see.

This can be made persistent using standard techniques (e.g., path copying), if that's useful (e.g., if you have many domains that are similar to each other).

Improve this answer
$\endgroup$
-1
$\begingroup$

The Google Guava library has a RangeSet data structure that might satisfy some of your requirements. You can check out its implementation to see if it is what you need.

https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/RangeSet.html

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Can you edit your answer to summarize the main algorithmic ideas that it implements? We don't want to be just a collection of links (and if the link stops working, this answer won't be very useful). $\endgroup$
    – D.W. ♦
    Aug 2, 2016 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.