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=1.1 required=5.0 tests=AWL,SPF_NEUTRAL 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 1C6F5BC0A for ; Tue, 5 Jun 2007 00:19:25 +0200 (CEST) Received: from ug-out-1314.google.com (ug-out-1314.google.com [66.249.92.175]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l54MJOTb019184 for ; Tue, 5 Jun 2007 00:19:24 +0200 Received: by ug-out-1314.google.com with SMTP id p27so877016ugc for ; Mon, 04 Jun 2007 15:19:20 -0700 (PDT) DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=niRpvQaol7joojR/4TsodK2CN5Yp0ZNFnsZA8G6wsf9q97R4SF1uMOa/jsoinOr2pliGgsEX/gD35+SdzCfXnrc2DMnA4okAOMFR2GI+n4rbdDIQ4ap92rS511FVGN3WX1P6zZeXE/xwo+MeWy+cJqrfr5NbVc6tRkc5D1Utvb8= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=GjjsyIWZPmzwfZb1n+OEjfWI+IpCm7prwj9tb+kQuXkF7iipoxDrNoxcsYVwmoB+27QfhTgDFLI5WQNC2dyBlHy7aEsVb0NRzATa51WeJbPlG3vp2tmw9xWmqbW2GbWvg2OcRf07frr/R1sAUKiwYtCv49fgrA2dCumSy+ic08g= Received: by 10.67.32.16 with SMTP id k16mr3381482ugj.1180995560856; Mon, 04 Jun 2007 15:19:20 -0700 (PDT) Received: by 10.66.233.7 with HTTP; Mon, 4 Jun 2007 15:19:20 -0700 (PDT) Message-ID: <9d3ec8300706041519y57915f66s9506096a0cb9f9d6@mail.gmail.com> Date: Tue, 5 Jun 2007 00:19:20 +0200 From: "Till Varoquaux" To: OCaml Subject: Fwd: [Caml-list] Comparison of OCaml and MLton for numerics In-Reply-To: <9d3ec8300706041518y115d22bdsa120d4010261d841@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <5195a210705302250u6a9e5adey4ed857480f9e5cd8@mail.gmail.com> <200706011813.48515.jon@ffconsultancy.com> <46641BC1.9090305@cs.umd.edu> <200706041539.03286.jon@ffconsultancy.com> <1180980488.6220.18.camel@rosella.wigram> <9d3ec8300706041518y115d22bdsa120d4010261d841@mail.gmail.com> X-j-chkmail-Score: MSGID : 46648FEC.000 on discorde : j-chkmail score : XX : 0/20 2 0.000 -> 2 X-Miltered: at discorde with ID 46648FEC.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 ocaml:01 translated:01 inserting:01 nodes:01 hashtables:01 hashing:01 wikipedia:01 wiki:01 sdu:01 0100,:01 arrays:01 arrays:01 nodes:01 mutable:01 Forgot the reply-to-all.... ---------- Forwarded message ---------- From: Till Varoquaux Date: Jun 5, 2007 12:18 AM Subject: Re: [Caml-list] Comparison of OCaml and MLton for numerics To: skaller Hmm.... 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...). 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). 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). For more functional data structures you might be interested by vlists. There is even an OCaml version. Regards, Till * Since hashtables have to deal with collisions and hashing of large values, I do not consider their operations to be O(1). [1]http://en.wikipedia.org/wiki/VList [2]http://www.imada.sdu.dk/~bardur/personal/45-programs/index.html On 6/4/07, skaller wrote: > 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 > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs >