Skip to content

Instantly share code, notes, and snippets.

@quinnj

quinnj/gist:6908779

Created October 9, 2013 21:30
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save quinnj/6908779 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save quinnj/6908779 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.txt
_
_ _ _(_)_ | A fresh approach to technical computing
(_) | (_) (_) | Documentation: http://docs.julialang.org
_ _ _| |_ __ _ | Type "help()" to list help topics
| | | | | | |/ _` | |
| | |_| | | | (_| | | Version 0.2.0-prerelease+3952
_/ |\__'_|_|_|\__'_| | Commit d0c2058 2013-10-06 19:08:09 UTC
|__/ | x86_64-w64-mingw32
julia> abstract BTree
.......type Empty <: BTree
.......end
.......type Node <: BTree
....... info::Int
....... left::BTree
....... right::BTree
.......end
.......const min_depth = 4
.......function make(val, d)
....... if d > 0
....... Node(val, make(2*val-1, d-1), make(2*val, d-1))
....... else
....... Node(val, Empty(), Empty())
....... end
.......end
.......check(t::Empty) = 0
.......check(t::Node) = t.info + check(t.left) - check(t.right)
.......function binary_trees(N::Int=10)
....... max_depth = N
....... stretch_depth = max_depth + 1
....... c = check(make(0, stretch_depth))
.......
....... long_lived_tree = make(0, max_depth)
....... d = min_depth
....... for i = 0:div(max_depth - d, 2)
....... niter = 1 << (max_depth - d + min_depth)
....... c = 0
....... for j = 1:niter
....... c += check(make(i, d)) + check(make(-i, d))
....... end
....... d += 2
....... end
.......end
binary_trees (generic function with 2 methods)
julia> @profile binary_trees(17)
julia> Profile.print()
1 multi.jl; event_loop; line: 1536
1 stream.jl; process_events; line: 508
810 none; check; line: 19
1 none; check; line: 19
2 none; check; line: 18
1 none; check; line: 19
4 none; check; line: 19
7 none; check; line: 19
5 none; check; line: 19
+14 5 none; check; line: 19
+35 5 none; check; line: 19
+43 1 none; check; line: 19
1 none; check; line: 19
32 none; check; line: 19
1 none; check; line: 19
28 none; check; line: 19
+2 2 none; check; line: 19
+5 1 none; check; line: 19
+15 9 none; check; line: 19
+23 1 none; check; line: 18
+24 2 none; check; line: 18
606 none; check; line: 19
1 none; check; line: 19
1 none; check; line: 19
+2 480 none; check; line: 19
+13 2 none; check; line: 19
+14 2 none; check; line: 19
+15 1 none; check; line: 19
+23 315 none; check; line: 19
+31 1 none; check; line: 18
+33 2 none; check; line: 19
+36 1 none; check; line: 19
+44 153 none; check; line: 19
+54 2 none; check; line: 19
+65 45 none; check; line: 19
+74 1 none; check; line: 18
+86 29 none; check; line: 19
+94 1 none; check; line: 19
+107 16 none; check; line: 19
+128 1 none; check; line: 19
2 none; make; line: 12
12 none; make; line: 13
12 none; make; line: 15
1 none; make; line: 15
86 profile.jl; anonymous; line: 14
1 none; binary_trees; line: 23
85 none; binary_trees; line: 32
1 none; make; line: 12
19 none; make; line: 13
18 none; make; line: 13
+8 1 none; make; line: 15
+9 17 none; check; line: 19
+13 17 none; make; line: 13
+22 2 none; make; line: 12
+22 2 none; make; line: 13
+22 13 none; make; line: 15
1 none; make; line: 15
57 none; check; line: 19
+13 51 none; check; line: 19
+29 32 none; make; line: 13
+31 32 none; check; line: 19
+52 22 none; check; line: 19
+73 16 none; check; line: 19
+94 14 none; check; line: 19
+115 11 none; check; line: 19
+136 11 none; check; line: 19
+157 10 none; check; line: 19
+178 9 none; check; line: 19
+199 9 none; check; line: 19
+220 9 none; check; line: 19
+231 1 none; check; line: 19
+241 6 none; check; line: 19
+262 2 none; check; line: 19
+271 1 none; check; line: 18
+31 14 none; check; line: 19
+39 1 none; check; line: 19
+46 4 none; check; line: 19
+67 4 none; check; line: 19
+88 3 none; check; line: 19
+14 1 none; check; line: 19
+20 1 none; check; line: 19
362 none; check; line: 19
1 none; make; line: 12
47 none; make; line: 13
4 none; make; line: 13
1 none; make; line: 12
1 none; make; line: 12
40 none; make; line: 15
34 none; make; line: 15
1 none; check; line: 19
7 none; check; line: 19
1 none; check; line: 18
2 none; check; line: 18
1 none; check; line: 18
3 none; check; line: 19
13 none; check; line: 19
2 none; check; line: 19
+12 2 none; check; line: 19
+33 2 none; check; line: 19
9 none; check; line: 19
+15 9 none; check; line: 19
+36 7 none; check; line: 19
+46 1 none; check; line: 19
+57 5 none; check; line: 19
1 none; check; line: 19
1 none; check; line: 19
+16 1 none; check; line: 19
+37 1 none; check; line: 19
+58 1 none; check; line: 19
158 none; check; line: 19
1 none; check; line: 19
106 none; make; line: 13
+3 106 none; check; line: 19
+24 106 none; check; line: 19
+45 106 none; check; line: 19
+66 105 none; check; line: 19
+87 105 none; check; line: 19
+108 101 none; check; line: 19
+129 99 none; check; line: 19
+150 92 none; check; line: 19
+161 1 none; check; line: 19
+171 88 none; check; line: 19
+192 76 none; check; line: 19
+213 33 none; check; line: 19
+221 1 none; check; line: 18
+222 1 none; check; line: 18
4 none; check; line: 19
+21 4 none; check; line: 19
+42 4 none; check; line: 19
+63 2 none; check; line: 19
+3 34 none; check; line: 19
+11 2 none; check; line: 18
+24 14 none; check; line: 19
+45 12 none; check; line: 19
+55 1 none; check; line: 19
+66 9 none; check; line: 19
+87 2 none; check; line: 19
+108 2 none; check; line: 19
+129 1 none; check; line: 19
+150 1 none; check; line: 19
9 none; check; line: 19
+4 6 none; check; line: 19
+25 4 none; check; line: 19
+46 4 none; check; line: 19
+67 4 none; check; line: 19
+88 2 none; check; line: 19
+109 2 none; check; line: 19
+130 2 none; check; line: 19
+143 1 none; check; line: 19
+151 1 none; check; line: 19
3 none; make; line: 12
77 none; make; line: 13
2 none; check; line: 19
2 none; check; line: 19
+5 2 none; check; line: 19
+22 1 none; make; line: 13
+26 1 none; check; line: 19
+47 1 none; check; line: 19
+68 1 none; check; line: 19
+89 1 none; check; line: 19
+110 1 none; check; line: 19
+131 1 none; check; line: 19
+26 1 none; check; line: 19
+47 1 none; check; line: 19
+68 1 none; check; line: 19
+89 1 none; check; line: 19
+110 1 none; check; line: 19
+131 1 none; check; line: 19
+152 1 none; check; line: 19
+173 1 none; check; line: 19
+194 1 none; check; line: 19
1 none; make; line: 12
1 none; make; line: 15
70 none; make; line: 13
1 none; make; line: 12
2 none; make; line: 12
37 none; make; line: 13
1 none; make; line: 12
1 none; make; line: 12
2 none; make; line: 13
1 none; make; line: 12
33 none; make; line: 15
27 none; make; line: 15
2 none; make; line: 13
+1 2 none; check; line: 19
+3 2 none; make; line: 13
+17 1 none; make; line: 13
+31 1 none; make; line: 13
+42 1 none; make; line: 15
1 none; make; line: 15
8 none; make; line: 15
52 none; check; line: 19
14 none; make; line: 15
1 none; check; line: 18
1 none; check; line: 19
4 none; check; line: 19
1 none; check; line: 18
1 none; make; line: 12
122 none; make; line: 13
1 none; make; line: 12
1 none; make; line: 13
1 none; make; line: 15
41 none; make; line: 15
79 none; make; line: 13
20 none; make; line: 15
31 none; make; line: 13
1 none; make; line: 15
3 none; make; line: 13
1 none; make; line: 12
27 none; make; line: 15
23 none; make; line: 15
5 none; check; line: 19
5 none; make; line: 13
5 none; make; line: 15
95 none; check; line: 19
7 none; check; line: 19
1 none; check; line: 19
+11 1 none; check; line: 19
+32 1 none; check; line: 19
+53 1 none; check; line: 19
+74 1 none; check; line: 19
+95 1 none; check; line: 19
6 none; check; line: 19
1 none; check; line: 19
2 none; check; line: 19
1 none; check; line: 19
31 none; check; line: 19
1 none; check; line: 19
+5 21 none; check; line: 19
+26 6 none; check; line: 19
+47 4 none; check; line: 19
+68 4 none; check; line: 19
3 none; check; line: 19
48 none; make; line: 13
1 none; make; line: 12
3 none; make; line: 15
6 none; make; line: 12
2 none; make; line: 12
1 none; make; line: 12
1 none; make; line: 12
2 none; make; line: 12
1 none; check; line: 19
1 none; make; line: 13
1 none; make; line: 12
3 none; make; line: 12
22 none; make; line: 13
4 none; make; line: 12
1 none; make; line: 15
1 none; make; line: 12
1 none; make; line: 15
2 none; make; line: 12
1 none; make; line: 15
2 none; make; line: 12
1 none; check; line: 19
1 none; make; line: 13
1 none; make; line: 15
6 none; make; line: 13
1 none; make; line: 12
1 none; make; line: 12
1 none; make; line: 15
6 none; make; line: 15
15 none; make; line: 15
183 none; check; line: 19
4 none; make; line: 15
1 none; make; line: 12
6 none; make; line: 13
6 none; make; line: 15
3 none; check; line: 19
1 none; check; line: 19
2 none; check; line: 19
2 none; check; line: 19
+19 2 none; check; line: 19
109 none; check; line: 19
+6 65 none; check; line: 19
+17 1 none; check; line: 19
+27 43 none; check; line: 19
+35 1 none; check; line: 18
+48 5 none; check; line: 19
+69 3 none; check; line: 19
+77 1 none; check; line: 18
+90 1 none; check; line: 19
+101 1 none; check; line: 19
13 none; make; line: 12
295 none; make; line: 15
28 none; check; line: 19
24 none; check; line: 19
+7 20 none; check; line: 19
+28 20 none; check; line: 19
+49 19 none; check; line: 19
+70 16 none; check; line: 19
+91 11 none; check; line: 19
54 none; make; line: 13
2 none; make; line: 13
52 none; make; line: 13
3 none; make; line: 12
22 none; make; line: 13
1 none; make; line: 12
1 none; make; line: 13
20 none; make; line: 15
27 none; make; line: 15
1 none; check; line: 19
1 none; check; line: 19
+8 1 none; check; line: 19
+29 1 none; check; line: 19
+50 1 none; check; line: 19
+71 1 none; check; line: 19
+92 1 none; check; line: 19
+113 1 none; check; line: 19
+134 1 none; check; line: 19
1 none; make; line: 12
258 none; make; line: 15
23 none; check; line: 19
1 none; make; line: 12
9 none; make; line: 13
8 none; check; line: 19
8 none; make; line: 13
1 none; make; line: 12
1 none; make; line: 13
6 none; make; line: 15
1 none; make; line: 13
1 none; check; line: 19
1 none; make; line: 13
+5 1 none; make; line: 15
1 none; make; line: 15
2 none; make; line: 12
73 none; make; line: 13
5 none; make; line: 13
68 none; make; line: 13
1 none; make; line: 12
25 none; make; line: 13
+3 1 none; make; line: 13
+3 23 none; make; line: 15
41 none; make; line: 15
1 none; check; line: 19
1 none; make; line: 13
+6 1 none; make; line: 13
10 none; make; line: 15
32 none; make; line: 13
32 none; make; line: 13
1 none; make; line: 12
4 none; make; line: 13
1 none; make; line: 12
+4 1 none; make; line: 13
+5 1 none; make; line: 12
+4 2 none; make; line: 15
27 none; make; line: 15
1 none; make; line: 13
+6 1 none; make; line: 12
+123 1 none; make; line: 13
+137 1 none; make; line: 13
+149 1 none; check; line: 19
+151 1 none; make; line: 13
+160 1 none; make; line: 15
+1099 1 none; make; line: 13
+1108 1 none; make; line: 15
+18384 1 stream.jl; write!; line: 667
***Repl Closed***
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment