On 13/02/2011, at 12:28 AM, Schaeferhaus wrote: > Hi, > > it is sade that there are not so many examples showing how powerfull the judy > arrays library is.
Yes. In fact, Judy is pretty close to a "perfect" data structure. Almost all operations have minimum possible order, usually O(1) or O(n), and it is fast in the real world as well. It provides both sequential and random access at this high speed, including searches with total order relations (< <= == >= > and can even find "empty" slots): there's no other data structure I know of that can do this. There are two downsides. The first is seriously interesting but I don't think Doug has looked at this yet, possibly because he's a bit "old world" :) :) *Functional Judy* What's that? That's a version of Judy which is purely functional. For example instead of "JudyIns" inserting into an existing array, a new array is created with the new element, the old array is untouched. Using actual arrays this is an O(N) operation. However trees using shared subtrees can do this in O(log N). Ocaml and Haskell both provide this kind of tree for implementation of function sets and maps. However its still way short of the performance of an imperative array modifying an element, which is O(1) ... just store the new element in the i'th slot. Since Judy is a tree .. an functional implementation should be possible. It would revolutionise functional programming. The second downside is that the interface confuses 64 bit integers are 64 bit pointers. Unfortunately that's C for you. The problem is sometimes Judy requires a pointer to a word and other times a word. We have to choose the word as an integer and force a cast for the pointers, and that means you can get the cast wrong. This problem would go away in C++ using templates. Or in Felix with a similar superior type system. It could also go away in C with "inline" wrappers: C99 has "inline" so this is actually possible .. however it doesn't have overloading so that would make the interface a lot harder than in C++ which does. So Judy is a bit harder to use than would be nice, because it is a C API. All in all though it is a really nice base system: I'm heavily critical of just about everything, but I think the C API is right. A lot of work went into making it right I'm sure. You can tell it's right: an empty Judy array is a NULL pointer. Very clean. -- john skaller [email protected] ------------------------------------------------------------------------------ The ultimate all-in-one performance toolkit: Intel(R) Parallel Studio XE: Pinpoint memory and threading errors before they happen. Find and fix more than 250 security defects in the development cycle. Locate bottlenecks in serial and parallel code that limit performance. http://p.sf.net/sfu/intel-dev2devfeb _______________________________________________ Judy-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/judy-devel
