В статье, написанной Даниэлем Корзеква, он сказал, что производительность следующего кода:
list.map(e => e*2).filter(e => e>10)
намного хуже, чем итеративное решение, написанное на Java.
Кто-нибудь может объяснить, почему? И какое лучшее решение для такого кода в Scala (надеюсь, это не итеративная версия Java, основанная на Scala)?
Причина, по которой эта конкретная программа работает медленно, заключается в том, что она работает с примитивами, но использует общие операции, поэтому примитивы должны быть упакованы. (Это можно было бы улучшить, если бы 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.)
view/force не спасет вас, когда вы работаете с примитивами.
- person Rex Kerr; 04.02.2011
e*2 было дорого, то стоимость промежуточного шага уменьшилась бы. Возможно, проблемы с памятью, если вы имеете дело с большими объемами данных.
- person ziggystar; 05.02.2011
В основном это обход списка дважды. Один раз для умножения каждого элемента на два. А затем еще раз, чтобы отфильтровать результаты.
Думайте об этом как об одном цикле while, создающем 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 гораздо более абстрактный и общий. Поэтому трудно оптимизировать каждый отдельный случай.
Я мог бы представить, что JIT-компилятор HotSpot может применить слияние потоков и циклов к коду в будущем, если увидит, что немедленные результаты не используются.
Кроме того, код 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.
У Wilfried Springer есть отличное решение, похожее на Scala. При использовании view не создаются (подправленные) копии всего списка.
Обратите внимание, что использование представления не всегда может быть идеальным. Например, если ваш первый вызов — filter, который, как ожидается, выбросит большую часть списка, может быть целесообразно явно создать более короткую версию и использовать view только после этого, чтобы улучшить локальность памяти для последующих итераций.
list.filter(e => e*2>10).map(e => e*2)
Эта попытка сначала сокращает список. Таким образом, второй обход выполняется на меньшем количестве элементов.
