From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id A3256BC0A for ; Mon, 4 Jun 2007 20:08:18 +0200 (CEST) Received: from ipmail03.adl2.internode.on.net (ipmail03.adl2.internode.on.net [203.16.214.135]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l54I8GaV004847 for ; Mon, 4 Jun 2007 20:08:17 +0200 X-IronPort-AV: E=Sophos;i="4.16,381,1175437800"; d="scan'208";a="98842411" Received: from ppp9-14.lns1.syd7.internode.on.net (HELO [192.168.1.201]) ([59.167.9.14]) by ipmail03.adl2.internode.on.net with ESMTP; 05 Jun 2007 03:38:12 +0930 Subject: Re: [Caml-list] Comparison of OCaml and MLton for numerics From: skaller To: Jon Harrop Cc: caml-list@yquem.inria.fr In-Reply-To: <200706041539.03286.jon@ffconsultancy.com> References: <5195a210705302250u6a9e5adey4ed857480f9e5cd8@mail.gmail.com> <200706011813.48515.jon@ffconsultancy.com> <46641BC1.9090305@cs.umd.edu> <200706041539.03286.jon@ffconsultancy.com> Content-Type: text/plain Date: Tue, 05 Jun 2007 04:08:08 +1000 Message-Id: <1180980488.6220.18.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.10.1 Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 46645510.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 0100,:01 arrays:01 arrays:01 nodes:01 mutable:01 sourceforge:01 sourceforge:01 wrote:01 caml-list:01 binary:01 implemented:02 tree:02 tree:02 functional:02 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 Felix, successor to C++: http://felix.sf.net