В статье написанной Даниэлем Корцевой, он сказал, что производительность следующего кода:
list.map(e => e*2).filter(e => e>10)
намного хуже, чем итерационное решение, написанное с использованием Java.
Может кто-нибудь объяснить, почему? И что является лучшим решением для такого кода в Scala (надеюсь, это не итеративная версия Java, которая является Scala -fied)?
Причина, по которой этот код медленный, заключается в том, что он работает с примитивами, но использует общие операции, поэтому примитивы должны быть в штучной упаковке. (Это может быть улучшено, если List и его предки были специализированными.) Это, вероятно, замедлит работу примерно в 5 раз.
Кроме того, алгоритмически эти операции несколько дороги, потому что вы создаете целый список, а затем создаете целый новый список, отбрасывая несколько компонентов промежуточного списка. Если бы вы сделали это одним махом, тогда вам было бы лучше. Вы можете сделать что-то вроде:
list collect (case e if (e*2>10) => e*2)
но что, если расчет e*2 действительно дорог? Тогда вы могли бы
(List[Int]() /: list)((ls,e) => { val x = e*2; if (x>10) x :: ls else ls }
за исключением того, что это будет выглядеть обратным образом. (Если нужно, вы можете отменить его, но для этого требуется создать новый список, что опять же не является идеальным алгоритмом.)
Конечно, у вас есть аналогичные алгоритмические проблемы в Java, если вы используете одноуровневый список - ваш новый список окажется в обратном порядке, или вам нужно создать его дважды, сначала в обратном порядке, а затем вперед, или вы должны построить его с (без хвоста) рекурсии (что легко в Scala, но нецелесообразно для такого рода вещей на любом языке, поскольку вы исчерпаете стек), или вам нужно создать изменяемый список и затем делать вид, что он не изменчив. (Что, кстати, вы также можете сделать в Scala - см. mutable.LinkedList.)
В основном это перемещение списка дважды. Один раз для умножения каждого элемента на два. И еще раз, чтобы отфильтровать результаты.
Подумайте об этом как о том, пока цикл создает LinkedList с промежуточными результатами. А затем еще один цикл, применяющий фильтр для получения окончательных результатов.
Это должно быть быстрее:
list.view.map(e => e * 2).filter(e => e > 10).force
Решение лежит в основном с JVM. Хотя Scala имеет обходной путь на рисунке @specialization, который значительно увеличивает размер любого специализированного класса и решает только половину проблемы - вторая половина - создание временных объектов.
JVM на самом деле делает хорошую работу, оптимизируя ее, или производительность будет еще более ужасной, но Java не требует оптимизаций, которые делает Scala, поэтому JVM не предоставляет их. Я ожидаю, что это изменится в некоторой степени с введением SAM не-реальных замыканий в Java.
Но, в конце концов, это сводится к балансированию потребностей. Тот же цикл while, что Java и Scala делают намного быстрее, чем эквивалент функции Scala, могут выполняться быстрее, но в C. Однако, несмотря на то, что говорят нам микробиблиотеки, люди используют Java.
Scala подход гораздо более абстрактный и общий. Поэтому трудно оптимизировать каждый отдельный случай.
Я мог представить, что компилятор HotSpot JIT может применить к коду потоковое и циклическое слияние в будущем, если увидит, что немедленные результаты не используются.
Кроме того, код Java просто делает гораздо больше.
Если вы действительно хотите изменить мутацию над структурой данных, рассмотрите transform.
Он немного похож на map, но не создает новую коллекцию, например. г:.
val array = Array(1,2,3,4,5,6,7,8,9,10).transform(_ * 2)
// array is now WrappedArray(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)
Я действительно надеюсь, что некоторые дополнительные операции на месте будут добавлены в будущее...
Чтобы избежать перебора списка дважды, я думаю, что синтаксис for является хорошим вариантом здесь:
val list2 = for(v <- list1; e = v * 2; if e > 10) yield e
Рекс Керр правильно утверждает основную проблему: работая над неизменными списками, заявленная часть кода создает промежуточные списки в памяти. Обратите внимание, что это не обязательно медленнее, чем эквивалентный Java-код; вы просто никогда не используете неизменяемые структуры данных на Java.
У Вилфрида Спрингера есть приятное, Scala idomatic решение. Используя view, нет (управляемых) копий всего списка.
Обратите внимание, что использование представления может не всегда быть идеальным. Например, если ваш первый вызов filter, который, как ожидается, выкинет большую часть списка, может оказаться целесообразным создать более короткую версию явно и использовать view только после этого, чтобы улучшить локальность памяти для последующих итераций.
list.filter(e = > e * 2 > 10).map(e = > e * 2)
Эта попытка сначала сводит список. Таким образом, второе перемещение на меньшее количество элементов.