Home | History | Annotate | Download | only in collect 
      1 /*
      2  * Copyright (C) 2014 The Guava Authors
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
      5  * in compliance with the License. You may obtain a copy of the License at
      6  *
      7  * http://www.apache.org/licenses/LICENSE-2.0
      8  *
      9  * Unless required by applicable law or agreed to in writing, software distributed under the License
     10  * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
     11  * or implied. See the License for the specific language governing permissions and limitations under
     12  * the License.
     13  */
     14 
     15 package com.google.common.collect;
     16 
     17 import static com.google.common.base.Preconditions.checkArgument;
     18 
     19 import com.google.caliper.BeforeExperiment;
     20 import com.google.caliper.Benchmark;
     21 import com.google.caliper.Param;
     22 
     23 import java.util.ArrayList;
     24 import java.util.Collections;
     25 import java.util.LinkedHashSet;
     26 import java.util.List;
     27 import java.util.Random;
     28 import java.util.Set;
     29 import java.util.TreeSet;
     30 
     31 /**
     32  * Provides supporting data for performance notes in the documentation of {@link
     33  * Ordering#sortedCopy} and {@link Ordering#immutableSortedCopy}, as well as for
     34  * automated code suggestions.
     35  *
     36  */
     37 public class SortedCopyBenchmark {
     38   @Param({"1", "10", "1000", "1000000"}) int size; // logarithmic triangular
     39 
     40   @Param boolean mutable;
     41 
     42   @Param InputOrder inputOrder;
     43 
     44   enum InputOrder {
     45     SORTED {
     46       @Override void arrange(List<Integer> list) {
     47         Collections.sort(list);
     48       }
     49     },
     50     ALMOST_SORTED {
     51       @Override void arrange(List<Integer> list) {
     52         Collections.sort(list);
     53         if (list.size() > 1) {
     54           int i = (list.size() - 1) / 2;
     55           Collections.swap(list, i, i + 1);
     56         }
     57       }
     58     },
     59     RANDOM {
     60       @Override void arrange(List<Integer> list) {}
     61     };
     62 
     63     abstract void arrange(List<Integer> list);
     64   }
     65 
     66   private ImmutableList<Integer> input;
     67 
     68   @BeforeExperiment
     69   void setUp() {
     70     checkArgument(size > 0, "empty collection not supported");
     71     Set<Integer> set = new LinkedHashSet<Integer>(size);
     72 
     73     Random random = new Random();
     74     while (set.size() < size) {
     75       set.add(random.nextInt());
     76     }
     77     List<Integer> list = new ArrayList<Integer>(set);
     78     inputOrder.arrange(list);
     79     input = ImmutableList.copyOf(list);
     80   }
     81 
     82   @Benchmark
     83   int collections(int reps) {
     84     int dummy = 0;
     85     // Yes, this could be done more elegantly
     86     if (mutable) {
     87       for (int i = 0; i < reps; i++) {
     88         List<Integer> copy = new ArrayList<Integer>(input);
     89         Collections.sort(copy);
     90         dummy += copy.get(0);
     91       }
     92     } else {
     93       for (int i = 0; i < reps; i++) {
     94         List<Integer> copy = new ArrayList<Integer>(input);
     95         Collections.sort(copy);
     96         dummy += ImmutableList.copyOf(copy).get(0);
     97       }
     98     }
     99     return dummy;
    100   }
    101 
    102   @Benchmark
    103   int ordering(int reps) {
    104     int dummy = 0;
    105     if (mutable) {
    106       for (int i = 0; i < reps; i++) {
    107         dummy += ORDERING.sortedCopy(input).get(0);
    108       }
    109     } else {
    110       for (int i = 0; i < reps; i++) {
    111         dummy += ORDERING.immutableSortedCopy(input).get(0);
    112       }
    113     }
    114     return dummy;
    115   }
    116 
    117   @Benchmark
    118   int sortedSet(int reps) {
    119     int dummy = 0;
    120     if (mutable) {
    121       for (int i = 0; i < reps; i++) {
    122         dummy += new TreeSet<Integer>(input).first();
    123       }
    124     } else {
    125       for (int i = 0; i < reps; i++) {
    126         dummy += ImmutableSortedSet.copyOf(input).first();
    127       }
    128     }
    129     return dummy;
    130   }
    131 
    132   private static final Ordering<Integer> ORDERING = Ordering.natural();
    133 }
    134