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 
BinaryNode(int x, Optional<BinaryNode> left, Optional<BinaryNode> right)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
createTree(int size, Random rng)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
createTree(int size, Random rng)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
createTree(int size, Random rng)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
createTree(int size, Random rng)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.
createTreap(List<Integer> keys)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 
createTree(int size, Random rng)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
view(T root, TreeTraverser<T> viewer)137       <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
138         return viewer.preOrderTraversal(root);
139       }
140     },
141     POST_ORDER {
142       @Override
view(T root, TreeTraverser<T> viewer)143       <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
144         return viewer.postOrderTraversal(root);
145       }
146     },
147     BREADTH_FIRST {
148       @Override
view(T root, TreeTraverser<T> viewer)149       <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
150         return viewer.breadthFirstTraversal(root);
151       }
152     };
153 
view(T root, TreeTraverser<T> viewer)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
setUp()175   void setUp() {
176     this.view = traversal.view(
177         topology.createTree(size, rng).get(),
178         useBinaryTraverser ? BINARY_VIEWER : VIEWER);
179   }
180 
traversal(int reps)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