The Computer Language
Benchmarks Game

binary-trees Java #4 program

source code

/* The Computer Language Benchmarks Game
 * http://benchmarksgame.alioth.debian.org/
 *
 * contributed by Diogo Lima
 * *reset*
*/

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class binarytrees {

    /**
     * Internal class for structuring nodes and childs
     */
    private static class TreeNode {

        private TreeNode left;
        private TreeNode right;

        private TreeNode(TreeNode i_left, 
                         TreeNode i_right) {
            this.left = i_left;
            this.right = i_right;
        }

        public static TreeNode createNode(int i_depth) {
            // Create bottom node with empty child nodes => depth = 0
            TreeNode bottomTree = new TreeNode(null, null);
            return i_depth == 0 ? 
                       bottomTree : 
                       createNode(i_depth,
                                  bottomTree);
        }

        private static TreeNode createNode(int i_depth, 
                                           TreeNode i_accumulator) {
            TreeNode accumulator = i_accumulator;
            if (i_depth > 0) {
                final int depth = i_depth - 1;
                accumulator.left = createNode(depth);
                accumulator.right = createNode(depth);
            }
            return accumulator;
        }

        public final int checkNode() {
            return left == null ? 
                       1 : 
                       left.checkNode() + right.checkNode() + 1;
        }
    }


    public static void main(String[] args) {
        int n = args.length > 0 ? Integer.parseInt(args[0]) : 0;

        // Make the main process parallel to improve recursive createNode
        int proc = Runtime.getRuntime().availableProcessors() * 2;
        ExecutorService service = Executors.newFixedThreadPool(proc);
        service.execute(() -> runBenchmark(n));
        service.shutdown();
        try {
            service.awaitTermination(120L, TimeUnit.SECONDS);
        } catch (InterruptedException e) {
        }
    }

    // Do the real work with createNode
    private static void runBenchmark(int n) {
        final int minimumDepth = 4;
        final int maximumDepth = Math.max(minimumDepth + 2, n);
        final int stretchDepth = maximumDepth + 1;

        TreeNode node = TreeNode.createNode(stretchDepth);
        final int checkNode = node.checkNode();

        System.out.println("stretch tree of depth " 
                                + (maximumDepth + 1) 
                                + "\t check: " 
                                + checkNode);

        TreeNode longLivedTree = TreeNode.createNode(maximumDepth);
        for (int depth = minimumDepth; depth <= maximumDepth; depth += 2) {
            final int iterations = 1 << (maximumDepth - depth + minimumDepth);
            int check = 0;

            for (int i = 1; i <= iterations; i++) {
                check += TreeNode.createNode(depth).checkNode();
            }
            System.out.println(iterations
                                + "\t trees of depth " 
                                + depth 
                                + "\t check: "
                                + check);
        }
        System.out.println("long lived tree of depth " 
                           + maximumDepth 
                           + "\t check: " 
                           + longLivedTree.checkNode());
    }
}
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
java version "1.8.0_121"
Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.121-b13, mixed mode)


Sat, 25 Mar 2017 01:06:06 GMT

MAKE:
mv binarytrees.java-4.java binarytrees.java
/usr/local/src/jdk1.8.0_121/bin/javac -d .  binarytrees.java
0.86s to complete and log all make actions

COMMAND LINE:
/usr/local/src/jdk1.8.0_121/bin/java   binarytrees 21

PROGRAM OUTPUT:
stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303