Hacker News Reader

What's the data structure you'd use when Judy arrays would be a good fit but the implementation doesn't exist for your language of choice? I mean: what's the closest to Judy arrays that's ubiquitous? Roaring bitmaps maybe?

View on HN

Roaring bitmaps are integer sets with optimized set-wise operations, like intersecting two sets to find out which integers are contained by both. Judy is an associate array (so it's interface is similar to a hash table). There's a specialized case for word->bit, but no set-wise operations and no way to match the performance of roaring for those.

This doesn't quite answer your question, but if Roaring fits your case you should use it instead of Judy1 even if have Judy1 available.

> but if Roaring fits your case you should use it instead of Judy1 even if have Judy1 available.

Why? Assuming you have no need for the specialized whole set union and intersection operations. At least the C roaring library only supports 32-bit keys which is a hard blocker vs judy1 for some applications.

I like hashed tries a lot. That's essentially a sparse array indexed by strings. Works well as a persistent data structure. Popularised by clojure and scala.

Reply on news.ycombinator.com