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 23 import java.util.Collections; 24 import java.util.List; 25 import java.util.Set; 26 27 /** 28 * Package up sample data for common collections benchmarking. 29 * 30 * @author Nicholaus Shupe 31 */ 32 class CollectionBenchmarkSampleData { 33 private final boolean isUserTypeFast; 34 private final SpecialRandom random; 35 private final double hitRate; 36 private final int size; 37 38 private final Set<Element> valuesInSet; 39 private final Element[] queries; 40 CollectionBenchmarkSampleData(int size)41 CollectionBenchmarkSampleData(int size) { 42 this(true, new SpecialRandom(), 1.0, size); 43 } 44 CollectionBenchmarkSampleData( boolean isUserTypeFast, SpecialRandom random, double hitRate, int size)45 CollectionBenchmarkSampleData( 46 boolean isUserTypeFast, 47 SpecialRandom random, 48 double hitRate, 49 int size) { 50 this.isUserTypeFast = isUserTypeFast; 51 this.random = checkNotNull(random); 52 this.hitRate = hitRate; 53 this.size = size; 54 55 this.valuesInSet = createData(); 56 this.queries = createQueries(valuesInSet, 1024); 57 } 58 getValuesInSet()59 Set<Element> getValuesInSet() { 60 return valuesInSet; 61 } 62 getQueries()63 Element[] getQueries() { 64 return queries; 65 } 66 createQueries(Set<Element> elementsInSet, int numQueries)67 private Element[] createQueries(Set<Element> elementsInSet, int numQueries) { 68 List<Element> queryList = Lists.newArrayListWithCapacity(numQueries); 69 70 int numGoodQueries = (int) (numQueries * hitRate + 0.5); 71 72 // add good queries 73 int size = elementsInSet.size(); 74 if (size > 0) { 75 int minCopiesOfEachGoodQuery = numGoodQueries / size; 76 int extras = numGoodQueries % size; 77 78 for (int i = 0; i < minCopiesOfEachGoodQuery; i++) { 79 queryList.addAll(elementsInSet); 80 } 81 List<Element> tmp = Lists.newArrayList(elementsInSet); 82 Collections.shuffle(tmp, random); 83 queryList.addAll(tmp.subList(0, extras)); 84 } 85 86 // now add bad queries 87 while (queryList.size() < numQueries) { 88 Element candidate = newElement(); 89 if (!elementsInSet.contains(candidate)) { 90 queryList.add(candidate); 91 } 92 } 93 Collections.shuffle(queryList, random); 94 return queryList.toArray(new Element[0]); 95 } 96 createData()97 private Set<Element> createData() { 98 Set<Element> set = Sets.newHashSetWithExpectedSize(size); 99 while (set.size() < size) { 100 set.add(newElement()); 101 } 102 return set; 103 } 104 newElement()105 private Element newElement() { 106 int value = random.nextInt(); 107 return isUserTypeFast 108 ? new Element(value) 109 : new SlowElement(value); 110 } 111 112 static class Element implements Comparable<Element> { 113 final int hash; Element(int hash)114 Element(int hash) { 115 this.hash = hash; 116 } equals(Object obj)117 @Override public boolean equals(Object obj) { 118 return this == obj 119 || (obj instanceof Element && ((Element) obj).hash == hash); 120 } hashCode()121 @Override public int hashCode() { 122 return hash; 123 } 124 @Override compareTo(Element that)125 public int compareTo(Element that) { 126 return Ints.compare(hash, that.hash); 127 } toString()128 @Override public String toString() { 129 return String.valueOf(hash); 130 } 131 } 132 133 static class SlowElement extends Element { SlowElement(int hash)134 SlowElement(int hash) { 135 super(hash); 136 } equals(Object obj)137 @Override public boolean equals(Object obj) { 138 return slowItDown() != 1 && super.equals(obj); 139 } hashCode()140 @Override public int hashCode() { 141 return slowItDown() + hash; 142 } compareTo(Element e)143 @Override public int compareTo(Element e) { 144 int x = slowItDown(); 145 return x + super.compareTo(e) - x; // silly attempt to prevent opt 146 } slowItDown()147 static int slowItDown() { 148 int result = 0; 149 for (int i = 1; i <= 1000; i++) { 150 result += i; 151 } 152 return result; 153 } 154 } 155 } 156