Version française
Home     About     Download     Resources     Contact us    
Browse thread
Comparison of OCaml and MLton for numerics
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] Comparison of OCaml and MLton for numerics
On Mon, 2007-06-04 at 15:39 +0100, Jon Harrop wrote:

> A functional array implemented as a balanced binary tree needs the number of 
> elements (size) of a sub tree just to index into the tree. 

It might be worth considering a functional version of Judy arrays:

http://judy.sourceforge.net/

They're fairly close to ideal: all operations are O(1),
they never need rebalancing, and they work just as well with
sparse arrays as compact ones. Judy arrays are digital tries
with compressed nodes. It's not clear whether a functional
variation would retain the performance claimed for the mutable
version.

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