Java example source code file (BinaryTreeTraverserBenchmark.java)

This example Java source code file (BinaryTreeTraverserBenchmark.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

all_right, beforeexperiment, binary_viewer, binarynode, binarytreetraverser, iterable, optional, override, param, pre_order, random, topology, traversal, treetraverser, util

The BinaryTreeTraverserBenchmark.java Java example source code

/*
 * Copyright (C) 2012 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.collect;

import com.google.caliper.BeforeExperiment;
import com.google.caliper.Benchmark;
import com.google.caliper.Param;
import com.google.common.base.Optional;
import com.google.common.primitives.Ints;

import java.util.List;
import java.util.Random;

/**
 * Benchmarks for the {@code TreeTraverser} and optimized {@code BinaryTreeTraverser} operations on
 * binary trees.
 *
 * @author Louis Wasserman
 */
public class BinaryTreeTraverserBenchmark {
  private static class BinaryNode {
    final int x;
    final Optional<BinaryNode> left;
    final Optional<BinaryNode> right;

    BinaryNode(int x, Optional<BinaryNode> left, Optional right) {
      this.x = x;
      this.left = left;
      this.right = right;
    }
  }

  enum Topology {
    BALANCED {
      @Override
      Optional<BinaryNode> createTree(int size, Random rng) {
        if (size == 0) {
          return Optional.absent();
        } else {
          int leftChildSize = (size - 1) / 2;
          int rightChildSize = size - 1 - leftChildSize;
          return Optional.of(new BinaryNode(
              rng.nextInt(), createTree(leftChildSize, rng), createTree(rightChildSize, rng)));
        }
      }
    },
    ALL_LEFT {
      @Override
      Optional<BinaryNode> createTree(int size, Random rng) {
        Optional<BinaryNode> root = Optional.absent();
        for (int i = 0; i < size; i++) {
          root = Optional.of(new BinaryNode(rng.nextInt(), root, Optional.<BinaryNode>absent()));
        }
        return root;
      }
    },
    ALL_RIGHT {
      @Override
      Optional<BinaryNode> createTree(int size, Random rng) {
        Optional<BinaryNode> root = Optional.absent();
        for (int i = 0; i < size; i++) {
          root = Optional.of(new BinaryNode(rng.nextInt(), Optional.<BinaryNode>absent(), root));
        }
        return root;
      }
    },
    RANDOM {
      /**
       * Generates a tree with topology selected uniformly at random from the topologies of binary
       * trees of the specified size.
       */
      @Override
      Optional<BinaryNode> createTree(int size, Random rng) {
        int[] keys = new int[size];
        for (int i = 0; i < size; i++) {
          keys[i] = rng.nextInt();
        }
        return createTreap(Ints.asList(keys));
      }

      // See http://en.wikipedia.org/wiki/Treap for details on the algorithm.
      private Optional<BinaryNode> createTreap(List keys) {
        if (keys.isEmpty()) {
          return Optional.absent();
        }
        int minIndex = 0;
        for (int i = 1; i < keys.size(); i++) {
          if (keys.get(i) < keys.get(minIndex)) {
            minIndex = i;
          }
        }
        Optional<BinaryNode> leftChild = createTreap(keys.subList(0, minIndex));
        Optional<BinaryNode> rightChild = createTreap(keys.subList(minIndex + 1, keys.size()));
        return Optional.of(new BinaryNode(keys.get(minIndex), leftChild, rightChild));
      }
    };

    abstract Optional<BinaryNode> createTree(int size, Random rng);
  }

  private static final BinaryTreeTraverser<BinaryNode> BINARY_VIEWER =
      new BinaryTreeTraverser<BinaryNode>() {

    @Override
    public Optional<BinaryNode> leftChild(BinaryNode node) {
      return node.left;
    }

    @Override
    public Optional<BinaryNode> rightChild(BinaryNode node) {
      return node.right;
    }
  };

  private static final TreeTraverser<BinaryNode> VIEWER = new TreeTraverser() {
    @Override
    public Iterable<BinaryNode> children(BinaryNode root) {
      return BINARY_VIEWER.children(root);
    }
  };

  enum Traversal {
    PRE_ORDER {
      @Override
      <T> Iterable view(T root, TreeTraverser viewer) {
        return viewer.preOrderTraversal(root);
      }
    },
    POST_ORDER {
      @Override
      <T> Iterable view(T root, TreeTraverser viewer) {
        return viewer.postOrderTraversal(root);
      }
    },
    BREADTH_FIRST {
      @Override
      <T> Iterable view(T root, TreeTraverser viewer) {
        return viewer.breadthFirstTraversal(root);
      }
    };

    abstract <T> Iterable view(T root, TreeTraverser viewer);
  }

  private Iterable<BinaryNode> view;

  @Param
  Topology topology;

  @Param({"1", "100", "10000", "1000000"})
  int size;

  @Param
  Traversal traversal;

  @Param
  boolean useBinaryTraverser;

  @Param({"1234"})
  SpecialRandom rng;

  @BeforeExperiment
  void setUp() {
    this.view = traversal.view(
        topology.createTree(size, rng).get(),
        useBinaryTraverser ? BINARY_VIEWER : VIEWER);
  }

  @Benchmark int traversal(int reps) {
    int tmp = 0;

    for (int i = 0; i < reps; i++) {
      for (BinaryNode node : view) {
        tmp += node.x;
      }
    }
    return tmp;
  }
}