Re: Fwd: [Caml-list] Comparison of OCaml and MLton for numerics

[skaller <skaller@users.sourceforge.net>]

On Tue, 2007-06-05 at 00:19 +0200, Till Varoquaux wrote:
> Forgot the reply-to-all....

> At a first glance these could be translated to persistent data
> structures, although with a cost  (they are "upside down": inserting a
> new element modifies one of the leafs... but this is also the case
> with red/black trees). It doesn't seem to me that most operations
> would be O(1) (sounds too good to be true anyways*), I'd rather guess
> O(ln(n)) (where log is base 256 and n is length of the element we are
> storing/querying etc...). 

Integers are fixed size ... it's an array remember, integers
are the keys, so it's O(1) because ln 64 ~= 1 :) The main thing
is it isn't O(ln N) where N is the number of elements in the array.

> I do wonder how well these would scale when
> used with big elements. they might prove an interesting back-end for
> an implementation of maps (values would be stored in the nodes).

JudySL accepts C style null terminated strings. It sorts them faster
than the GNU sort command. JudyHS tries to work for strings with length
count, and combines a Trie with a Hashtable, but it doesn't supply
an iterator at the moment so it's fairly useless.

I make no claims for non-fixed sized keys.

> Most of the optimizations seem to reside more on the low level details
> of the implementation rather than on the algorithmic side (which seems
> fairly classical from a distance).

Correct .. Tries are already theoretically optimal .. they're just
not very fast in practice on modern machines because size matters
due to caching .. Judy arrays solve that problem, which isn't really
a theoretical one.

However the implementation is mutable .. in a functional version
if you write:

	newA = OldA + element

and OldA isn't reachable now, there's also a load on the garbage
collector which is part of the real cost, and that cost might
be proportional to the number of insertions.. so maybe this
data structure isn't very good in functional form?


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net