From: Caleb Clausen Date: 2010-04-05T03:21:51+09:00 Subject: Re: combined ranges... On 4/4/10, Robert Klemme wrote: > On 04/03/2010 03:07 AM, Caleb Clausen wrote: >> Oh, I wish for a real integer set class! > > Well, there's Fixnum / Bignum: Well, yeah, and that's fine for storing sets of small integers. Or I could put my Integers into a Set, and that's fine for small sets of integers. I have used both techniques in the past. What I have in mind is more scalable: a way to store large sets of large integers. Efficiently. So, what I would like to see is a data structure with O(1) (or at most O(log(n))) insertion, deletion, and lookup times, as well as (as close as possible to) O(1) memory cost per stored item. Contiguous ranges of integers should be storable with not much more memory cost than that of a single integer. Bitmaps come close, but also cost O(1) bits per integer (< the largest integer stored) which _isn't_ in the set. A hash-based set costs something like O(2*wordsize) bits per stored integer. Perhaps this can be reduced to O(2+wordsize) if using google's sparse array/sparse hash. (Which Roger has been kind enough to add a ruby interfaces for.... but not an integer set.) Of course there's a contradiction here; if: 1) the integer set is fairly dense, and 2) members are randomly distributed throughout it, then Kolmogorov complexity theory says you can't get any better storage efficiency than a bitmap. So, this miraculous data structure I'm imagining has to be allowed to discard one or the other of those assumptions. Discarding 1) leads to something like google's sparse array (sparse bitmap really; I'm not sure if google's sparse array code could be used as is). Discarding 2) leads you in the direction of a tree or trie. That's what I'm more interested in. Maybe something based on Judy would suit my purposes.... I've wanted this several times, but never really needed it badly enough to go and implement what I want to see. (As it almost surely involves writing a fair bit of c code.)