Я написал некоторый код Scala для поэтапной операции над коллекцией. Здесь я определил два метода, которые выполняют одну и ту же задачу. Один метод использует, zip
а другой использует zipped
.
def ES (arr :Array[Double], arr1 :Array[Double]) :Array[Double] = arr.zip(arr1).map(x => x._1 + x._2)
def ES1(arr :Array[Double], arr1 :Array[Double]) :Array[Double] = (arr,arr1).zipped.map((x,y) => x + y)
Чтобы сравнить эти два метода с точки зрения скорости, я написал следующий код:
def fun (arr : Array[Double] , arr1 : Array[Double] , f :(Array[Double],Array[Double]) => Array[Double] , itr : Int) ={
val t0 = System.nanoTime()
for (i <- 1 to itr) {
f(arr,arr1)
}
val t1 = System.nanoTime()
println("Total Time Consumed:" + ((t1 - t0).toDouble / 1000000000).toDouble + "Seconds")
}
Я вызываю fun
метод и передаю ES
и ES1
как ниже:
fun(Array.fill(10000)(math.random), Array.fill(10000)(math.random), ES , 100000)
fun(Array.fill(10000)(math.random), Array.fill(10000)(math.random), ES1, 100000)
Результаты показывают, что названный метод, ES1
который использует zipped
, быстрее, чем метод, ES
который использует zip
. Основываясь на этих наблюдениях, у меня есть два вопроса.
Почему zipped
быстрее чем zip
?
Есть ли еще более быстрый способ поэтапного выполнения операций над коллекцией в Scala?
scala
performance
scala-collections
jmh
elementwise-operations
user12140540
источник
источник
Ответы:
Чтобы ответить на ваш второй вопрос:
Печальная правда заключается в том, что, несмотря на краткость, повышенную производительность и устойчивость к ошибкам, функциональные языки не обязательно являются наиболее производительными - использование функций более высокого порядка для определения проекции, выполняемой на несвободные коллекции, и ваш жесткий цикл это подчеркивает. Как уже отмечали другие, дополнительное распределение памяти для промежуточных и конечных результатов также будет иметь накладные расходы.
Если производительность критична, хотя отнюдь не универсальна, в таких случаях, как ваш, вы можете развернуть операции Scala обратно в императивные эквиваленты, чтобы восстановить более прямой контроль над использованием памяти и исключить вызовы функций.
В вашем конкретном примере
zipped
суммы могут быть выполнены обязательно, предварительно выделив фиксированный, изменяемый массив правильного размера (поскольку zip останавливается, когда в одной из коллекций заканчивается элемент), а затем добавляя элементы с соответствующим индексом вместе (так как доступ элементы массива по порядковому индексу - очень быстрая операция).Добавление третьей функции
ES3
в ваш набор тестов:На моем i7 я получаю следующее время отклика:
Еще более отвратительным было бы сделать прямую мутацию на месте более короткого из двух массивов, которая, очевидно, повредила бы содержимое одного из массивов, и это было бы сделано, только если бы исходный массив снова не понадобился:
Но очевидно, что прямая мутация элементов массива не в духе Scala.
источник
Array.tabulate(minSize)(i => arr(i) + arr1(i))
Array.tabulate
должно быть гораздо быстрее, чем здесьzip
илиzipped
здесь (и это в моих тестах).for
функция обращена к вызову функции более высокого порядка (foreach
). В обоих случаях лямбда будет создаваться только один раз.Ни в одном из других ответов не упоминается основная причина разницы в скорости, заключающаяся в том, что
zipped
версия избегает 10000 распределений кортежей. Как пара других ответов сделать примечание, тоzip
версия включает в себя промежуточный массив, в то время какzipped
версия не делает, но выделять массив 10000 элементов не то , что делаетzip
версию намного хуже, это 10.000 короткоживущих кортежей , которые помещаются в этот массив. Они представлены объектами в JVM, поэтому вы делаете кучу распределений объектов для вещей, которые вы немедленно собираетесь выбросить.Оставшаяся часть этого ответа просто подробнее расскажет о том, как вы можете это подтвердить.
Лучший бенчмаркинг
Вы действительно хотите использовать инфраструктуру, такую как jmh, для ответственного проведения любых сравнительных тестов в JVM, и даже тогда ответственно сложно, хотя настройка самого jmh не так уж и плоха. Если у вас есть
project/plugins.sbt
такие:И
build.sbt
вот так (я использую 2.11.8, так как вы упоминаете, что вы используете):Затем вы можете написать свой тест следующим образом:
И запустить его с
sbt "jmh:run -i 10 -wi 10 -f 2 -t 1 zipped_bench.ZippedBench"
:Что показывает, что
zipped
версия получает примерно на 80% больше пропускной способности, что, вероятно, более или менее соответствует вашим измерениям.Измерительные распределения
Вы также можете попросить JMH измерить распределение с
-prof gc
:…где
gc.alloc.rate.norm
, пожалуй, самая интересная часть, показывающая, чтоzip
версия выделяется в три раза больше, чемzipped
.Императивные реализации
Если бы я знал, что этот метод будет вызываться в чрезвычайно чувствительных к производительности контекстах, я бы, вероятно, реализовал его следующим образом:
Обратите внимание, что в отличие от оптимизированной версии в одном из других ответов, она использует
while
вместо a,for
посколькуfor
все равно будет десагар в операциях с коллекциями Scala. Мы можем сравнить эту реализацию (withWhile
), оптимизированную (но не на месте) реализацию другого ответа (withFor
) и две исходные реализации:Это действительно огромная разница между императивной и функциональной версиями, и все эти сигнатуры методов абсолютно идентичны, а реализации имеют одинаковую семантику. Это не так, как императивные реализации используют глобальное состояние и т. Д. В то время как
zip
иzipped
версия более читаемая, лично я не думаю , что есть какой -то смысл , в котором императивные версии против «духа Scala», и я бы не колеблясь , использовать их сам.С таблицей
Обновление: я добавил
tabulate
реализацию в тест на основе комментария в другом ответе:Это намного быстрее, чем
zip
версии, хотя все еще намного медленнее, чем императивные:Это то, что я ожидаю, поскольку нет ничего изначально дорогого в вызове функции, и потому что доступ к элементам массива по индексу очень дешев.
источник
Рассматривать
lazyZip
вместо
zip
Scala 2.13 добавлен
lazyZip
в пользу.zipped
zipped
(и, следовательно,lazyZip
) быстрее, чемzip
потому, что, как объяснили Тим и Майк Аллен ,zip
следование за нимmap
приведет к двум отдельным преобразованиям из-за строгости, аzipped
затемmap
приведет к одному преобразованию, выполненному за один раз из-за лени.zipped
даетTuple2Zipped
и анализируетTuple2Zipped.map
,мы видим две коллекции
coll1
иcoll2
повторяем и на каждой итерации функция,f
переданная вmap
нее, применяется по путибез необходимости выделять и преобразовывать посреднические структуры.
Применяя метод бенчмаркинга Трэвиса, приведем сравнение между новым
lazyZip
и устаревшим,zipped
гдедает
lazyZip
кажется, работает немного лучше, чемzipped
наArraySeq
. Интересно, что заметить значительно пониженную производительность при использованииlazyZip
наArray
.источник
Вы всегда должны быть осторожны с измерением производительности из-за JIT-компиляции, но вероятная причина в том, что
zipped
он ленив и извлекает элементы из исходныхArray
пар во времяmap
вызова, тогда какzip
создает новыйArray
объект, а затем вызываетmap
новый объект.источник