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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id C43E0BC6C for ; Wed, 30 Jan 2008 18:50:55 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAANNHoEfAXQImh2dsb2JhbACQJwEBAQgKKZ9X X-IronPort-AV: E=Sophos;i="4.25,278,1199660400"; d="asc'?ml'?scan'208";a="7440754" Received: from discorde.inria.fr ([192.93.2.38]) by mail1-smtp-roc.national.inria.fr with ESMTP; 30 Jan 2008 18:50:55 +0100 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id m0UHosgB028729 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Wed, 30 Jan 2008 18:50:55 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAExIoEfBMHhLiGdsb2JhbACQGg0BAQEIBAYICRifVw X-IronPort-AV: E=Sophos;i="4.25,278,1199660400"; d="asc'?ml'?scan'208";a="21988487" Received: from net.univ-savoie.fr ([193.48.120.75]) by mail4-smtp-sop.national.inria.fr with ESMTP; 30 Jan 2008 18:50:39 +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 m0UHoY2X027151 ; Wed, 30 Jan 2008 18:50:34 +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 m0UHoUJP004008 ; Wed, 30 Jan 2008 18:50:30 +0100 Message-ID: <47A0B8E7.5010308@univ-savoie.fr> Date: Wed, 30 Jan 2008 18:50:31 +0100 From: Christophe Raffalli User-Agent: Thunderbird 2.0.0.6 (X11/20071022) MIME-Version: 1.0 To: caml-list@inria.fr Subject: Re: [Caml-list] strange timing between search trees References: <47993C41.1050900@univ-savoie.fr> In-Reply-To: <47993C41.1050900@univ-savoie.fr> X-Enigmail-Version: 0.95.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enigF4E396E8E7A5DC8F43234FAF" X-Scanned-By: MIMEDefang 2.33 (www . roaringpenguin . com / mimedefang) X-Miltered: at discorde with ID 47A0B8FE.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; christophe:01 raffalli:01 christophe:01 raffalli:01 univ-savoie:01 stdlib:01 node:01 nodes:01 stdlib:01 ocamlopt:01 cmxa:01 integers:01 integers:01 ocaml:01 chablais:01 X-Attachments: name="set234.ml" name="set234.ml" name="test234tree.ml" name="test234tree.ml" type="application/pgp-signature" name="signature.asc" name="signature.asc" This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enigF4E396E8E7A5DC8F43234FAF Content-Type: multipart/mixed; boundary="------------030006080603030609090404" This is a multi-part message in MIME format. --------------030006080603030609090404 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Dear list members, I did more research for balanced trees ... The conclusion, is really that it is not worth changing the data structur= e for map and set in the stdlib. I produced an algorithm balancing more the 234-trees with the following p= roperties (code attached): Let d be the depth of the tree and n the number of node we have: in all cases d <=3D ln(n)/ln(3) + 1 - I think one can produce a better lo= wer bound for ordered insertion d =3D ln(n)/ln(4) + 1 - This is completely optimal = and means that for 4^d-1 nodes only 4-nodes appear in the tree. for random insertion, it seems that d =3D ln(n)/ln(4) + 2 (I did not prov= e it, but observed it) - this is almost optimal ! These good results are obtained because rebalancing is done to have that = sons of 3-nodes and 4-nodes are never 2-nodes. Despite all this the gain again stdlib set is arround 20% for insertion, = and depends on the size of the trees in all cases for searches. The gain is also much smaller with 3= =2E10 on my intel OS X while I have a more constant gain on 3.09 on my intel linux box. So, unless the mem functions are not fairly optimized in the case of 234-= tree (maybe someone could check the generated assembly code for set234 and stdlib set) it is not wo= rth the work. Here are the timings with 3.09 on linux intel ubuntu 7.10: raffalli@www:~/Caml$ ocamlopt unix.cmxa set234.ml test234tree.ml raffalli@www:~/Caml$ ./a.out 4095 construction of random tree with 200000 integers less then 10^6 234: 1.08s bal: 1.29s 234: 1.10s bal: 1.29s 234: 1.10s bal: 1.29s 234: 1.11s bal: 1.29s search 10^6 times in tree of size 100000 234: 1.78s bal: 1.87s 234: 1.78s bal: 1.86s 234: 1.77s bal: 1.86s 234: 1.78s bal: 1.86s search 10^6 times in tree of size 500000 234: 2.43s bal: 2.72s 234: 2.43s bal: 2.68s 234: 2.43s bal: 2.69s 234: 2.42s bal: 2.68s search 10^6 times in tree of size 2000000 234: 2.71s bal: 3.06s 234: 2.71s bal: 3.05s 234: 2.71s bal: 3.05s 234: 2.72s bal: 3.05s construction of random tree with 200000 integers less then 10^6 (ordered= insertion) 234: 0.35s bal: 0.40s 234: 0.40s bal: 0.38s 234: 0.33s bal: 0.38s 234: 0.36s bal: 0.38s search 10^6 times in tree of size 100000 (ordered insertion) 234: 1.33s bal: 1.21s 234: 1.34s bal: 1.21s 234: 1.34s bal: 1.21s 234: 1.34s bal: 1.21s search 10^6 times in tree of size 500000 (ordered insertion) 234: 1.90s bal: 1.90s 234: 1.90s bal: 1.91s 234: 1.90s bal: 1.91s 234: 1.90s bal: 1.91s search 10^6 times in tree of size 2000000 (ordered insertion) 234: 2.81s bal: 3.29s 234: 2.85s bal: 3.27s 234: 2.81s bal: 3.28s 234: 2.81s bal: 3.26s Christophe PS: I should create a page for "boring ocaml code whose writing is advise= d for meditation" to store this code ;-) --=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 --------------------------------------------- --------------030006080603030609090404 Content-Type: text/plain; name="set234.ml" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline; filename="set234.ml" module type OrderedType =3D sig type t val compare: t -> t -> int end module Make(Ord: OrderedType) =3D struct type elt =3D Ord.t let cmp =3D Ord.compare type t =3D=20 Empty=20 | Node2 of t * elt * t | Node3 of t * elt * t * elt * t | Node4 of t * elt * t * elt * t * elt * t | Node5 of t * elt * t * elt * t * elt * t * elt * t (* Only interm= ediate, never in final result *) let empty =3D Empty let rec mem x =3D function Empty -> false | Node2(t1,d1,t2) -> let c =3D cmp x d1 in c =3D 0 || mem x (if c < 0 then t1 else t2) | Node3(t1,d1,t2,d2,t3) -> let c =3D cmp x d1 in c =3D 0 ||=20 if c < 0 then mem x t1 else let c =3D cmp x d2 in c =3D 0 || mem x (if c < 0 then t2 else t3) | Node4(t1,d1,t2,d2,t3,d3,t4) -> let c =3D cmp x d2 in c =3D 0 || if c < 0 then =20 let c =3D cmp x d1 in c =3D 0 || mem x (if c < 0 then t1 else t2) else let c =3D cmp x d3 in c =3D 0 || mem x (if c < 0 then t3 else t4) | Node5 _ ->=20 assert false let bNode2 t1 d1 t2 =3D match t1, t2 with | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node2(t21,d21,t22) ->= Node2(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node3(t15,d1,t21,d21,t22)= ) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node3(t21,d21,t22,d22= ,t23) -> Node2(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node4(t15,d1,t21,d21,t22,= d22,t23)) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node4(t21,d21,t22,d22= ,t23,d23,t24) -> Node3(Node3(t11,d11,t12,d12,t13),d13,Node3(t14,d14,t15,d1,t21),d21,Nod= e3(t22,d22,t23,d23,t24)) | Node2(t11,d11,t12), Node5(t21,d21,t22,d22,t23,d23,t24,d24,t25) ->= Node2(Node3(t11,d11,t12,d1,t21),d21,Node4(t22,d22,t23,d23,t24,d24,t25)= ) | Node3(t11,d11,t12,d12,t13), Node5(t21,d21,t22,d22,t23,d23,t24,d24= ,t25) -> Node2(Node4(t11,d11,t12,d12,t13,d1,t21),d21,Node4(t22,d22,t23,d23,t24,= d24,t25)) | Node4(t11,d11,t12,d12,t13,d13,t14), Node5(t21,d21,t22,d22,t23,d23= ,t24,d24,t25) -> Node3(Node3(t11,d11,t12,d12,t13),d13,Node3(t14,d1,t21,d21,t22),d22,Nod= e3(t23,d23,t24,d24,t25)) | Node2(Empty,d11,Empty),Empty -> Node3(Empty,d11,Empty,d1,Empty) | Empty, Node2(Empty,d21,Empty) -> Node3(Empty,d1,Empty,d21,Empty) | _ -> Node2(t1,d1,t2) let bNode3 t1 d1 t2 d2 t3 =3D match t1, t2, t3 with | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node2(t21,d21,t22), _= -> Node3(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node3(t15,d1,t21,d21,t22)= ,d2,t3) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node3(t21,d21,t22,d22= ,t23), _ -> Node3(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node4(t15,d1,t21,d21,t22,= d22,t23),d2,t3) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node4(t21,d21,t22,d22= ,t23,d23,t24), Node2(t31,d31,t32) -> Node3(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node4(t15,d1,t21,d21,t22,= d22,t23),d23,Node3(t24,d2,t31,d31,t32)) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node4(t21,d21,t22,d22= ,t23,d23,t24), Node3(t31,d31,t32,d32,t33) -> Node3(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node4(t15,d1,t21,d21,t22,= d22,t23),d23,Node4(t24,d2,t31,d31,t32,d32,t33)) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node4(t21,d21,t22,d22= ,t23,d23,t24), _ -> Node4(Node3(t11,d11,t12,d12,t13),d13,Node3(t14,d14,t15,d1,t21),d21,Nod= e3(t22,d22,t23,d23,t24),d2,t3) | Node2(t11,d11,t12), Node5(t21,d21,t22,d22,t23,d23,t24,d24,t25), = _ -> Node3(Node3(t11,d11,t12,d1,t21),d21,Node4(t22,d22,t23,d23,t24,d24,t25)= ,d2,t3) | _, Node5(t21,d21,t22,d22,t23,d23,t24,d24,t25), Node2(t31,d31,t32)= -> Node3(t1,d1,Node4(t21,d21,t22,d22,t23,d23,t24),d24,Node3(t25,d2,t31,d3= 1,t32)) | Node3(t11,d11,t12,d12,t13), Node5(t21,d21,t22,d22,t23,d23,t24,d2= 4,t25), _ -> Node3(Node4(t11,d11,t12,d12,t13,d1,t21),d21,Node4(t22,d22,t23,d23,t24,= d24,t25),d2,t3) | _, Node5(t21,d21,t22,d22,t23,d23,t24,d24,t25), Node3(t31,d31,t32,= d32,t33) -> Node3(t1,d1,Node4(t21,d21,t22,d22,t23,d23,t24),d24,Node4(t25,d2,t31,d3= 1,t32,d32,t33)) | Node4(t11,d11,t12,d12,t13,d13,t14), Node5(t21,d21,t22,d22,t23,d23= ,t24,d24,t25), _ -> Node4(Node3(t11,d11,t12,d12,t13),d13,Node3(t14,d1,t21,d21,t22),d22,Nod= e3(t23,d23,t24,d24,t25),d2,t3) | _, Node2(t21,d21,t22), Node5(t31,d31,t32,d32,t33,d33,t34,d34,t35)= -> Node3(t1,d1,Node3(t21,d21,t22,d2,t31),d31,Node4(t32,d32,t33,d33,t34,d3= 4,t35)) | _, Node3(t21,d21,t22,d22,t23), Node5(t31,d31,t32,d32,t33,d33,t34,= d34,t35) -> Node3(t1,d1,Node4(t21,d21,t22,d22,t23,d2,t31),d31,Node4(t32,d32,t33,d3= 3,t34,d34,t35)) | Node2(t11,d11,t12), Node4(t21,d21,t22,d22,t23,d23,t24), Node5(t31= ,d31,t32,d32,t33,d33,t34,d34,t35) -> Node3(Node3(t11,d11,t12,d1,t21),d21,Node4(t22,d22,t23,d23,t24,d2,t31),= d31,Node4(t32,d32,t33,d33,t34,d34,t35)) | Node3(t11,d11,t12,d12,t13), Node4(t21,d21,t22,d22,t23,d23,t24), N= ode5(t31,d31,t32,d32,t33,d33,t34,d34,t35) -> Node3(Node4(t11,d11,t12,d12,t13,d1,t21),d21,Node4(t22,d22,t23,d23,t24,= d2,t31),d31,Node4(t32,d32,t33,d33,t34,d34,t35)) | _, Node4(t21,d21,t22,d22,t23,d23,t24), Node5(t31,d31,t32,d32,t33= ,d33,t34,d34,t35) -> Node4(t1,d1,Node3(t21,d21,t22,d22,t23),d23,Node3(t24,d2,t31,d31,t32),d= 32,Node3(t33,d33,t34,d34,t35)) | Node2(Empty,d11,Empty),Empty, Empty -> Node4(Empty,d11,Empty,d1,Empty,d2,Empty) | Empty, Node2(Empty,d21,Empty),Empty -> Node4(Empty,d1,Empty,d21,Empty,d2,Empty) | Empty, Empty, Node2(Empty,d31,Empty) -> Node4(Empty,d1,Empty,d2,Empty,d31,Empty) | _ -> Node3(t1,d1,t2,d2,t3) let bNode4 t1 d1 t2 d2 t3 d3 t4 =3D=20 match t1, t2, t3, t4 with | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node2(t21,d21,t22), _= , _ -> Node4(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node3(t15,d1,t21,d21,t22)= ,d2,t3,d3,t4) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node3(t21,d21,t22,d22= ,t23), _, _ -> Node4(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node4(t15,d1,t21,d21,t22,= d22,t23),d2,t3,d3,t4) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node4(t21,d21,t22,d22= ,t23,d23,t24), Node2(t31,d31,t32), _ -> Node4(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node4(t15,d1,t21,d21,t22,= d22,t23),d23,Node3(t24,d2,t31,d31,t32),d3,t4) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node4(t21,d21,t22,d22= ,t23,d23,t24), Node3(t31,d31,t32,d32,t33), _ -> Node4(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node4(t15,d1,t21,d21,t22,= d22,t23),d23,Node4(t24,d2,t31,d31,t32,d32,t33),d3,t4) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node4(t21,d21,t22,d22= ,t23,d23,t24), Node4(t31,d31,t32,d32,t33,d33,t34), Node2(t41,d41,t42) -> Node4(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node4(t15,d1,t21,d21,t22,= d22,t23),d23,Node4(t24,d2,t31,d31,t32,d32,t33),d33,Node3(t34,d3,t41,d41,t= 42)) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node4(t21,d21,t22,d22= ,t23,d23,t24), Node4(t31,d31,t32,d32,t33,d33,t34), Node3(t41,d41,t42,d42,= t43) -> Node4(Node4(t11,d11,t12,d12,t13,d13,t14),d14,Node4(t15,d1,t21,d21,t22,= d22,t23),d23,Node4(t24,d2,t31,d31,t32,d32,t33),d33,Node4(t34,d3,t41,d41,t= 42,d42,t43)) | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15), Node4(t21,d21,t22,d22= ,t23,d23,t24), _, _ -> Node5(Node3(t11,d11,t12,d12,t13),d13,Node3(t14,d14,t15,d1,t21),d21,Nod= e3(t22,d22,t23,d23,t24),d2,t3,d3,t4) | Node2(t11,d11,t12), Node5(t21,d21,t22,d22,t23,d23,t24,d24,t25), _= , _ -> Node4(Node3(t11,d11,t12,d1,t21),d21,Node4(t22,d22,t23,d23,t24,d24,t25)= ,d2,t3,d3,t4) | _, Node5(t21,d21,t22,d22,t23,d23,t24,d24,t25), Node2(t31,d31,t32)= , _ -> Node4(t1,d1,Node3(t21,d21,t22,d22,t23),d23,Node4(t24,d24,t25,d2,t31,d3= 1,t32),d3,t4) | Node3(t11,d11,t12,d12,t13), Node5(t21,d21,t22,d22,t23,d23,t24,d24= ,t25), _, _ -> Node4(Node4(t11,d11,t12,d12,t13,d1,t21),d21,Node4(t22,d22,t23,d23,t24,= d24,t25),d2,t3,d3,t4) | _, Node5(t21,d21,t22,d22,t23,d23,t24,d24,t25), Node3(t31,d31,t32,= d32,t33), _ -> Node4(t1,d1,Node4(t21,d21,t22,d22,t23,d23,t24),d24,Node4(t25,d2,t31,d3= 1,t32,d32,t33),d3,t4) | _, Node5(t21,d21,t22,d22,t23,d23,t24,d24,t25), Node4(t31,d31,t32,= d32,t33,d33,t34), Node2(t41,d41,t42) -> Node4(t1,d1,Node4(t21,d21,t22,d22,t23,d23,t24),d24,Node4(t25,d2,t31,d3= 1,t32,d32,t33),d33, Node3(t34,d3,t41,d41,t42)) | _, Node5(t21,d21,t22,d22,t23,d23,t24,d24,t25), Node4(t31,d31,t32,= d32,t33,d33,t34), Node3(t41,d41,t42,d42,t43) -> Node4(t1,d1,Node4(t21,d21,t22,d22,t23,d23,t24),d24,Node4(t25,d2,t31,d3= 1,t32,d32,t33),d33, Node4(t34,d3,t41,d41,t42,d42,t43)) | Node4(t11,d11,t12,d12,t13,d13,t14), Node5(t21,d21,t22,d22,t23,d23= ,t24,d24,t25), _, _ -> Node5(Node3(t11,d11,t12,d12,t13),d13,Node3(t14,d1,t21,d21,t22),d22,Nod= e3(t23,d23,t24,d24,t25),d2,t3,d3,t4) | _, Node2(t21,d21,t22), Node5(t31,d31,t32,d32,t33,d33,t34,d34,t35)= , _ -> Node4(t1,d1,Node3(t21,d21,t22,d2,t31),d31,Node4(t32,d32,t33,d33,t34,d3= 4,t35),d3,t4) | _, _, Node5(t31,d31,t32,d32,t33,d33,t34,d34,t35), Node2(t41,d41,t= 42) -> Node4(t1,d1,t2,d2,Node4(t31,d31,t32,d32,t33,d33,t34),d34,Node3(t35,d3,= t41,d41,t42)) | _, Node3(t21,d21,t22,d22,t23), Node5(t31,d31,t32,d32,t33,d33,t34,= d34,t35), _ -> Node4(t1,d1,Node4(t21,d21,t22,d22,t23,d2,t31),d31,Node4(t32,d32,t33,d3= 3,t34,d34,t35),d3,t4) | _, _, Node5(t31,d31,t32,d32,t33,d33,t34,d34,t35), Node3(t41,d41,t= 42,d42,t43) -> Node4(t1,d1,t2,d2,Node4(t31,d31,t32,d32,t33,d33,t34),d34,Node4(t35,d3,= t41,d41,t42,d42,t43)) | Node2(t11,d11,t12), Node4(t21,d21,t22,d22,t23,d23,t24), Node5(t31= ,d31,t32,d32,t33,d33,t34,d34,t35), _ -> Node4(Node3(t11,d11,t12,d1,t21),d21,Node4(t22,d22,t23,d23,t24,d2,t31),= d31,Node4(t32,d32,t33,d33,t34,d34,t35),d3,t4) | Node3(t11,d11,t12,d12,t13), Node4(t21,d21,t22,d22,t23,d23,t24), N= ode5(t31,d31,t32,d32,t33,d33,t34,d34,t35), _ -> Node4(Node4(t11,d11,t12,d12,t13,d1,t21),d21,Node4(t22,d22,t23,d23,t24,= d2,t31),d31,Node4(t32,d32,t33,d33,t34,d34,t35),d3,t4) | _, Node4(t21,d21,t22,d22,t23,d23,t24), Node5(t31,d31,t32,d32,t33,= d33,t34,d34,t35), _ -> Node5(t1,d1,Node3(t21,d21,t22,d22,t23),d23,Node3(t24,d2,t31,d31,t32),d= 32,Node3(t33,d33,t34,d34,t35),d3,t4) | _, _, Node2(t31,d31,t32), Node5(t41,d41,t42,d42,t43,d43,t44,d44,t= 45)-> Node4(t1,d1,t2,d2,Node3(t31,d31,t32,d3,t41),d41,Node4(t42,d42,t43,d43,= t44,d44,t45)) | _, _, Node3(t31,d31,t32,d32,t33), Node5(t41,d41,t42,d42,t43,d43,t= 44,d44,t45)-> Node4(t1,d1,t2,d2,Node4(t31,d31,t32,d32,t33,d3,t41),d41,Node4(t42,d42,= t43,d43,t44,d44,t45)) | _, Node2(t21,d21,t22), Node4(t31,d31,t32,d32,t33,d33,t34), Node5(= t41,d41,t42,d42,t43,d43,t44,d44,t45)-> Node4(t1,d1,Node3(t21,d21,t22,d2,t31),d31,Node4(t32,d32,t33,d33,t34,d3= ,t41),d41,Node4(t42,d42,t43,d43,t44,d44,t45)) | _, Node3(t21,d21,t22,d22,t23), Node4(t31,d31,t32,d32,t33,d33,t34)= , Node5(t41,d41,t42,d42,t43,d43,t44,d44,t45)-> Node4(t1,d1,Node4(t21,d21,t22,d22,t23,d2,t31),d31,Node4(t32,d32,t33,d3= 3,t34,d3,t41),d41,Node4(t42,d42,t43,d43,t44,d44,t45)) | Node2(t11,d11,t12), Node4(t21,d21,t22,d22,t23,d23,t24), Node4(t31= ,d31,t32,d32,t33,d33,t34), Node5(t41,d41,t42,d42,t43,d43,t44,d44,t45)-> Node4(Node3(t11,d11,t12,d1,t21),d21,Node4(t22,d22,t23,d23,t24,d2,t31),= d31,Node4(t32,d32,t33,d33,t34,d3,t41),d41,Node4(t42,d42,t43,d43,t44,d44,t= 45)) | Node3(t11,d11,t12,d12,t13), Node4(t21,d21,t22,d22,t23,d23,t24), N= ode4(t31,d31,t32,d32,t33,d33,t34), Node5(t41,d41,t42,d42,t43,d43,t44,d44,= t45)-> Node4(Node4(t11,d11,t12,d12,t13,d1,t21),d21,Node4(t22,d22,t23,d23,t24,= d2,t31),d31,Node4(t32,d32,t33,d33,t34,d3,t41),d41,Node4(t42,d42,t43,d43,t= 44,d44,t45)) | _, _, Node4(t31,d31,t32,d32,t33,d33,t34), Node5(t41,d41,t42,d42,t= 43,d43,t44,d44,t45)-> Node5(t1,d1,t2,d2,Node3(t31,d31,t32,d32,t33),d33,Node3(t34,d3,t41,d41,= t42),d42,Node3(t43,d43,t44,d44,t45)) | Node2(Empty,d11,Empty),Empty, Empty, Empty -> Node5(Empty,d11,Empty,d1,Empty,d2,Empty,d3,Empty) | Empty, Node2(Empty,d21,Empty),Empty, Empty -> Node5(Empty,d1,Empty,d21,Empty,d2,Empty,d3,Empty) | Empty, Empty, Node2(Empty,d31,Empty), Empty -> Node5(Empty,d1,Empty,d2,Empty,d31,Empty,d3,Empty) | Empty, Empty, Empty, Node2(Empty,d41,Empty) -> Node5(Empty,d1,Empty,d2,Empty,d3,Empty,d41,Empty) | _ -> Node4(t1,d1,t2,d2,t3,d3,t4) let treat_root =3D function | Node5(t11,d11,t12,d12,t13,d13,t14,d14,t15) -> Node2(Node3(t11,d11,t12,d12,t13),d13,Node2(t14,d14,t15)) | t -> t let add x s =3D=20 let rec fn s =3D match s with Empty -> Node2(Empty,x,Empty) | Node2(t1,d1,t2) -> let c =3D cmp x d1 in if c =3D 0 then s else if c < 0 then bNode2 (fn t1) d1 t2 else bNode2 t1 d1 (fn t2) | Node3(t1,d1,t2,d2,t3) -> let c =3D cmp x d1 in if c =3D 0 then s else if c < 0 then bNode3 (fn t1) d1 t2 d2 t3 else let c =3D cmp x d2 in if c =3D 0 then s else=20 if c < 0 then bNode3 t1 d1 (fn t2) d2 t3=20 else bNode3 t1 d1 t2 d2 (fn t3) | Node4(t1,d1,t2,d2,t3,d3,t4) -> let c =3D cmp x d2 in if c =3D 0 then s else if c < 0 then =20 let c =3D cmp x d1 in if c =3D 0 then s else=20 if c < 0 then bNode4 (fn t1) d1 t2 d2 t3 d3 t4 else bNode4 t1 d1 (fn t2) d2 t3 d3 t4 else let c =3D cmp x d3 in if c =3D 0 then s else=20 if c < 0 then bNode4 t1 d1 t2 d2 (fn t3) d3 t4=20 else bNode4 t1 d1 t2 d2 t3 d3 (fn t4) | Node5 _ ->=20 assert false in treat_root (fn s) =09 let rec cardinal =3D function Empty -> 0 | Node2(t1,_,t2) -> cardinal t1 + cardinal t2 + 1 | Node3(t1,_,t2,_,t3) -> cardinal t1 + cardinal t2 + cardinal t3 + = 2 | Node4(t1,_,t2,_,t3,_,t4) -> cardinal t1 + cardinal t2 + cardinal = t3 + cardinal t4 + 3 | Node5 _ -> assert false let rec test_height t =3D match t with Empty -> 0 | Node2(t1,_,t2) -> let h1 =3D test_height t1 in let h2 =3D test_height t2 in assert (h1 =3D h2); h1 + 1 | Node3(t1,_,t2,_,t3) -> let h1 =3D test_height t1 in let h2 =3D test_height t2 in let h3 =3D test_height t3 in assert (h1 =3D h2); assert (h1 =3D h3); h1 + 1 | Node4(t1,_,t2,_,t3,_,t4) -> let h1 =3D test_height t1 in let h2 =3D test_height t2 in let h3 =3D test_height t3 in let h4 =3D test_height t4 in assert (h1 =3D h2); assert (h1 =3D h3); assert (h1 =3D h4); h1 + 1 | Node5 _ -> assert false =20 end =09 --------------030006080603030609090404 Content-Type: text/plain; name="test234tree.ml" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline; filename="test234tree.ml" module Int =3D struct type t =3D int let compare =3D compare end module Set1 =3D Set234.Make(Int) let create1 size max =3D let rec fn acc remain =3D if remain =3D 0 then acc else let x =3D Random.int max in fn (Set1.add x acc) (remain - 1) in fn Set1.empty size module Set2 =3D Set.Make(Int) let create2 size max =3D let rec fn acc remain =3D if remain =3D 0 then acc else let x =3D Random.int max in fn (Set2.add x acc) (remain - 1) in fn Set2.empty size let create12 size max =3D let rec fn acc acc' remain =3D if remain =3D 0 then acc, acc' else let x =3D Random.int max in fn (Set1.add x acc) (Set2.add x acc') (remain - 1) in fn Set1.empty Set2.empty size let ocreate1 size max =3D let rec fn acc remain =3D if remain =3D 0 then acc else let x =3D remain in fn (Set1.add x acc) (remain - 1) in fn Set1.empty size let ocreate2 size max =3D let rec fn acc remain =3D if remain =3D 0 then acc else let x =3D remain in fn (Set2.add x acc) (remain - 1) in fn Set2.empty size let ocreate12 size max =3D let rec fn acc acc' remain =3D if remain =3D 0 then acc, acc' else let x =3D remain in fn (Set1.add x acc) (Set2.add x acc') (remain - 1) in fn Set1.empty Set2.empty size let search1 t size max =3D let rec fn acc remain =3D if remain =3D 0 then acc else let x =3D Random.int max in fn (if Set1.mem x t then acc+1 else acc) (remain - 1) in fn 0 size let search2 t size max =3D let rec fn acc remain =3D if remain =3D 0 then acc else let x =3D Random.int max in fn (if Set2.mem x t then acc+1 else acc) (remain - 1) in fn 0 size let t1,t2 =3D=20 let n =3D int_of_string Sys.argv.(1) in create12 n (n*3) let h =3D Set1.test_height t1 let _ =3D=20 print_int h; print_newline (); print_int (Set1.cardinal t1); print_newline (); print_int (Set2.cardinal t2); print_newline (); if Set2.for_all (fun n -> Set1.mem n t1) t2 then print_string "identical trees\n" let t1,t2 =3D=20 let n =3D int_of_string Sys.argv.(1) in ocreate12 n (n*3) let h =3D Set1.test_height t1 let _ =3D=20 print_int h; print_newline (); print_int (Set1.cardinal t1); print_newline (); print_int (Set2.cardinal t2); print_newline (); if Set2.for_all (fun n -> Set1.mem n t1) t2 then print_string "identical trees\n" let chrono s f x =3D let {Unix.tms_utime =3D ut;Unix.tms_stime =3D st} =3D Unix.times () in let r =3D f x in let {Unix.tms_utime =3D ut';Unix.tms_stime =3D st'} =3D Unix.times () i= n Printf.printf "%s: %.2fs\n" s ((ut' -. ut) +. (st' -. st)); flush stdout; ignore r let _ =3D print_string "construction of random tree with 200000 interger less the= n 10^6"; print_newline (); chrono "234" (create1 200000) 1000000; chrono "bal" (create2 200000) 1000000; chrono "234" (create1 200000) 1000000; chrono "bal" (create2 200000) 1000000; chrono "234" (create1 200000) 1000000; chrono "bal" (create2 200000) 1000000; chrono "234" (create1 200000) 1000000; chrono "bal" (create2 200000) 1000000; let t1, t2 =3D create12 100000 1000000 in print_string "search 10^6 times in tree of size 100000"; print_newline = (); chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; let t1, t2 =3D create12 500000 1000000 in print_string "search 10^6 times in tree of size 500000"; print_newline = (); chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; let t1, t2 =3D create12 2000000 1000000 in print_string "search 10^6 times in tree of size 2000000"; print_newline= (); chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; print_string "construction of random tree with 200000 interger less the= n 10^6 (ordered insertion)"; print_newline (); chrono "234" (ocreate1 200000) 1000000; chrono "bal" (ocreate2 200000) 1000000; chrono "234" (ocreate1 200000) 1000000; chrono "bal" (ocreate2 200000) 1000000; chrono "234" (ocreate1 200000) 1000000; chrono "bal" (ocreate2 200000) 1000000; chrono "234" (ocreate1 200000) 1000000; chrono "bal" (ocreate2 200000) 1000000; let t1, t2 =3D ocreate12 100000 1000000 in print_string "search 10^6 times in tree of size 100000 (ordered inserti= on)"; print_newline (); chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; let t1, t2 =3D ocreate12 500000 1000000 in print_string "search 10^6 times in tree of size 500000 (ordered inserti= on)"; print_newline (); chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; let t1, t2 =3D ocreate12 2000000 1000000 in print_string "search 10^6 times in tree of size 2000000 (ordered insert= ion)"; print_newline (); chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000; chrono "234" (search1 t1 1000000) 1000000; chrono "bal" (search2 t2 1000000) 1000000 --------------030006080603030609090404-- --------------enigF4E396E8E7A5DC8F43234FAF 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 iD8DBQFHoLjti9jr/RgYAS4RAvvVAJ4oUhUymMTg6OBuT7XM2YIgI8yv/ACfRLoF +uedxIqi+x9lata8UiGL9U8= =VSZj -----END PGP SIGNATURE----- --------------enigF4E396E8E7A5DC8F43234FAF--