1 /* 2 * Copyright (C) 2012 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15 package com.google.common.collect; 16 17 import com.google.caliper.BeforeExperiment; 18 import com.google.caliper.Benchmark; 19 import com.google.caliper.Param; 20 import com.google.common.base.Optional; 21 import com.google.common.primitives.Ints; 22 import java.util.List; 23 import java.util.Random; 24 25 /** 26 * Benchmarks for the {@code TreeTraverser} operations on binary trees. 27 * 28 * @author Louis Wasserman 29 */ 30 public class BinaryTreeTraverserBenchmark { 31 private static class BinaryNode { 32 final int x; 33 final Optional<BinaryNode> left; 34 final Optional<BinaryNode> right; 35 BinaryNode(int x, Optional<BinaryNode> left, Optional<BinaryNode> right)36 BinaryNode(int x, Optional<BinaryNode> left, Optional<BinaryNode> right) { 37 this.x = x; 38 this.left = left; 39 this.right = right; 40 } 41 } 42 43 enum Topology { 44 BALANCED { 45 @Override createTree(int size, Random rng)46 Optional<BinaryNode> createTree(int size, Random rng) { 47 if (size == 0) { 48 return Optional.absent(); 49 } else { 50 int leftChildSize = (size - 1) / 2; 51 int rightChildSize = size - 1 - leftChildSize; 52 return Optional.of( 53 new BinaryNode( 54 rng.nextInt(), createTree(leftChildSize, rng), createTree(rightChildSize, rng))); 55 } 56 } 57 }, 58 ALL_LEFT { 59 @Override createTree(int size, Random rng)60 Optional<BinaryNode> createTree(int size, Random rng) { 61 Optional<BinaryNode> root = Optional.absent(); 62 for (int i = 0; i < size; i++) { 63 root = Optional.of(new BinaryNode(rng.nextInt(), root, Optional.<BinaryNode>absent())); 64 } 65 return root; 66 } 67 }, 68 ALL_RIGHT { 69 @Override createTree(int size, Random rng)70 Optional<BinaryNode> createTree(int size, Random rng) { 71 Optional<BinaryNode> root = Optional.absent(); 72 for (int i = 0; i < size; i++) { 73 root = Optional.of(new BinaryNode(rng.nextInt(), Optional.<BinaryNode>absent(), root)); 74 } 75 return root; 76 } 77 }, 78 RANDOM { 79 /** 80 * Generates a tree with topology selected uniformly at random from the topologies of binary 81 * trees of the specified size. 82 */ 83 @Override createTree(int size, Random rng)84 Optional<BinaryNode> createTree(int size, Random rng) { 85 int[] keys = new int[size]; 86 for (int i = 0; i < size; i++) { 87 keys[i] = rng.nextInt(); 88 } 89 return createTreap(Ints.asList(keys)); 90 } 91 92 // See http://en.wikipedia.org/wiki/Treap for details on the algorithm. createTreap(List<Integer> keys)93 private Optional<BinaryNode> createTreap(List<Integer> keys) { 94 if (keys.isEmpty()) { 95 return Optional.absent(); 96 } 97 int minIndex = 0; 98 for (int i = 1; i < keys.size(); i++) { 99 if (keys.get(i) < keys.get(minIndex)) { 100 minIndex = i; 101 } 102 } 103 Optional<BinaryNode> leftChild = createTreap(keys.subList(0, minIndex)); 104 Optional<BinaryNode> rightChild = createTreap(keys.subList(minIndex + 1, keys.size())); 105 return Optional.of(new BinaryNode(keys.get(minIndex), leftChild, rightChild)); 106 } 107 }; 108 createTree(int size, Random rng)109 abstract Optional<BinaryNode> createTree(int size, Random rng); 110 } 111 112 private static final TreeTraverser<BinaryNode> VIEWER = 113 new TreeTraverser<BinaryNode>() { 114 @Override 115 public Iterable<BinaryNode> children(BinaryNode root) { 116 return Optional.presentInstances(ImmutableList.of(root.left, root.right)); 117 } 118 }; 119 120 enum Traversal { 121 PRE_ORDER { 122 @Override view(T root, TreeTraverser<T> viewer)123 <T> Iterable<T> view(T root, TreeTraverser<T> viewer) { 124 return viewer.preOrderTraversal(root); 125 } 126 }, 127 POST_ORDER { 128 @Override view(T root, TreeTraverser<T> viewer)129 <T> Iterable<T> view(T root, TreeTraverser<T> viewer) { 130 return viewer.postOrderTraversal(root); 131 } 132 }, 133 BREADTH_FIRST { 134 @Override view(T root, TreeTraverser<T> viewer)135 <T> Iterable<T> view(T root, TreeTraverser<T> viewer) { 136 return viewer.breadthFirstTraversal(root); 137 } 138 }; 139 view(T root, TreeTraverser<T> viewer)140 abstract <T> Iterable<T> view(T root, TreeTraverser<T> viewer); 141 } 142 143 private Iterable<BinaryNode> view; 144 145 @Param Topology topology; 146 147 @Param({"1", "100", "10000", "1000000"}) 148 int size; 149 150 @Param Traversal traversal; 151 152 @Param({"1234"}) 153 SpecialRandom rng; 154 155 @BeforeExperiment setUp()156 void setUp() { 157 this.view = traversal.view(topology.createTree(size, rng).get(), VIEWER); 158 } 159 160 @Benchmark traversal(int reps)161 int traversal(int reps) { 162 int tmp = 0; 163 164 for (int i = 0; i < reps; i++) { 165 for (BinaryNode node : view) { 166 tmp += node.x; 167 } 168 } 169 return tmp; 170 } 171 } 172