From: Christophe Raffalli <christophe.raffalli@univ-savoie.fr>
To: caml-list@inria.fr
Subject: Re: [Caml-list] strange timing between search trees
Date: Wed, 30 Jan 2008 18:50:31 +0100 [thread overview]
Message-ID: <47A0B8E7.5010308@univ-savoie.fr> (raw)
In-Reply-To: <47993C41.1050900@univ-savoie.fr>
[-- Attachment #1.1: Type: text/plain, Size: 3321 bytes --]
Dear list members,
I did more research for balanced trees ...
The conclusion, is really that it is not worth changing the data structure for map
and set in the stdlib.
I produced an algorithm balancing more the 234-trees with the following properties (code attached):
Let d be the depth of the tree and n the number of node we have:
in all cases d <= ln(n)/ln(3) + 1 - I think one can produce a better lower bound
for ordered insertion d = 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 = ln(n)/ln(4) + 2 (I did not prove 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.10 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 worth 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 advised for meditation" to
store this code ;-)
--
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
---------------------------------------------
[-- Attachment #1.2: set234.ml --]
[-- Type: text/plain, Size: 14420 bytes --]
module type OrderedType =
sig
type t
val compare: t -> t -> int
end
module Make(Ord: OrderedType) =
struct
type elt = Ord.t
let cmp = Ord.compare
type t =
Empty
| 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 intermediate, never in final result *)
let empty = Empty
let rec mem x = function
Empty -> false
| Node2(t1,d1,t2) ->
let c = cmp x d1 in
c = 0 || mem x (if c < 0 then t1 else t2)
| Node3(t1,d1,t2,d2,t3) ->
let c = cmp x d1 in
c = 0 ||
if c < 0 then mem x t1 else
let c = cmp x d2 in
c = 0 || mem x (if c < 0 then t2 else t3)
| Node4(t1,d1,t2,d2,t3,d3,t4) ->
let c = cmp x d2 in
c = 0 ||
if c < 0 then
let c = cmp x d1 in
c = 0 || mem x (if c < 0 then t1 else t2)
else
let c = cmp x d3 in
c = 0 || mem x (if c < 0 then t3 else t4)
| Node5 _ ->
assert false
let bNode2 t1 d1 t2 = 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,Node3(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,Node3(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 = 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,Node3(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,d31,t32))
| Node3(t11,d11,t12,d12,t13), Node5(t21,d21,t22,d22,t23,d23,t24,d24,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,d31,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,Node3(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,d34,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,d33,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), Node5(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),d32,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 =
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,t42))
| 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,t42,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,Node3(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,d31,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,d31,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,d31,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,d31,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,Node3(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,d34,t35),d3,t4)
| _, _, Node5(t31,d31,t32,d32,t33,d33,t34,d34,t35), Node2(t41,d41,t42) ->
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,d33,t34,d34,t35),d3,t4)
| _, _, Node5(t31,d31,t32,d32,t33,d33,t34,d34,t35), Node3(t41,d41,t42,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), Node5(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),d32,Node3(t33,d33,t34,d34,t35),d3,t4)
| _, _, Node2(t31,d31,t32), Node5(t41,d41,t42,d42,t43,d43,t44,d44,t45)->
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,t44,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,d33,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,t45))
| Node3(t11,d11,t12,d12,t13), 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(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,t44,d44,t45))
| _, _, Node4(t31,d31,t32,d32,t33,d33,t34), Node5(t41,d41,t42,d42,t43,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 = 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 =
let rec fn s = match s with
Empty -> Node2(Empty,x,Empty)
| Node2(t1,d1,t2) ->
let c = cmp x d1 in
if c = 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 = cmp x d1 in
if c = 0 then s else
if c < 0 then bNode3 (fn t1) d1 t2 d2 t3 else
let c = cmp x d2 in
if c = 0 then s else
if c < 0 then bNode3 t1 d1 (fn t2) d2 t3
else bNode3 t1 d1 t2 d2 (fn t3)
| Node4(t1,d1,t2,d2,t3,d3,t4) ->
let c = cmp x d2 in
if c = 0 then s else
if c < 0 then
let c = cmp x d1 in
if c = 0 then s else
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 = cmp x d3 in
if c = 0 then s else
if c < 0 then bNode4 t1 d1 t2 d2 (fn t3) d3 t4
else bNode4 t1 d1 t2 d2 t3 d3 (fn t4)
| Node5 _ ->
assert false
in
treat_root (fn s)
let rec cardinal = 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 =
match t with
Empty -> 0
| Node2(t1,_,t2) ->
let h1 = test_height t1 in
let h2 = test_height t2 in
assert (h1 = h2);
h1 + 1
| Node3(t1,_,t2,_,t3) ->
let h1 = test_height t1 in
let h2 = test_height t2 in
let h3 = test_height t3 in
assert (h1 = h2);
assert (h1 = h3);
h1 + 1
| Node4(t1,_,t2,_,t3,_,t4) ->
let h1 = test_height t1 in
let h2 = test_height t2 in
let h3 = test_height t3 in
let h4 = test_height t4 in
assert (h1 = h2);
assert (h1 = h3);
assert (h1 = h4);
h1 + 1
| Node5 _ -> assert false
end
[-- Attachment #1.3: test234tree.ml --]
[-- Type: text/plain, Size: 6640 bytes --]
module Int = struct
type t = int
let compare = compare
end
module Set1 = Set234.Make(Int)
let create1 size max =
let rec fn acc remain =
if remain = 0 then acc
else
let x = Random.int max in
fn (Set1.add x acc) (remain - 1)
in
fn Set1.empty size
module Set2 = Set.Make(Int)
let create2 size max =
let rec fn acc remain =
if remain = 0 then acc
else
let x = Random.int max in
fn (Set2.add x acc) (remain - 1)
in
fn Set2.empty size
let create12 size max =
let rec fn acc acc' remain =
if remain = 0 then acc, acc'
else
let x = 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 =
let rec fn acc remain =
if remain = 0 then acc
else
let x = remain in
fn (Set1.add x acc) (remain - 1)
in
fn Set1.empty size
let ocreate2 size max =
let rec fn acc remain =
if remain = 0 then acc
else
let x = remain in
fn (Set2.add x acc) (remain - 1)
in
fn Set2.empty size
let ocreate12 size max =
let rec fn acc acc' remain =
if remain = 0 then acc, acc'
else
let x = 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 =
let rec fn acc remain =
if remain = 0 then acc
else
let x = 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 =
let rec fn acc remain =
if remain = 0 then acc
else
let x = Random.int max in
fn (if Set2.mem x t then acc+1 else acc) (remain - 1)
in
fn 0 size
let t1,t2 =
let n = int_of_string Sys.argv.(1) in
create12 n (n*3)
let h = Set1.test_height t1
let _ =
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 =
let n = int_of_string Sys.argv.(1) in
ocreate12 n (n*3)
let h = Set1.test_height t1
let _ =
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 =
let {Unix.tms_utime = ut;Unix.tms_stime = st} = Unix.times () in
let r = f x in
let {Unix.tms_utime = ut';Unix.tms_stime = st'} = Unix.times () in
Printf.printf "%s: %.2fs\n" s ((ut' -. ut) +. (st' -. st));
flush stdout;
ignore r
let _ =
print_string "construction of random tree with 200000 interger less then 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 = 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 = 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 = 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 then 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 = ocreate12 100000 1000000 in
print_string "search 10^6 times in tree of size 100000 (ordered insertion)"; 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 = ocreate12 500000 1000000 in
print_string "search 10^6 times in tree of size 500000 (ordered insertion)"; 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 = ocreate12 2000000 1000000 in
print_string "search 10^6 times in tree of size 2000000 (ordered insertion)"; 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
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]
next prev parent reply other threads:[~2008-01-30 17:50 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-01-25 1:32 Christophe Raffalli
2008-01-25 2:28 ` [Caml-list] " Jon Harrop
2008-01-25 18:12 ` Christophe Raffalli
2008-01-25 2:31 ` Jon Harrop
2008-01-30 17:50 ` Christophe Raffalli [this message]
2008-01-30 18:10 ` Edgar Friendly
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=47A0B8E7.5010308@univ-savoie.fr \
--to=christophe.raffalli@univ-savoie.fr \
--cc=caml-list@inria.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox