Производительность нескольких генераторов в выражениях Scala for?

Пример:

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

что можно перевести на:

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

or:

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

Временная сложность составляет O(c1 * c2 * c3) согласно второму переводу, что, если c1, c2, c3 — очень большие числа?

Я попытался поискать в Интернете и обнаружил множество кодов, в которых генераторов гораздо больше, чем в этом примере.

Вопрос: В других языках мы хотим избежать вложенных циклов for, но почему scala разработала этот механизм, если в нем есть какие-то специальные приемы для обеспечения очень хорошей производительности вложенного цикла?

Если я что-то неправильно понимаю, скажите, пожалуйста, я хотел бы лучше знать for-comprehension в scala. Спасибо.


for-loop performance scala for-comprehension
person Leyla Lee    schedule 14.09.2017    source источник
comment
Ну а если говорить про понимание в коллекциях, то такой пример означает, что вы действительно хотите получить все возможные упорядоченные триплеты и применить к ним какое-то действие. Как бы это ни было реализовано, с for comprehension или с циклами это займет, как вы заметили, O(c1* c2*c3) времени, и ни один язык ни с какими другими средствами не даст лучше. Но я чувствую, что вы воспринимаете для понимания как что-то идентичное циклам, хотя на самом деле это не так. Например, для таких коллекций, как List, это может быть рекурсия, для вещей, отличных от коллекций, это будет совсем другая вещь.   -  person Alexander Arendar    schedule 14.09.2017
comment
@AlexanderArendar Спасибо за ответ, да, я думаю, что цикл for-comprehension и for идентичны с точки зрения производительности. Ваш пример я не понимаю, можете ли вы объяснить его более ясно?   -  person Leyla Lee    schedule 14.09.2017
comment
Лейла, чтобы понять разницу между for Scala и for loop в Java или JavaScript, я думаю, что лучше всего прочитать хотя бы одну солидную книгу по Scala. Например, «Функциональное программирование на Scala» Рунара Бьярнасона.   -  person Alexander Arendar    schedule 14.09.2017

Ответы (1)


arrow_upward
1
arrow_downward

Есть две причины, по которым можно избежать вложенных циклов. Во-первых, читабельность и качество кода (особенно в ООП). Второе, как вы сказали, производительность, но это не жесткое правило. Это скорее индикатор того, что у вас в этом месте может быть более медленный код и стоит проверить, можно ли сделать то же самое быстрее. Очевидно, что многие проблемы требуют всего O(n^2) шагов, и не имеет значения, реализуете ли вы их с помощью вложенных циклов или каким-либо другим способом. Например. самый тривиальный случай, если у вас есть две коллекции размером n и вы хотите напечатать все пары (декартово произведение), для этого требуется всего O(n^2) шагов и все.

И помните, что for-comprehension в Scala — это не просто замена for инструкций из других языков. Это дает вам хороший способ для работы с монадами и написания более читаемого кода. Наличие нескольких выражений внутри for не обязательно означает, что у вас есть проблемы с производительностью.

person michaJlS    schedule 14.09.2017
comment
Наличие нескольких выражений внутри for не означает, что у вас проблемы с производительностью? Если внутри несколько выражений (генераторов), должна быть проблема с производительностью, не так ли? гораздо больше времени, чтобы закончить это - person Leyla Lee; 14.09.2017
comment
@LeylaLee Я добавил одно слово, чтобы сделать это предложение более понятным. Могут быть проблемы с производительностью, но это не обязательно. По-разному. И длительное время работы может быть либо результатом вашей плохой реализации, либо характером проблемы, которая не может быть решена быстрее. Это не проблема вложенности или нет. - person michaJlS; 14.09.2017