Home | History | Annotate | Download | only in collect 
      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