Created
September 29, 2016 21:24
Star
You must be signed in to star a gist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import javafx.util.Pair; | |
import java.util.*; | |
import java.util.function.Consumer; | |
import java.util.stream.Collectors; | |
import static java.lang.Math.max; | |
public class Main { | |
private static final int FRACTIONAL_DENOMINATOR_TO_KEEP = 1000; | |
/** | |
* The predicate that determines if an item shall be removed from the list. | |
* In this example we are looking for extreme cases, so we chose a predicate | |
* that removes all but every 1000 items. | |
* | |
* @param i | |
* @return true iff the item i shall be removed | |
*/ | |
private static boolean predicate(int i) { | |
return i % FRACTIONAL_DENOMINATOR_TO_KEEP != 0; | |
} | |
public static void main(String[] args) { | |
warmUpJit(); | |
computeAll(); | |
} | |
private static void warmUpJit() { | |
computeComparativeGraphData(1000, 10_000, 1000); // compute and throw away results | |
} | |
private static void computeAll() { | |
final int step = FRACTIONAL_DENOMINATOR_TO_KEEP; | |
final int start = step; | |
final int end = 150 * step; | |
final Map<Integer, Pair<Long, Long>> results = computeComparativeGraphData(start, end, step); | |
printResults("Actual times", results); | |
System.out.println(" --- 8< ---"); | |
printResults("Normalized times", normalize(results)); | |
} | |
private static void printResults(String title, Map<Integer, Pair<Long, Long>> results) { | |
System.out.println(title); | |
System.out.println("Length, Iterator, removeIf"); | |
results.entrySet().stream().sorted((e1, e2) -> e1.getKey() - e2.getKey()) | |
.forEach(entry -> { | |
final Pair<Long, Long> p = entry.getValue(); | |
System.out.println("" + entry.getKey() + ", " + | |
p.getKey() + ", " + | |
p.getValue() | |
); | |
}); | |
} | |
/** | |
* Normalize value pairs to make max values equal. | |
* | |
* @param results a Map from Integer to a Pair of Longs representing | |
* execution times for two different designs. | |
* | |
* @return a new map with normalized values, where max values are equal | |
*/ | |
private static Map<Integer, Pair<Long, Long>> normalize(Map<Integer, Pair<Long, Long>> results) { | |
final Pair<Long, Long> maxValues = results.values().stream(). | |
reduce(new Pair<>(0L, 0L), | |
(s, v) -> new Pair<>( | |
max(s.getKey(), v.getKey()), | |
max(s.getValue(), v.getValue()) | |
) | |
); | |
final double maxInteratorTime = maxValues.getKey().doubleValue(); | |
final double maxRemoveIfTime = maxValues.getValue().doubleValue(); | |
double factor = maxInteratorTime / maxRemoveIfTime; | |
System.out.println("Iterator is " + factor + " times slower than removeIf()"); | |
double scalingFactor = factor * 0.5; // we scale the faster times up half the way | |
return results.entrySet().stream(). | |
collect(Collectors.toMap( | |
Map.Entry::getKey, | |
p -> new Pair<>( | |
p.getValue().getKey(), | |
(long) (p.getValue().getValue() * scalingFactor) | |
)) | |
); | |
} | |
/** | |
* Create a map from array size to a pair of execution times - (iterator, removeIf) | |
* | |
* @param start start array size | |
* @param end ending array size | |
* @param step step between sizes | |
* @return a mapping (array size) -> (iterator execution time, removeIf execution time) | |
*/ | |
private static Map<Integer, Pair<Long, Long>> computeComparativeGraphData(int start, int end, int step) { | |
Map<Integer, Pair<Long, Long>> results = new HashMap<>(); | |
for (int n = start; n <= end; n += step) { | |
results.put(n, new Pair<>(timeIterator(n), timeRemoveIf(n))); | |
} | |
return results; | |
} | |
private static long timeRemoveIf(int n) { | |
return timeMany(n, l -> l.removeIf(i -> predicate(i))); | |
} | |
private static long timeIterator(int n) { | |
return timeMany(n, l -> { | |
for (Iterator<Integer> it = l.iterator(); it.hasNext();) { | |
if (predicate(it.next())) { | |
it.remove(); | |
} | |
} | |
} | |
); | |
} | |
/** | |
* Create and fill an array, then apply a consumer to all elements and measure average execution time | |
* | |
* @param size the size of the array to be created | |
* @param filter the list consumer to be evaluated | |
* @return average execution time in some unit of time ( | |
*/ | |
private static long timeMany(int size, Consumer<List<Integer>> filter) { | |
final int skipped = 5; // extreme values to be removed before averaging | |
final int n = skipped * 8; // total number of runs | |
long[] results = new long[n]; | |
for (int i=0; i<n; i++) { | |
results[i] = timeOnce(buildList(size), filter); | |
} | |
Arrays.sort(results); | |
long tailSum = Arrays.stream(results).skip(n - skipped).sum(); | |
long midAndTailSum = Arrays.stream(results).skip(skipped).sum(); | |
return midAndTailSum - tailSum; | |
} | |
private static List<Integer> buildList(int size) { | |
ArrayList<Integer> numbers = new ArrayList<>(size); | |
for (int i=0; i < size; i++) { | |
numbers.add(i); | |
} | |
return numbers; | |
} | |
private static <T> long timeOnce(List<T> list, Consumer<List<T>> filter) { | |
int lengthBefore = list.size(); | |
System.gc(); | |
long start = System.nanoTime(); | |
filter.accept(list); | |
long time = System.nanoTime() - start; | |
assert list.size() == lengthBefore / FRACTIONAL_DENOMINATOR_TO_KEEP; | |
return time; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment