Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <stdlib.h>
#include <iostream>
#include <memory>
class Tree {
std::unique_ptr<Tree> left;
std::unique_ptr<Tree> right;
public:
Tree(int depth) {
if (depth == 0) {
return;
}
left = std::make_unique<Tree>(depth - 1);
right = std::make_unique<Tree>(depth - 1);
}
int count() const {
return !left ? 1 : left->count() + 1 + right->count();
}
};
int main(int argc, char *argv[]) {
int min_depth = 4;
int max_depth = argc == 2 ? atoi(argv[1]) : 10;
max_depth = std::max(max_depth, min_depth + 2);
int stretch_depth = max_depth + 1;
{
Tree tree{stretch_depth};
std::cout << stretch_depth << " " << tree.count() << std::endl;
}
Tree long_lived{max_depth};
for (int depth = min_depth; depth <= max_depth; depth += 2) {
int iterations = 16 << (max_depth - depth);
int count = 0;
for (int i = 0; i < iterations; ++i) {
count += Tree{depth}.count();
}
std::cout << iterations << " " << depth << " " << count << std::endl;
}
std::cout << max_depth << " " << long_lived.count() << std::endl;
}
class Tree {
private Tree left;
private Tree right;
Tree(int depth) {
if (depth == 0) {
return;
}
left = new Tree(depth - 1);
right = new Tree(depth - 1);
}
public int count() {
return left == null ? 1 : left.count() + 1 + right.count();
}
}
public class binarytrees {
public static void main(String[] args) {
int minDepth = 4;
int maxDepth = args.length == 1 ? Integer.parseInt(args[0]) : 10;
maxDepth = Math.max(maxDepth, minDepth + 2);
int stretchDepth = maxDepth + 1;
{
Tree tree = new Tree(stretchDepth);
System.out.println(stretchDepth + " " + tree.count());
}
Tree longLived = new Tree(maxDepth);
for (int depth = minDepth; depth <= maxDepth; depth += 2) {
int iterations = 16 << (maxDepth - depth);
int count = 0;
for (int i = 0; i < iterations; i++) {
count += new Tree(depth).count();
};
System.out.println(iterations + " " + depth + " " + count);
};
System.out.println(maxDepth + " " + longLived.count());
}
}
@Veedrac

This comment has been minimized.

Copy link
Owner Author

@Veedrac Veedrac commented Jun 3, 2017

$ javac binarytrees.java
$ time java binarytrees 22
23 16777215
4194304 4 130023424
1048576 6 133169152
262144 8 133955584
65536 10 134152192
16384 12 134201344
4096 14 134213632
1024 16 134216704
256 18 134217472
64 20 134217664
16 22 134217712
22 8388607
java binarytrees 22  42.98s user 0.92s system 343% cpu 12.761 total
$ g++ -O3 -std=c++14 binarytrees_cpp.cpp -o binarytrees_cpp
$ time ./binarytrees_cpp 22
23 16777215
4194304 4 130023424
1048576 6 133169152
262144 8 133955584
65536 10 134152192
16384 12 134201344
4096 14 134213632
1024 16 134216704
256 18 134217472
64 20 134217664
16 22 134217712
22 8388607
./binarytrees_cpp 22  42.26s user 0.10s system 99% cpu 42.357 total
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment