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.3 required=5.0 tests=AWL,SPF_SOFTFAIL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id B20ADBC69 for ; Thu, 19 Jul 2007 10:18:32 +0200 (CEST) Received: from animal.inescn.pt (ns.inescn.pt [192.35.246.1]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6J8IVXe012041 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Thu, 19 Jul 2007 10:18:32 +0200 Received: from localhost (localhost [127.0.0.1]) by animal.inescn.pt (8.13.8/8.13.6/9) with ESMTP id l6J8IT33023225; Thu, 19 Jul 2007 09:18:29 +0100 (WEST) X-Virus-Scanned: amavisd-new at inescporto.pt Received: from animal.inescn.pt ([127.0.0.1]) by localhost (animal.inescn.pt [127.0.0.1]) (amavisd-new, port 10024) with LMTP id p3LkEVxcP212; Thu, 19 Jul 2007 09:18:04 +0100 (WEST) Received: from [194.117.30.94] (morfina.inescn.pt [194.117.30.94]) by animal.inescn.pt (8.13.8/8.13.8/11) with ESMTP id l6J8Hsu3023197; Thu, 19 Jul 2007 09:17:56 +0100 (WEST) Message-ID: <469F1E32.3040502@inescporto.pt> Date: Thu, 19 Jul 2007 09:17:54 +0100 From: Hugo Ferreira User-Agent: Thunderbird 2.0.0.4 (X11/20070618) MIME-Version: 1.0 To: Loup Vaillant Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Vec: a functional implementation of extensible arrays References: <28fa90930707181032q7681340pc30fb47434aff5fc@mail.gmail.com> <6f9f8f4a0707190045g609abca4kfa3bb39d93604081@mail.gmail.com> In-Reply-To: <6f9f8f4a0707190045g609abca4kfa3bb39d93604081@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Miltered: at concorde with ID 469F1E57.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; arrays:01 filliatre:01 arrays:01 backtracking:01 nodes:01 backtracking:01 lri:01 filliatr:01 publis:01 ocaml:01 iterating:01 stack:01 bounded:01 stack:01 worst-case:01 Hello, For those of you interested in functional array consider Sylvain Conchon and Jean-Christophe Filliātre paper in [1]. The Union-Find (UF) uses persistent arrays as its base data structure. I have made tests with the UF using the code provided, an implementation of k-BUF data structure (delayed backtracking) and altered version of the persistent array (fat nodes + delayed backtracking). The tests I did show that this version of persistent arrays is very efficient (especially for single threaded backtracking). Maybe Luca could pit his implementation against that of the article and report on how they fare? Regards, Hugo Ferreira. [1] http://www.lri.fr/~filliatr/ftp/publis/puf-wml07.ps Loup Vaillant wrote: > 2007/7/18, Luca de Alfaro : >> Dear All, >> >> I would like to share with you an Ocaml implementation of extensible >> arrays. >> The implementation is functional, based on balanced trees (and on the >> code >> for Set and Map); I called the module Vec (for vector - I like >> short names). You can find it at >> http://www.dealfaro.com/home/vec.html >> Module Vec provides, in log-time: >> >> Access and modification to arbitrary elements ( Vec.put n el v puts >> element >> el in position n of vector v, for instance). >> Concatenation >> Insertion and removal of elements from arbitrary positions >> (auto-enlarging >> and auto-shrinking the vector). >> as well as: >> >> All kind of iterators and some visitor functions. >> Efficient translation to/from lists and arrays. >> An advantage of Vec over List, for very large data structures, is that >> iterating over a Vec of size n requires always stack depth bounded by >> log n: >> with lists, non-tail-recursive functions can cause stack overflows. >> >> I have been using this data structure for some months, and it has been >> very >> handy in a large number of occasions. I hope it can be as useful to you. >> >> I would appreciate all advice and feedback. Also, is there a repository >> where I should upload it? Do you think it is worth it? >> >> All the best, >> >> Luca > > Very interesting. I always felt uneasy about the presence of > imperative arrays without a functional counterpart. I can't wait to > try it. > > Looking at your array type definition, I assume that the timings you > specified are worst-case? Is it possible to achieve better (but > amortized) bounds? Do you think it would be worth the trouble? > > I didn't see in your specs the complexity of your iterators. Does > these work in linear time, like those of the List and Array module? > > Regards, > Loup > > _______________________________________________ > 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 >