IntSet
Caleb Clausen
google_hash library? Somehow, this is a construct that I keep wanting
to have. How efficient is it, in time and space.
Roger Pack
> google_hash library? Somehow, this is a construct that I keep wanting
> to have. How efficient is it, in time and space.
Did you just want Fixnum's or Bignum? Did you want it in the hash library?
-r
Caleb Clausen
Well, I guess I'm interested in finding out about what the tradeoffs and
limitations are. Bignums are nice, but I'm really thinking about
efficient storage. I thought I remembered somewhere you (I think it was
you...) saying that space efficiency for integer sets should be 1 bit
per item in the set, but I may be misremembering. Google's docs aren't
being a lot of help to me, I'm afraid.
Roger Pack
> limitations are. Bignums are nice, but I'm really thinking about
> efficient storage. I thought I remembered somewhere you (I think it was
> you...) saying that space efficiency for integer sets should be 1 bit
> per item in the set, but I may be misremembering. Google's docs aren't
> being a lot of help to me, I'm afraid.
Yeah if you use the GoogleHashSparseIntToInt it's said to use "2 bits
per entry" for the key,
so theoretically it's 2+4(key) + 4(value) per entry. Plus the GC
doesn't have to collect it :)
Caleb Clausen
<<Scratch head?>>
Ok, so are you saying its a total of 2+4+4=10 bits per integer stored in
the set? But that doesn't make a whole lotta sense... the 4s make me
think you mean 4 BYTES per key and value, which would add up as
4+32+32=68 bits per integer stored. (Which is a lot more bulky and less
appealing...)
Please help me and my little brain understand...
Roger Pack
>> per entry" for the key,
>> so theoretically it's 2+4(key) + 4(value) per entry. Plus the GC
>> doesn't have to collect it :)
>
> <<Scratch head?>>
Ahh good point. So instead of Ruby's typical ?? bits + 20 + 20 per
key value pair, you get 2 +4+4 = 10. Of course, even in C land that's
about as small as it's gonna get for a hash.
Yeah you had it right.
-rp