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=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 5452FBC6B for ; Tue, 30 Oct 2007 16:04:19 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAEbkJkfBMHhLjGdsb2JhbACOXwIBCAQGCQYa X-IronPort-AV: E=Sophos;i="4.21,347,1188770400"; d="asc'?scan'208";a="5284512" Received: from net.univ-savoie.fr ([193.48.120.75]) by mail3-smtp-sop.national.inria.fr with ESMTP; 30 Oct 2007 16:04:19 +0100 Received: from post.bourget.univ-savoie.fr (post.bourget.univ-savoie.fr [193.48.120.73]) by net.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id l9UF3wwv013750 ; Tue, 30 Oct 2007 16:03:58 +0100 Received: from d45.lama.univ-savoie.fr (d45.lama.univ-savoie.fr [193.48.123.45]) by post.bourget.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id l9UF3hFA004422 ; Tue, 30 Oct 2007 16:03:53 +0100 Message-ID: <472747CD.7020103@univ-savoie.fr> Date: Tue, 30 Oct 2007 16:03:41 +0100 From: Christophe Raffalli User-Agent: Thunderbird 2.0.0.6 (X11/20071008) MIME-Version: 1.0 To: David Allsopp Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Preferred Way to Split a List References: <47266DB7.1020009@SmokejumperIT.com> <20071030012012.GA29836@localhost> <1193723182.6129.66.camel@rosella.wigram><4726E433.7060408@frisch.fr> <4725A915.3020005@univ-savoie.fr> <000001c81af0$ad1ad830$017ca8c0@countertenor> In-Reply-To: <000001c81af0$ad1ad830$017ca8c0@countertenor> X-Enigmail-Version: 0.95.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enigFD447538F9194B8CB4E4DA87" X-Scanned-By: MIMEDefang 2.33 (www . roaringpenguin . com / mimedefang) X-Spam: no; 0.00; christophe:01 raffalli:01 christophe:01 raffalli:01 univ-savoie:01 ocaml:01 struct:01 chablais:01 73376:01 univ-savoie:01 bellow:98 3.1:98 6.2:98 wrote:01 rec:01 X-Attachments: type="application/pgp-signature" name="signature.asc" name="signature.asc" This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enigFD447538F9194B8CB4E4DA87 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable David Allsopp a =E9crit : > Christophe Raffalli wrote: >> let split l n =3D >> let rec aux acc l n =3D >> if n =3D 0 then List.rev acc, l >> else match l with >> [] -> List.rev acc, [] >> | hd::l -> aux (hd::acc) l (n-1) >> in aux [] l n >=20 > let split l n =3D > let acc =3D List.tlempty () > in > let rec aux l n =3D > if n =3D 0 then (List.tlresult acc, l) > else match l with > [] -> (List.tlresult acc, []) > | hd::l -> List.tlcons hd acc; aux l (n-1) > in > aux l n >=20 >=20 My point in my second last post was that in practice, for OCaml, the second code is not much faster than the first ... All this forced me to redo the testing : the details are bellow, but list_split with rev wins for small list, the dirty thing with set_field wins for big lists and the transition is between length 10000 and 100000.= Overall the difference is small. Remark: the result might differ a lot for map if the mapped function does= allocate memory ... then there should almost no difference ... So I would advice not to use Obj.set_field in this case ... (* module for lists that can be constructed by both end *) module Tlist =3D struct type 'a tlist =3D 'a list * 'a list (* a fake value for the tail of a list *) let rec dummy_tlist =3D Obj.magic 0::dummy_tlist let empty =3D [], [] let tailcons tl a =3D match tl with [], [] -> let tl =3D a :: dummy_tlist in (tl, tl) | (_::_ as s), (_::dl as e) when dl =3D=3D dummy_tlist -> let e' =3D a::dummy_tlist in Obj.set_field (Obj.repr e) 1 (Obj.repr e'); s, e' | _ -> raise (Invalid_argument "Tlist.tail_cons") let cons a tl =3D match tl with [], [] -> let tl =3D a :: dummy_tlist in (tl, tl) | (_::_ as s), (_::dl as e) when dl =3D=3D dummy_tlist -> a::s, e | _ -> raise (Invalid_argument "Tlist.cons") (* this must be the final call to transform a 'a tlist into a list *) let append tl l =3D match tl with [], [] -> l | (_::_ as s), (_::dl as e) when dl =3D=3D dummy_tlist -> Obj.set_field (Obj.repr e) 1 (Obj.repr l); s | _ -> raise (Invalid_argument "Tlist.append") end (* the two versions of split *) let split_with_rev l n =3D let rec aux acc l n =3D if n =3D 0 then List.rev acc, l else match l with [] -> List.rev acc, [] | hd::l -> aux (hd::acc) l (n-1) in aux [] l n let split_with_tlist l n =3D let rec aux acc l n =3D if n =3D 0 then (Tlist.append acc [], l) else match l with [] -> Tlist.append acc [], [] | hd::l -> aux (Tlist.tailcons acc hd) l (n-1) in aux Tlist.empty l n (* code for testing *) let rec build_list n =3D let rec aux acc n =3D if n =3D 0 then acc else aux (n::acc) (n-1) in aux [] n let test_tlist n p =3D for i =3D 1 to n do ignore (split_with_tlist (build_list (2*p)) p) done let test_rev n p =3D for i =3D 1 to n do ignore (split_with_rev (build_list (2*p)) p) done let _ =3D test_tlist 10 1000000 (* result: test_tlist 10000000 10 : 3.1s test_rev 10000000 10 : 2.6s test_tlist 100000 1000 : 8.8s test_rev 100000 1000 : 6.9s test_tlist 100 100000 : 5.9s test_rev 100 100000 : 7.4s test_tlist 10 1000000 : 6.2s test_rev 10 1000000 : 7.9s *) --=20 Christophe Raffalli Universite de Savoie Batiment Le Chablais, bureau 21 73376 Le Bourget-du-Lac Cedex tel: (33) 4 79 75 81 03 fax: (33) 4 79 75 87 42 mail: Christophe.Raffalli@univ-savoie.fr www: http://www.lama.univ-savoie.fr/~RAFFALLI --------------------------------------------- IMPORTANT: this mail is signed using PGP/MIME At least Enigmail/Mozilla, mutt or evolution can check this signature. The public key is stored on www.keyserver.net --------------------------------------------- --------------enigFD447538F9194B8CB4E4DA87 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHJ0fUi9jr/RgYAS4RApIiAJ9DDwYUMpP3b9kjFTRRfMc5MT4oLQCgmCar o91uQEWCPY7ZbMWRV9RqTPI= =2wW/ -----END PGP SIGNATURE----- --------------enigFD447538F9194B8CB4E4DA87--