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
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkNotNull;
20
21import com.google.common.primitives.Ints;
22
23import java.util.Collections;
24import java.util.List;
25import java.util.Set;
26
27/**
28 * Package up sample data for common collections benchmarking.
29 *
30 * @author Nicholaus Shupe
31 */
32class 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