Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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