Optimization of Elixir/Erlang data structure, multiset stored as ranges.

Need a highly optimized implementation of a purely functional data structure written in either Elixir or Erlang. No ETS tables or similar. The data structure is a multiset of integers, optimized for integers occurring in runs of consecutive numbers. Apart from the usual union, set difference, subset checks, max, min etc., it needs to efficiently be able to return a new multiset of all integers x: a < x < b, and also return a new multiset with only integers that are part of a consecutive run longer than n. The ranges are bounded inside a small integer, with some margin, i.e. around (-2^59, 2^59).

The current implementation uses a linked-list to store the runs of integers as pairs (from,to). It will be provided as a reference implementation. There are unit tests, but they are not complete. I'd guess a tree-based structure and property based testing against the reference implementation is the way to go.

The most common access pattern is first, passing a list of ranges to a constructor. Then, do a lot of intersections, then remove a few non-overlapping ranges of integers at the lower end over and over again. On each remove, we need to return a copy (because we're using the same instance to create multiple new data structures). The linked-list implementation is really bad at reusing parts of the data structure on remove operations, I'd guess a tree would handle this much better. The data structure usually contains up to ~1000 continuous runs of integers, in the range (-2^50,2^50).

The resulting product will probably be open-sourced.

Erlang

Nº del proyecto: #11496684

Sobre el proyecto