javajava-8

Using nested for loops in Java 8


I have below code where I am using nested for loops and I have some condition that breaks the inner for loop, and this improves the performance of this code.

public static int getMaxValue(List<Integer> list) {
    int result = -1;
    for(int i=0; i<list.size(); i++) {
        for(int j=i+1; j<list.size(); j++) {
            if(list.get(j) - list.get(i) <= 0) break;
            if(list.get(j) - list.get(i) > result) {
                result = list.get(j) - list.get(i);
            }
        }
    }
    return result;
}

Now how can I use Java 8 streams to do the same logic? I have come up with below code:

public static int getMaxValue(List<Integer> list) {
    int[] result = { -1 };
    IntStream.range(0, list.size()).forEach(i -> {
        IntStream.range(i + 1, list.size()).forEach(j -> {
            if(list.get(j) - list.get(i) <= 0) return;

            if(list.get(j) - list.get(i) > result[0]) {
                result[0] = list.get(j) - list.get(i);
            }
        });
    });
    return result[0];
}

Here I cannot use a break statement in java streams, so I have used return statement, but that still runs the inner loop, as it will not break it the performance is not improved.


Solution

  • If I understand your code, you're trying to find the maximum pairwise difference between any two elements in the input list. You can do that with IntSummaryStatistics:

    public static int getMaxValue(List<Integer> list) {
        IntSummaryStatistics stats = list.stream()
            .mapToInt(Integer::intValue)
            .summaryStatistics();
        return stats.getMax() - stats.getMin();
    }
    

    This is an O(n) operation, with O(1) auxiliary storage. There is still no need for an O(n²) operation. Ultimately, breaking out of a loop early is an optimization, but not a very effective one -- finding an approach with a lower asymptotic cost will always be more effective than just breaking out of a loop early.