Performance of multiple generators in Scala 'for' expressions?

0
votes

An example:

for(x <- c1; y <- c2; z <- c3) yield {...}

which can be translated into:

c1.flatMap(x => c2.flatMap(y => c3.map(z => {...})))

or:

for(x <- c1) for (y <- c2) for (z <- c3) yield {...}

Time complexity is O(c1 * c2 * c3) according to the second translation, what if c1, c2, c3 are very big numbers?

I tried to search on the internet, and I found there are many codes who have much more generators than this example.

Question: In other languages, we want to avoid nested for loops, but why scala designed this mechanism, dose it have some special tricks to make a very good performance for the nested loop ?

If I misunderstand something, please tell me, I would like to know better the for-comprehension in scala. Thank you.

1
performancescalafor-loopfor-comprehension
Well, if you talk about for comprehension in collections then such example means that you really want to get every possible ordered triplet and apply some action to it. No matter how this is implemented, with for comprehension or with loops it will take as you noted O(c1* c2*c3) time, and no language with any other means will deliver better. But I feel like you perceive for comprehension as smthng identical to loops while in fact it is not. For example, for collections like List this may be recursion, for things different than collections this will be altogether different thing. - Alexander Arendar
@AlexanderArendar Thank you for reply, yes, I think the for-comprehension and for loop are the identical in terms of performance. Your example I dont understand, can you explain it more clearly ? - Leyla Lee
Leyla, in order to understand difference between for comprehension in Scala and for loop in Java or JavaScript, I think the best way is to read at least one solid book on Scala. For example "Functional Programming in Scala" by Runar Bjarnason. - Alexander Arendar

1 Answers

1
votes

There are two reasons why one may wish to avoid nested loops. The first one, the readability and quality of the code (especially in OOP). The second, as you said, performance, but it isn't a hard rule. This is more like an indicator, that you may have in this place slower code and it's worth verifying whether it is possible to do the same thing faster. Obviously, many problems just require O(n^2) steps and it doesn't matter if you implement it using nested loops or some other way. E.g. most trivial case, if you have two collections of size n and you want to print all pairs (Cartesian product), it just requires O(n^2) steps and that's it.

And remember that for-comprehension in Scala isn't just a replacement for for instructions from other languages. It gives you a nice way for working with Monads and writing more readable code. Having multiple expressions inside the for doesn't necessarily mean that you have a performance problem here.