From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id E71EBBB9A for ; Mon, 26 Sep 2005 23:29:09 +0200 (CEST) Received: from web26806.mail.ukl.yahoo.com (web26806.mail.ukl.yahoo.com [217.146.176.82]) by nez-perce.inria.fr (8.13.0/8.13.0) with SMTP id j8QLT9xk001221 for ; Mon, 26 Sep 2005 23:29:09 +0200 Received: (qmail 72916 invoked by uid 60001); 26 Sep 2005 21:29:09 -0000 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.de; h=Message-ID:Received:Date:From:Subject:To:Cc:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=ZS418Dnd70LukFI/JDb8D/H00+Y3jwAwW7zVPLQuU8E6uaAtjLE+DhCSRiOyZ3VlWHHdA7KOX68oSJWjoIu3hSyVSC863VzSte5DNS6iW5YlZ/iEq88EhZM1DUKV/ns9peVz51xLPCoi10s/WLZrJo0ZvEwbYIieA7RAe9JkHzs= ; Message-ID: <20050926212909.72914.qmail@web26806.mail.ukl.yahoo.com> Received: from [213.103.152.126] by web26806.mail.ukl.yahoo.com via HTTP; Mon, 26 Sep 2005 23:29:08 CEST Date: Mon, 26 Sep 2005 23:29:08 +0200 (CEST) From: Martin Chabr Subject: Ant: Re: [Caml-list] Avoiding shared data To: Brian Hurt Cc: caml-list@yquem.inria.fr In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Miltered: at nez-perce with ID 43386825.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 avoiding:01 intuitively:01 ocaml:01 ocaml:01 marshaling:01 arrays:01 pairs:01 integers:01 arrays:01 struct:01 foo:01 baz:01 struct:01 foo:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.4 required=5.0 tests=DNS_FROM_RFC_ABUSE autolearn=disabled version=3.0.3 Hello Brian, thank you for the whole lot of useful tips and nice explanations. It is immediately clear to me how to copy a record and a tuple, but I will need some time to think about your suggestions using a map. Intuitively I feel that it needs a method to create non-shared data structures in the first place, so that no copying whatsoever is needed. Regards, Martin --- Brian Hurt schrieb: > > > On Sun, 25 Sep 2005, Martin Chabr wrote: > > > Working with non-shared data structures in OCaml > > Deep copy of OCaml structures, marshaling > > ================================================ > > > > Dear group members, > > > > I need to process arrays of pairs of integers and > > records ((int * record) array) in which all > elements > > must be updated individually, which means that > > unshared data structures must be used. For arrays > of > > arrays I can produce unshared data by using the > > library functions Array.copy and Array.append to > > append the individual arrays into the embedding > array. > > It works, the low level arrays can be updated > > individually. But I cannot use the same scheme to > the > > array of the (int * record) structures, because I > do > > not know how to copy these structures to dissolve > the > > sharing. I do not even know how to copy records. > It > > seems to me that this problem occurs always when I > > want to produce an array of data with a fixed > > structure automatically (rather than entering the > > array [| ... |] by hand at the top level > interpreter > > using constants only). How can I produce > completely > > unshared structures? > > First of all, you can copy a structure easily enough > using the with key > word. Say you have: > > type my_struct = { > foo: int; > bar: float; > baz: string; > } > > You can write a copy function just like: > > let copy_my_struct x = { x with foo = x.foo };; > > In this case, the "with" construct says "create a > new structure with the > same elements as the old structure, except give the > foo member this new > value (which in this case just happens to be the > same value as the old > value)". Unfortunately you have to specify at least > one new value to use > the with construct, even if it doesn't get a new > value. This is > especially usefull if there are other value you want > to copy, for example, > you probably want to write: > > let copy_my_struct x = { x with baz = String.copy > x.baz } > > As this doesn't just create a new copy of the > structure, it also creates a > new copy of the string as well (foo and bar get > whatever values the > original structure had). > > I can create a new tuple just by breaking the old > tuple apart and putting > it back together again. For all two element tuples, > I can create a new > copy of them just by going: > > let copy_tuple (a,b) = a,b > > This function, given a tuple of two elements, > creates a new tuple with the > same two elements. > > The easiest way to create a new list from old values > is to just use the > map function. The output list type of List.map can > be the same type as > the input list. This is really usefull- imagine > that I want to add 1 each > to a list of floats, I can just write: > > List.map (fun i -> i + 1) lst > > So, to answer you specific question, say I have an > (int * my_struct) list > (where t is the structure I defined above). The > function to create a > whole new copy of this list (assuming I've written > copy_t like I did > above) is just: > > let copy_list lst = List.map (fun (i,s) -> i, > (copy_my_struct s)) lst > > Notice that I made copy_tuple an anonymous (unnamed) > function there. With > a couple of more tricks I can fit the whole thing on > one line: > > let cplst = List.map (fun (i,s) -> i, {s with baz = > String.copy s.baz}) > > Which is nice for bragging rights, but I kind of > like the more unpacked > version. > > Now, I'm going to jump from the question you asked > to the question you > didn't ask, and make a big assumption along the way. > I'd bet dollars to > donuts that you really don't want to be using either > lists or array- you > really want to be using a map. Let me guess: you've > written a function > like: > > let rec find i lst = (* find element i in list lst) > match lst with > | (j, s) :: t -> > if i == j then > s > else > find i t > | [] -> raise Not_found > > and are calling it a lot (or rewritting it a lot). > If this is the case, > then what you really want to be using is a map, not > a list or an array. > You can do this with the following code: > > module Int = struct > type t = int > let compare (x: int) y = > if x < y then > -1 > else if x > y then > 1 > else > 0 > end;; > > module IntMap = Map.Make(Int);; > > Now you can just keep your structures in a my_struct > IntMap.t. The find > function is now: > let find i lst = (* lst is a IntMap, not a list *) > IntMap.find i lst > ;; > > The big difference here is that IntMap.find is O(log > N) cost, while the > list-based find I wrote above is O(N) cost. What > this means is that if > the list is 1000 elements long, the list-based find > will have to do (on > aveage) about 500 steps of processing to find the > answer- it has to walk > halfway down the list. The IntMap.find function, > however, only has to do > about 10 steps on average to find the answer- it's > literally 50 times > faster to do the IntMap.find in this case than the > list-based find. If > we're dealing with a million elements, the > list-based find will take > 500,000 steps to find the answer on average, the > IntMap.find only 20, for > an incredible speed up of 25,000 times. > > Note that IntMap has a map function as well- so I > can steal the exact same > trick to copy it (but note that I don't have to > allocate the new tuples): > > let copy_list lst = (* list is an IntMap, not a list > *) > IntMap.map copy_my_struct lst > ;; > > If you actually want the associated integers as > well, use mapi instead of > map. > > Note that O(log N) vr.s O(N) thing applies to > updates as well. Let's say > === message truncated === ___________________________________________________________ Was denken Sie über E-Mail? Wir hören auf Ihre Meinung: http://surveylink.yahoo.com/wix/p0379378.aspx