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 23 import java.util.List; 24 import java.util.Random; 25 26 /** 27 * Benchmarks for the {@code TreeTraverser} and optimized {@code BinaryTreeTraverser} operations on 28 * binary trees. 29 * 30 * @author Louis Wasserman 31 */ 32 public class BinaryTreeTraverserBenchmark { 33 private static class BinaryNode { 34 final int x; 35 final Optional<BinaryNode> left; 36 final Optional<BinaryNode> right; 37 38 BinaryNode(int x, Optional<BinaryNode> left, Optional<BinaryNode> right) { 39 this.x = x; 40 this.left = left; 41 this.right = right; 42 } 43 } 44 45 enum Topology { 46 BALANCED { 47 @Override 48 Optional<BinaryNode> createTree(int size, Random rng) { 49 if (size == 0) { 50 return Optional.absent(); 51 } else { 52 int leftChildSize = (size - 1) / 2; 53 int rightChildSize = size - 1 - leftChildSize; 54 return Optional.of(new BinaryNode( 55 rng.nextInt(), createTree(leftChildSize, rng), createTree(rightChildSize, rng))); 56 } 57 } 58 }, 59 ALL_LEFT { 60 @Override 61 Optional<BinaryNode> createTree(int size, Random rng) { 62 Optional<BinaryNode> root = Optional.absent(); 63 for (int i = 0; i < size; i++) { 64 root = Optional.of(new BinaryNode(rng.nextInt(), root, Optional.<BinaryNode>absent())); 65 } 66 return root; 67 } 68 }, 69 ALL_RIGHT { 70 @Override 71 Optional<BinaryNode> createTree(int size, Random rng) { 72 Optional<BinaryNode> root = Optional.absent(); 73 for (int i = 0; i < size; i++) { 74 root = Optional.of(new BinaryNode(rng.nextInt(), Optional.<BinaryNode>absent(), root)); 75 } 76 return root; 77 } 78 }, 79 RANDOM { 80 /** 81 * Generates a tree with topology selected uniformly at random from the topologies of binary 82 * trees of the specified size. 83 */ 84 @Override 85 Optional<BinaryNode> createTree(int size, Random rng) { 86 int[] keys = new int[size]; 87 for (int i = 0; i < size; i++) { 88 keys[i] = rng.nextInt(); 89 } 90 return createTreap(Ints.asList(keys)); 91 } 92 93 // See http://en.wikipedia.org/wiki/Treap for details on the algorithm. 94 private Optional<BinaryNode> createTreap(List<Integer> keys) { 95 if (keys.isEmpty()) { 96 return Optional.absent(); 97 } 98 int minIndex = 0; 99 for (int i = 1; i < keys.size(); i++) { 100 if (keys.get(i) < keys.get(minIndex)) { 101 minIndex = i; 102 } 103 } 104 Optional<BinaryNode> leftChild = createTreap(keys.subList(0, minIndex)); 105 Optional<BinaryNode> rightChild = createTreap(keys.subList(minIndex + 1, keys.size())); 106 return Optional.of(new BinaryNode(keys.get(minIndex), leftChild, rightChild)); 107 } 108 }; 109 110 abstract Optional<BinaryNode> createTree(int size, Random rng); 111 } 112 113 private static final BinaryTreeTraverser<BinaryNode> BINARY_VIEWER = 114 new BinaryTreeTraverser<BinaryNode>() { 115 116 @Override 117 public Optional<BinaryNode> leftChild(BinaryNode node) { 118 return node.left; 119 } 120 121 @Override 122 public Optional<BinaryNode> rightChild(BinaryNode node) { 123 return node.right; 124 } 125 }; 126 127 private static final TreeTraverser<BinaryNode> VIEWER = new TreeTraverser<BinaryNode>() { 128 @Override 129 public Iterable<BinaryNode> children(BinaryNode root) { 130 return BINARY_VIEWER.children(root); 131 } 132 }; 133 134 enum Traversal { 135 PRE_ORDER { 136 @Override 137 <T> Iterable<T> view(T root, TreeTraverser<T> viewer) { 138 return viewer.preOrderTraversal(root); 139 } 140 }, 141 POST_ORDER { 142 @Override 143 <T> Iterable<T> view(T root, TreeTraverser<T> viewer) { 144 return viewer.postOrderTraversal(root); 145 } 146 }, 147 BREADTH_FIRST { 148 @Override 149 <T> Iterable<T> view(T root, TreeTraverser<T> viewer) { 150 return viewer.breadthFirstTraversal(root); 151 } 152 }; 153 154 abstract <T> Iterable<T> view(T root, TreeTraverser<T> viewer); 155 } 156 157 private Iterable<BinaryNode> view; 158 159 @Param 160 Topology topology; 161 162 @Param({"1", "100", "10000", "1000000"}) 163 int size; 164 165 @Param 166 Traversal traversal; 167 168 @Param 169 boolean useBinaryTraverser; 170 171 @Param({"1234"}) 172 SpecialRandom rng; 173 174 @BeforeExperiment 175 void setUp() { 176 this.view = traversal.view( 177 topology.createTree(size, rng).get(), 178 useBinaryTraverser ? BINARY_VIEWER : VIEWER); 179 } 180 181 @Benchmark int traversal(int reps) { 182 int tmp = 0; 183 184 for (int i = 0; i < reps; i++) { 185 for (BinaryNode node : view) { 186 tmp += node.x; 187 } 188 } 189 return tmp; 190 } 191 } 192
