Mercurial > repos > rhope
comparison binary_trees.rhope @ 93:09831a71a4bc
Added binary trees benchmark
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Mon, 02 Aug 2010 00:59:27 -0400 |
parents | |
children | f4fd8962c385 |
comparison
equal
deleted
inserted
replaced
92:e73a93fb5de1 | 93:09831a71a4bc |
---|---|
1 | |
2 | |
3 Blueprint Tree | |
4 { | |
5 Left | |
6 Right | |
7 Item | |
8 } | |
9 | |
10 Blueprint Empty | |
11 { | |
12 | |
13 } | |
14 | |
15 Make Tree[item,depth:out] | |
16 { | |
17 If[depth] | |
18 { | |
19 dbl <- [item]+[item] | |
20 ndepth <- [depth]-[1] | |
21 out <- [[[Build[Tree()]]Left <<[ Make Tree[[dbl]-[1], ndepth] ]]Right <<[ Make Tree[dbl, ndepth] ]]Item <<[item] | |
22 }{ | |
23 out <- [[[Build[Tree()]]Left <<[Build[Empty()]]]Right <<[Build[Empty()]]]Item <<[item] | |
24 } | |
25 } | |
26 | |
27 Check Tree@Tree[node:out] | |
28 { | |
29 out <- [[[node]Item >>]+[Check Tree[[node]Left >>]]] - [Check Tree[[node]Right >>]] | |
30 } | |
31 | |
32 Check Tree@Empty[node:out] | |
33 { | |
34 out <- 0 | |
35 } | |
36 | |
37 Step[num, depth: out] | |
38 { | |
39 out <- [Check Tree[Make Tree[num, depth]]] + [Check Tree[Make Tree[[0]-[num], depth]]] | |
40 } | |
41 | |
42 Test Size[sum, current,iterations,depth:out] | |
43 { | |
44 nsum <- [sum]+[Step[current, depth]] | |
45 If[[current]=[iterations]] | |
46 { | |
47 out <- Val[nsum] | |
48 }{ | |
49 out <- Test Size[nsum, [current]+[1], iterations, depth] | |
50 } | |
51 } | |
52 | |
53 Test Sizes[current,max,iterations:out] | |
54 { | |
55 sum <- Test Size[0, 1, iterations, current] | |
56 { | |
57 Print[[iterations]*[2]] | |
58 { Print["trees of depth"] | |
59 { Print[current] | |
60 { Print["check"] | |
61 { Print[sum] | |
62 { | |
63 If[[current]=[max]] | |
64 { | |
65 out <- 1 | |
66 }{ | |
67 out <- Test Sizes[[current]+[2], max, [iterations]/[4]] | |
68 } | |
69 }}}}} | |
70 } | |
71 } | |
72 | |
73 Main[] | |
74 { | |
75 min depth <- 4 | |
76 max depth <- 16 | |
77 Print["stretch tree of depth 17 check:"] | |
78 { Print[Check Tree[Make Tree[0, 17]]] | |
79 { long lived <- Make Tree[0, max depth] | |
80 { Test Sizes[min depth, max depth, [1]LShift[max depth]] | |
81 { Print["long lived tree of depth 16 check:"] | |
82 { Print[Check Tree[long lived]] }}}}} | |
83 } | |
84 |