Ant: Re: [Caml-list] Avoiding shared data

[Martin Chabr <martin_chabr@yahoo.de>]

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 <bhurt@spnz.org> 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