blob: 6de000caea271d16240377b0196a8d5b2c314ac5 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
// Adapted from binary-trees C# .NET Core #2 program
// http://benchmarksgame.alioth.debian.org/u64q/program.php?test=binarytrees&lang=csharpcore&id=2
// Best-scoring single-threaded C# .NET Core version as of 2017-09-01
/* The Computer Language Benchmarks Game
http://benchmarksgame.alioth.debian.org/
contributed by Marek Safar
*reset*
*/
using System;
namespace BenchmarksGame
{
class BinaryTrees
{
const int minDepth = 4;
public static void Main(String[] args)
{
int n = 0;
if (args.Length > 0) n = Int32.Parse(args[0]);
int maxDepth = Math.Max(minDepth + 2, n);
int stretchDepth = maxDepth + 1;
int check = (TreeNode.bottomUpTree(stretchDepth)).itemCheck();
Console.WriteLine("stretch tree of depth {0}\t check: {1}", stretchDepth, check);
TreeNode longLivedTree = TreeNode.bottomUpTree(maxDepth);
for (int depth = minDepth; depth <= maxDepth; depth += 2)
{
int iterations = 1 << (maxDepth - depth + minDepth);
check = 0;
for (int i = 1; i <= iterations; i++)
{
check += (TreeNode.bottomUpTree(depth)).itemCheck();
}
Console.WriteLine("{0}\t trees of depth {1}\t check: {2}",
iterations, depth, check);
}
Console.WriteLine("long lived tree of depth {0}\t check: {1}",
maxDepth, longLivedTree.itemCheck());
}
struct TreeNode
{
class Next
{
public TreeNode left, right;
}
private Next next;
internal static TreeNode bottomUpTree(int depth)
{
if (depth > 0)
{
return new TreeNode(
bottomUpTree(depth - 1)
, bottomUpTree(depth - 1)
);
}
else
{
return new TreeNode();
}
}
TreeNode(TreeNode left, TreeNode right)
{
this.next = new Next();
this.next.left = left;
this.next.right = right;
}
internal int itemCheck()
{
// if necessary deallocate here
if (next == null) return 1;
else return 1 + next.left.itemCheck() + next.right.itemCheck();
}
}
}
}
|
