On Sat, 2007-05-26 at 09:25 -0700, Doug Baskins wrote:
> On a different subject, you are not the only one to critique the
> API to Judy.
BTW: I think you should consider seriously the idea of a
purely functional API. In such an API, the input Judy array
is never modified, instead, a new Judy array is created
for every operation that would be a mutator.
For example instead of the procedure
Add(a,key,value)
you have a function
new_a = Add(old_a, key, value)
For trees in general, ignoring 'rebalancing', such operations
usually involve copying all the nodes on the path from the root
to a leaf, but the other nodes stay the same and can be shared
by the old and new trees.
But rebalancing makes a bit of a mess, and most trees give
O(log N) performance at best.
Judy arrays are different .. they're O(1). If you have
a pointer key of length 8 (64 bit machine), the same property
applies as for other trees -- you need to copy the root to
leaf path, but all the other nodes can be shared.
Only, Judy trees do NOT need rebalancing.
Now actually, Judy meta-morphoses nodes along the path,
specialising their type depending on how many keys are
in them .. and this is actually slow anyhow -- so instead
of modifying the nodes, if you're doing a functional
tree you just make a new node of the right type and return
the new tree.
The point is: Judy Trees are the Holy Grail for functional
programming with this semantics. It's the ONLY data structure
known that can provide O(1) functional arrays. Other data
structure might provide 'slow, amortised O(1)' but Judy
provides fast, really truly O(1).
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
