Let us define a static nested class Time under PriorityQueueTest that stores runtimes for the add() and remove() methods in any PQ:
What is the advantage of defining static nested class over non-static nested class?
Runtime Estimation
Let us define addRuntime() that estimates the runtime for add() and remove()for a particular PQ:
L5-8: estimates the runtime for add():
L5: gets the snapshot of the starting time using .
Is the approach using currentTimeMillis() a proper way of benchmarking the speed?
We then define benchmark() that estimates the speeds of multiple PQs using the same lists of keys by calling addRuntime():
L1: method declaration:
AbstractPriorityQueue[]: It is unusual to declare an array of objects involving generics in Java (you will see the unique use case of it in the testSpeedAux() method).
Why do we need to benchmark the priority queues multiple times?
Benchmark
Let us define testSpeedAux() that takes multiple PQs and prints out the benchmarking results:
L1: annotates indicating that this method takes vararg parameters.
L2: declares a final method that cannot be overridden by its subclasses.
Why is it recommended to declare the method final if it takes vararg parameters?
Why does JVM need to be warmed-up before the actual benchmarking?
Why should you use StringJoiner instead of concatenating strings with the + operator?
Speed Comparison
The followings show runtime comparisons between LazyPQ, EagerPQ, and BinaryHeap:
static class Time {
long add = 0;
long remove = 0;
}
Supplier: passes a function as a parameter that returns a key of the generic type T.
L2: generates an array of Time using several stream operations. The dimension of times[] is the same as the dimension of queues such that times[i] accumulates the speeds taken by the queue[i], respectively.
: creates a stream specified by the supplier.
: creates a stream with a specific size.
: returns an array of the specific type.
L4: benchmarks the PQs multiple times as specified by iter.
L5: generates the list of keys specified by the supplier sup.
L6-7: estimate the runtimes by using the same list of keys for each PQ.
It can take a 0-to-many number of abstract PQs.
The type of queues is AbstractPriorityQueue<Integer>[] such that it can be directly passed to the benchmark() method.
<T extends Comparable<T>> void addRuntime(AbstractPriorityQueue<T> queue, Time time, List<T> keys) {
long st, et;
// runtime for add()
st = System.currentTimeMillis();
keys.forEach(queue::add);
et = System.currentTimeMillis();
time.add += et - st;
// runtime for remove()
st = System.currentTimeMillis();
while (!queue.isEmpty()) queue.remove();
et = System.currentTimeMillis();
time.remove += et - st;
}
<T extends Comparable<T>> Time[] benchmark(AbstractPriorityQueue<T>[] queues, int size, int iter, Supplier<T> sup) {
Time[] times = Stream.generate(Time::new).limit(queues.length).toArray(Time[]::new);
for (int i = 0; i < iter; i++) {
List<T> keys = Stream.generate(sup).limit(size).collect(Collectors.toList());
for (int j = 0; j < queues.length; j++)
addRuntime(queues[j], times[j], keys);
}
return times;
}
@SafeVarargs
final void testRuntime(AbstractPriorityQueue<Integer>... queues) {
final int begin_size = 1000;
final int end_size = 10000;
final int inc = 1000;
final Random rand = new Random();
for (int size = begin_size; size <= end_size; size += inc) {
// JVM warm-up
benchmark(queues, size, 10, rand::nextInt);
// benchmark all priority queues with the same keys
Time[] times = benchmark(queues, size, 1000, rand::nextInt);
StringJoiner joiner = new StringJoiner("\t");
joiner.add(Integer.toString(size));
joiner.add(Arrays.stream(times).map(t -> Long.toString(t.add)).collect(Collectors.joining("\t")));
joiner.add(Arrays.stream(times).map(t -> Long.toString(t.remove)).collect(Collectors.joining("\t")));
System.out.println(joiner.toString());
}
}