I was trying to implement a program from Coursera. The program statement is:
Given a sequence of non-negative integers a0,…,an−1, find the maximum pairwise product, that is, the largest integer that can be obtained by multiplying two different elements from the sequence.
I was trying out various ways to implement the solution and checking which works best.
I see that streams are still fast.
Why is it like that?
I was under the impression, then finding the largest 2 elements without sorting and multiplying them would be the best. Stream sorting (sequential stream is faster than parallel stream) is giving better result than this approach?
My program
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
public class MaxProduct {
public static void main(String[] args) {
List<Long> testList = createRandomArrayOfSize(30000000);
warmup(testList);
System.out.println("Warmup done");
Measure.meaureTime("No sorting, finding largest 2 elements and multiplying",
() -> findMaxProductByFindingLargest2Elements(new ArrayList<>(testList)));
Measure.meaureTime("Sorting, Multiplying last 2 elements",
() -> findMaxProductUsingSorting(new ArrayList<>(testList)));
Measure.meaureTime("Sorting using streams, Multiplying last 2 elements",
() -> findMaxProductUsingStreamSorting(new ArrayList<>(testList)));
Measure.meaureTime("Parallel sorting using streams, Multiplying last 2 elements by reduction",
() -> findMaxProductReducingParallelStream(new ArrayList<>(testList)));
}
public static long findMaxProductByFindingLargest2Elements(List<Long> list) {
long largest = 0;
long secondlargest = 0;
for (Long no : list) {
if (no > largest) {
secondlargest = largest;
largest = no;
}
}
return largest * secondlargest;
}
public static long findMaxProductUsingSorting(List<Long> list) {
list.sort(Comparator.naturalOrder());
return list.get(list.size() - 1) * list.get(list.size() - 2);
}
public static long findMaxProductUsingStreamSorting(List<Long> list) {
List<Long> collect = list.stream().sorted(Comparator.naturalOrder()).collect(Collectors.toList());
return collect.get(list.size() - 1) * collect.get(list.size() - 2);
}
public static long findMaxProductReducingParallelStream(List<Long> list) {
return list.parallelStream().sorted(Comparator.reverseOrder()).limit(2).reduce((x, y) -> x * y).get();
}
private static class Measure {
private static final int NO_OF_ITERATIONS = 3;
private static void meaureTime(String description, Runnable runnable) {
long startTime = System.nanoTime();
for (int i = 0; i < NO_OF_ITERATIONS; i++) {
runnable.run();
}
long timeTakenInNanos = System.nanoTime() - startTime;
System.out.println(description + " : " + (timeTakenInNanos / 3));
}
}
private static void warmup(List<Long> testList) {
findMaxProductByFindingLargest2Elements(new ArrayList<>(testList));
findMaxProductUsingSorting(new ArrayList<>(testList));
findMaxProductUsingStreamSorting(new ArrayList<>(testList));
findMaxProductReducingParallelStream(new ArrayList<>(testList));
}
private static List<Long> createRandomArrayOfSize(int size) {
return new Random().longs(size, 1, 10000000).boxed().collect(Collectors.toList());
}
}
Updated Results
No sorting, finding largest 2 elements and multiplying : 778547847
Sorting, Multiplying last 2 elements : 13423659115
Sorting using streams, Multiplying last 2 elements : 15518997158
Parallel sorting using streams, Multiplying last 2 elements by reduction : 5405983848
Updated the code
There is a bug in the first approach. If the largest no is at the zeroth index, then product will come as zero. Need to fix that.
Streams are not fast
Was a mistake in my test code. Fixed the mistake. And now working as expected.
