1 /* 2 * Copyright (C) 2010 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import static com.google.common.base.Preconditions.checkNotNull; 20 21 import com.google.common.primitives.Ints; 22 import java.util.Collections; 23 import java.util.List; 24 import java.util.Set; 25 26 /** 27 * Package up sample data for common collections benchmarking. 28 * 29 * @author Nicholaus Shupe 30 */ 31 class CollectionBenchmarkSampleData { 32 private final boolean isUserTypeFast; 33 private final SpecialRandom random; 34 private final double hitRate; 35 private final int size; 36 37 private final Set<Element> valuesInSet; 38 private final Element[] queries; 39 CollectionBenchmarkSampleData(int size)40 CollectionBenchmarkSampleData(int size) { 41 this(true, new SpecialRandom(), 1.0, size); 42 } 43 CollectionBenchmarkSampleData( boolean isUserTypeFast, SpecialRandom random, double hitRate, int size)44 CollectionBenchmarkSampleData( 45 boolean isUserTypeFast, SpecialRandom random, double hitRate, int size) { 46 this.isUserTypeFast = isUserTypeFast; 47 this.random = checkNotNull(random); 48 this.hitRate = hitRate; 49 this.size = size; 50 51 this.valuesInSet = createData(); 52 this.queries = createQueries(valuesInSet, 1024); 53 } 54 getValuesInSet()55 Set<Element> getValuesInSet() { 56 return valuesInSet; 57 } 58 getQueries()59 Element[] getQueries() { 60 return queries; 61 } 62 createQueries(Set<Element> elementsInSet, int numQueries)63 private Element[] createQueries(Set<Element> elementsInSet, int numQueries) { 64 List<Element> queryList = Lists.newArrayListWithCapacity(numQueries); 65 66 int numGoodQueries = (int) (numQueries * hitRate + 0.5); 67 68 // add good queries 69 int size = elementsInSet.size(); 70 if (size > 0) { 71 int minCopiesOfEachGoodQuery = numGoodQueries / size; 72 int extras = numGoodQueries % size; 73 74 for (int i = 0; i < minCopiesOfEachGoodQuery; i++) { 75 queryList.addAll(elementsInSet); 76 } 77 List<Element> tmp = Lists.newArrayList(elementsInSet); 78 Collections.shuffle(tmp, random); 79 queryList.addAll(tmp.subList(0, extras)); 80 } 81 82 // now add bad queries 83 while (queryList.size() < numQueries) { 84 Element candidate = newElement(); 85 if (!elementsInSet.contains(candidate)) { 86 queryList.add(candidate); 87 } 88 } 89 Collections.shuffle(queryList, random); 90 return queryList.toArray(new Element[0]); 91 } 92 createData()93 private Set<Element> createData() { 94 Set<Element> set = Sets.newHashSetWithExpectedSize(size); 95 while (set.size() < size) { 96 set.add(newElement()); 97 } 98 return set; 99 } 100 newElement()101 private Element newElement() { 102 int value = random.nextInt(); 103 return isUserTypeFast ? new Element(value) : new SlowElement(value); 104 } 105 106 static class Element implements Comparable<Element> { 107 final int hash; 108 Element(int hash)109 Element(int hash) { 110 this.hash = hash; 111 } 112 113 @Override equals(Object obj)114 public boolean equals(Object obj) { 115 return this == obj || (obj instanceof Element && ((Element) obj).hash == hash); 116 } 117 118 @Override hashCode()119 public int hashCode() { 120 return hash; 121 } 122 123 @Override compareTo(Element that)124 public int compareTo(Element that) { 125 return Ints.compare(hash, that.hash); 126 } 127 128 @Override toString()129 public String toString() { 130 return String.valueOf(hash); 131 } 132 } 133 134 static class SlowElement extends Element { SlowElement(int hash)135 SlowElement(int hash) { 136 super(hash); 137 } 138 139 @Override equals(Object obj)140 public boolean equals(Object obj) { 141 return slowItDown() != 1 && super.equals(obj); 142 } 143 144 @Override hashCode()145 public int hashCode() { 146 return slowItDown() + hash; 147 } 148 149 @Override compareTo(Element e)150 public int compareTo(Element e) { 151 int x = slowItDown(); 152 return x + super.compareTo(e) - x; // silly attempt to prevent opt 153 } 154 slowItDown()155 static int slowItDown() { 156 int result = 0; 157 for (int i = 1; i <= 1000; i++) { 158 result += i; 159 } 160 return result; 161 } 162 } 163 } 164