Iterations required when chaining stream intermediate operations

Question

I know that stream intermediate operations in Java are lazy and do not get executed until a terminal operation is being called. However, I'm not sure whether chaining intermediate operations increases the number of iterations required. Because sometimes we separate operations into multiple intermediate operations, just to make it easier to read.

So for instance the following two examples do the same thing. But in the second example, two intermediate operations are joined into one.

myStream
     .map(s -> methodA(s))
     .map(s -> methodB(s))
     .collect(Collectors.joining());

myStream
     .map(s -> methodB(methodA(s)))
     .collect(Collectors.joining());

Aren't the number of iterations required is same in both cases? Because it seems, it is possible for the JVM to execute it in a single iteration (similar to a single for-loop), rather than iterating over the elements for each intermediate operation.

You mean *time complexity*... not performance or execution time? Clearly the time complexity here would be the same. — ernest_k, Jul 01 '21 at 17:43
Yes, the time complexity. Like 2n, 3n. Not the execution time. — Gayan Weerakutti, Jul 01 '21 at 17:44
Time *complexity* does not change, maybe one time you run N operations, the other time N+N=2*N operations but they are still O(N). If you split it into 100 operations you run 100*N operations which is still O(N). — luk2302, Jul 01 '21 at 17:45
When talking about complexity, `O(2n)`, `O(3n)` etc aren't relevant. They're both just `O(n)`. It represents growth, not actual execution time. — Henry Twist, Jul 01 '21 at 17:49
@jrook Mine is a bit more specific. I want to know if there's a difference in the number of iterations required. — Gayan Weerakutti, Jul 01 '21 at 17:51
Number of iterations (time) is very different to order, which is what you're referring to with `O(n)` (growth) @GayanWeerakutti. Which one are you trying to find out? — Henry Twist, Jul 01 '21 at 17:54
Did you measure how long each takes? Does this answer your question? [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) — Ole V.V., Jul 01 '21 at 17:58
@GayanWeerakutti Here's [another answer](https://stackoverflow.com/a/24055107/2928853), says the same thing. Between hotspot optimizations and other surrounding conditions, it is virtually impossible to know by theoretical arguments. — jrook, Jul 01 '21 at 18:04
Even whether the intermediate operations are lazy or not, does not change the time complexity. So don't confuse time complexity with performance. They may interact, but still are entirely different things. — Holger, Jul 01 '21 at 18:08
@Holger I updated the question. I'm more curious about the iteration count. — Gayan Weerakutti, Jul 01 '21 at 18:11
Addressing your updated question, both variants are equivalent to a single loop. — Holger, Jul 01 '21 at 18:12
@Holger Good to know. Your other answer is when using filter operations though. If you have a different answer to this, focusing on the iteration counts and such, I would happy to reopen this question. — Gayan Weerakutti, Jul 01 '21 at 18:29
@GayanWeerakuttiI suggest that it will be better to ask a new question with only the part that has not been answered in the linked-to original. In your new question include a link to that question and/or this one to make the difference clear. — Ole V.V., Jul 01 '21 at 18:57
@OleV.V. I think the question is already very different. I've rephrased it few times. But I'm not sure whether the answer would be the same or not. May I reopen it? — Gayan Weerakutti, Jul 02 '21 at 05:06
Basically, I'm asking about the iteration count. As @Holger mentioned it same for both variants. — Gayan Weerakutti, Jul 02 '21 at 05:26

WJS · Answer 1 · 2021-07-02T18:23:46.450

I know that stream intermediate operations in Java are lazy and do not get executed until a terminal operation is being called. However, I'm not sure whether chaining intermediate operations increases the number of iterations required. ... Aren't the number of iterations required is same in both cases?

The following seems to confirm your (and others) conclusions. I used AtomicInteger since the counts would be off using parallel streams. In no case did the total number of method calls differ. However, since the two methods return different values, the sums will be different due to the ordering of the maps. In the first case, MethodA is processed last so its value will be summed. In the second case, MethodB is processed last so its value will be summed.

static AtomicInteger count = new AtomicInteger(0);
Random r = new Random();
for (int i = 0; i < 10000; i++) {
    count.set(0);
    List<Integer> list = IntStream.generate(
            () -> 1)
            .limit(r.nextInt(10) + 1).boxed().toList();
    
    int sum1 = list.stream().mapToInt(s -> methodB(s)).map(s -> methodA(s))
            .sum();
    
    int save = count.get();
    
    count.set(0);
    int sum2 = list.stream().mapToInt(s -> methodB(methodA(s)))
              .sum();
    if (save != count.get()) {
        System.out.println(
                "Inconsistent counts: " + save + " " + count);
    }
}
    
public static int methodA(int v) {
    count.incrementAndGet();
    return 1;
}

    
public static int methodB(int v) {
    count.incrementAndGet();
    return 2;
}

Iterations required when chaining stream intermediate operations

1 Answers1