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 
41   CollectionBenchmarkSampleData(int size) {
42     this(true, new SpecialRandom(), 1.0, size);
43   }
44 
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 
59   Set<Element> getValuesInSet() {
60     return valuesInSet;
61   }
62 
63   Element[] getQueries() {
64     return queries;
65   }
66 
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 
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 
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;
114     Element(int hash) {
115       this.hash = hash;
116     }
117     @Override public boolean equals(Object obj) {
118       return this == obj
119           || (obj instanceof Element && ((Element) obj).hash == hash);
120     }
121     @Override public int hashCode() {
122       return hash;
123     }
124     @Override
125     public int compareTo(Element that) {
126       return Ints.compare(hash, that.hash);
127     }
128     @Override public String toString() {
129       return String.valueOf(hash);
130     }
131   }
132 
133   static class SlowElement extends Element {
134     SlowElement(int hash) {
135       super(hash);
136     }
137     @Override public boolean equals(Object obj) {
138       return slowItDown() != 1 && super.equals(obj);
139     }
140     @Override public int hashCode() {
141       return slowItDown() + hash;
142     }
143     @Override public int compareTo(Element e) {
144       int x = slowItDown();
145       return x + super.compareTo(e) - x; // silly attempt to prevent opt
146     }
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