> On 24 Jan 2020, at 06:29, <[email protected]> <[email protected]> > wrote: > > Just to clarify, I need to walk all set indexes in random order. I thought > you meant Judy1Test as you mentioned below, might be a good bet to modify to > create Judy1Rand to randomly walk the Judy data structure 1 bit at a time. > But checking one bit at a time would not return the Indices uniformly in a > tree, without taking into account the count of Indices below a certain bit > level. It would just be more fun to select an integer between 1,...,(no of > indices left in Judy1 Array) and use J1BC to pick it out. Then keep repeating > until none left. It doesn't need to happen too often, so all good. > > Thanks everyone for your help :). I think I've got what I need. > > Judy Arrays are awesome.
indeed. There is no other data structure in existence I know of with its properties: O(1) random access O(1) linear scanning O(1) insert and delete Hashtables can do O(1) random access but do not support linear scanning. Various trees exist with good performance, such as C++ map, which is red-black tree. It has O(log N) access and scanning though. I did some tests and C++ map is actually quite good. Its not quite as fast or scalable as Judy but comes close. Its BIG advantage over Judy is that the keys can be anything totally ordered whereas Judy only supports a machine word as a key. Also, JudyL data has to be a machine word, but that can be a pointer to anything, at the cost of an extra heap allocation and a headache remembering to delete the data object. I implemented a naive digital trie and the performance was disgusting. I also implemented a smarter hybrid with reasonable performance designed to replace my use of JudyL for tracking heap allocations (in my GC). It was OK, but both Judy and C++ map were better (and bug free). The authors of Judy spent a decade tuning it. — John Skaller [email protected] _______________________________________________ Judy-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/judy-devel
