Вопрос производительности Scala

Question

В статье , написанной Даниэлем Korzekwa , он сказал, что выполнение следующего кода:

list.map(e => e*2).filter(e => e>10)

намного хуже, чем итеративное решение, написанное с использованием Java.

Кто-нибудь может объяснить, почему? И каково лучшее решение для такого кода в Scala (надеюсь, это не итерационная версия Java, которая основана на Scala)?

Answer 1

Причина в том, что конкретный код медленный, заключается в том, что он работает с примитивами, но использует общие операции, поэтому примитивы должны быть упакованы.(Это могло бы быть улучшено, если бы 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.)

Answer 2

По сути, это обход списка дважды. Один раз для умножения каждого элемента на два. А потом в другой раз отфильтровать результаты.

Думайте об этом как об одном цикле while, создающем LinkedList с промежуточными результатами. А затем еще один цикл применения фильтра для получения окончательных результатов.

Это должно быть быстрее:

list.view.map(e => e * 2).filter(e => e > 10).force

Answer 3

Решение лежит в основном с JVM. Хотя в Scala есть обходной путь на рисунке @specialization, он значительно увеличивает размер любого специализированного класса и решает только половину проблемы - другая половина - создание временных объектов.

JVM фактически хорошо выполняет свою работу, оптимизируя многие из них, иначе производительность будет еще более ужасной, но Java не требует оптимизаций, которые делает Scala, поэтому JVM не предоставляет их. Я ожидаю, что это изменится в некоторой степени с введением SAM not-real-closures в Java.

Но, в конце концов, все сводится к уравновешиванию потребностей. Тот же цикл while, который Java и Scala выполняют намного быстрее, чем функциональный эквивалент Scala, можно сделать еще быстрее в C. Однако, несмотря на то, что говорят нам микробенчмарки, люди используют Java.

Answer 4

Подход Scala гораздо более абстрактный и общий. Поэтому трудно оптимизировать каждый отдельный случай.

Я мог бы представить, что JIT-компилятор HotSpot может применить слияние потоков и циклов к коду в будущем, если увидит, что непосредственные результаты не используются.

Кроме того, Java-код делает гораздо больше.

Если вы действительно просто хотите изменить структуру данных, рассмотрите transform. Это выглядит как map, но не создает новую коллекцию, e. g.:

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)

Я действительно надеюсь, что в будущем будут добавлены дополнительные операции на месте ...

Answer 5

Чтобы избежать двойного обхода списка, я думаю, что синтаксис for является хорошим вариантом здесь:

val list2 = for(v <- list1; e = v * 2; if e > 10) yield e

Answer 6

Рекс Керр правильно утверждает главную проблему: работая с неизменяемыми списками, указанный фрагмент кода создает промежуточные списки в памяти.Обратите внимание, что это не обязательно медленнее, чем эквивалентный код Java;вы просто никогда не используете неизменяемые структуры данных в Java.

У Уилфрида Спрингера есть хорошее, идеальное решение для Scala.При использовании view не создаются (манипулируемые) копии всего списка.

Обратите внимание, что использование представления не всегда может быть идеальным.Например, если ваш первый вызов filter, который, как ожидается, отбросит большую часть списка, может быть целесообразным явно создать более короткую версию и использовать view только после этого для улучшения локальности памяти для последующих итераций.

Answer 7

list.filter (e => e * 2> 10) .map (e => e * 2)

Эта попытка сначала уменьшает список.Таким образом, второй обход обходится без элементов.