Using nested for loops in Java 8, to find out given difference [duplicate]

Question

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.

Assume that the list provided is already sorted. Now I want to find the number of elements whose difference is equal to some value say k.

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

Now the same logic using Java 8 streams, here to skip inner loop I have used return statement, but as the inner loop is not broken the performance is not improved.

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

@Alexei Kaigorodov, @Andy Turner, The marked as duplicate does not explain about how to do this with nested for loops. Also my logic is about counting such occurrences, the link does not explain that. — Learner
– Learner, Commented Jun 16, 2019 at 15:09
The duplicate makes it quite clear that there is no easy or idiomatic way to break out of forEach iteration. In Java 9 you could use takeWhile. But even this would be an inefficient way to solve the problem: it's still quadratic, whereas you could do it linearly (but not with streams). — Andy Turner
– Andy Turner, Commented Jun 16, 2019 at 17:35
Same as with your previous question, you are worrying about the tiny improvement of terminating the loop earlier instead of finding an approach with a lower asymptotic cost. If the list is sorted, you can use binary search instead of the inner loop. Or you maintain two indices into the list for an element e and its e+k position in a single loop. — Holger
– Holger, Commented Jun 17, 2019 at 9:30
@Holger, Or you maintain two indices into the list for an element e and its e+k position in a single loop. Can you please explain what it means? I understand like e is an element in the list, so see if e+k is also present in the list. Like this, I have to repeat for each element. Looks like what I am thinking is different from your point. — Learner
– Learner, Commented Jun 17, 2019 at 19:19
Start with index1, the index of e at 0. Find index2, the index of e+k, e.g. via Collections.binarySearch. Now enter the loop: raise index1 by one. Since the list is sorted, the new e is bigger than the old one, hence, the index of e + k must be bigger than the old one too. Raise index2 until you either, found e+k or reached an element bigger than e+k. Repeat until index2 reaches the end of the list. Then, you don’t need to raise index1 any more as the corresponding e+k wouldn’t be in the list. So you’re done. The bigger k, the less elements you have to check… — Holger
– Holger, Commented Jun 18, 2019 at 6:31

Pankaj Singhal · Accepted Answer · 2019-06-16 15:00:22Z

0

Replace your inner IntStream.forEach() with the following and see if it works as expected:

IntStream.range(i + 1, list.size())
        .filter(j -> list.get(j) - list.get(i) == k)
        .forEach(j -> result[0]++);

answered Jun 16, 2019 at 15:00

Pankaj Singhal

16.2k9 gold badges52 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Learner Over a year ago

Same issue, here also we are not breaking inner loop, so I am getting performance issue.

Collectives™ on Stack Overflow

Using nested for loops in Java 8, to find out given difference [duplicate]

1 Answer 1

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Linked

Related