BinaryTreeTraverserBenchmark.java

/*
 * 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} 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<BinaryNode> 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<Integer> 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 TreeTraverser<BinaryNode> VIEWER =
      new TreeTraverser<BinaryNode>() {
        @Override
        public Iterable<BinaryNode> children(BinaryNode root) {
          return Optional.presentInstances(ImmutableList.of(root.left, root.right));
        }
      };

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

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

  private Iterable<BinaryNode> view;

  @Param Topology topology;

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

  @Param Traversal traversal;

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

  @BeforeExperiment
  void setUp() {
    this.view = traversal.view(topology.createTree(size, rng).get(), 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;
  }
}