Saya telah menulis beberapa kode Scala untuk melakukan operasi elemen-bijaksana pada koleksi. Di sini saya mendefinisikan dua metode yang melakukan tugas yang sama. Satu metode menggunakan zip
dan yang lainnya menggunakan 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)
Untuk membandingkan kedua metode ini dalam hal kecepatan, saya menulis kode berikut:
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")
}
Saya memanggil fun
metode dan lulus ES
dan ES1
seperti di bawah ini:
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)
Hasil menunjukkan bahwa metode bernama ES1
yang menggunakan zipped
lebih cepat daripada metode ES
yang digunakan zip
. Berdasarkan pengamatan ini, saya punya dua pertanyaan.
Kenapa zipped
lebih cepat dari itu zip
?
Apakah ada cara yang lebih cepat untuk melakukan operasi elemen pada koleksi di Scala?
scala
performance
scala-collections
jmh
elementwise-operations
pengguna12140540
sumber
sumber
Jawaban:
Untuk menjawab pertanyaan kedua Anda:
Kebenaran yang menyedihkan adalah bahwa meskipun memiliki keringkasan, peningkatan produktivitas, dan ketahanan terhadap bug yang bahasa fungsional belum tentu paling berkinerja tinggi - menggunakan fungsi urutan yang lebih tinggi untuk menentukan proyeksi yang akan dijalankan terhadap koleksi yang tidak gratis, dan loop ketat Anda menyoroti ini. Seperti yang telah ditunjukkan orang lain, alokasi penyimpanan tambahan untuk hasil antara dan akhir juga akan memiliki overhead.
Jika kinerja sangat penting, meskipun tidak berarti universal, dalam kasus seperti milik Anda, Anda dapat melepas operasi Scala menjadi setara dengan imperatif untuk mendapatkan kembali kendali langsung atas penggunaan memori dan menghilangkan panggilan fungsi.
Dalam contoh spesifik Anda,
zipped
jumlah dapat dilakukan secara imperatif dengan mengalokasikan sebelumnya, array yang dapat diubah yang dapat diubah ukurannya (karena zip berhenti ketika salah satu koleksi kehabisan elemen), dan kemudian menambahkan elemen pada indeks yang sesuai bersama-sama (sejak mengakses elemen array dengan indeks ordinal adalah operasi yang sangat cepat).Menambahkan fungsi ketiga,
ES3
ke suite pengujian Anda:Pada i7 saya, saya mendapatkan waktu respons berikut:
Bahkan yang lebih kejam adalah melakukan mutasi langsung di tempat yang lebih pendek dari dua array, yang jelas akan merusak isi dari salah satu array, dan hanya akan dilakukan jika array asli lagi tidak diperlukan:
Tapi jelas, mutasi elemen array langsung tidak dalam semangat Scala.
sumber
Array.tabulate(minSize)(i => arr(i) + arr1(i))
untuk membuat array AndaArray.tabulate
harus jauh lebih cepat daripada salah satuzip
atau dizipped
sini (dan ada di tolok ukur saya).for
ingin panggilan fungsi tingkat tinggi (foreach
). Lambda hanya akan dipakai satu kali dalam kedua kasus.Tidak ada jawaban lain yang menyebutkan alasan utama perbedaan kecepatan, yaitu
zipped
versi menghindari 10.000 alokasi tuple. Sebagai beberapa jawaban yang lain melakukan catatan,zip
versi melibatkan array menengah, sedangkanzipped
versi tidak, tapi mengalokasikan sebuah array untuk 10.000 elemen tidak apa yang membuatzip
versi jauh lebih buruk-itu 10.000 tupel berumur pendek yang sedang dimasukkan ke dalam array itu. Ini diwakili oleh objek pada JVM, jadi Anda melakukan banyak alokasi objek untuk hal-hal yang akan segera Anda buang.Sisa dari jawaban ini hanya menjelaskan sedikit lebih detail tentang bagaimana Anda dapat mengonfirmasi hal ini.
Pembandingan yang lebih baik
Anda benar-benar ingin menggunakan kerangka kerja seperti jmh untuk melakukan pembandingan apa pun secara bertanggung jawab pada JVM, dan bahkan bagian yang bertanggung jawab itu sulit, meskipun mengatur jmh itu sendiri tidak terlalu buruk. Jika Anda memiliki yang
project/plugins.sbt
seperti ini:Dan
build.sbt
seperti ini (saya menggunakan 2.11.8 karena Anda menyebutkan itu yang Anda gunakan):Maka Anda dapat menulis patokan Anda seperti ini:
Dan jalankan dengan
sbt "jmh:run -i 10 -wi 10 -f 2 -t 1 zipped_bench.ZippedBench"
:Yang menunjukkan bahwa
zipped
versi tersebut mendapatkan throughput sekitar 80% lebih banyak, yang mungkin kurang lebih sama dengan pengukuran Anda.Mengukur alokasi
Anda juga dapat meminta jmh untuk mengukur alokasi dengan
-prof gc
:... di mana
gc.alloc.rate.norm
mungkin bagian yang paling menarik, menunjukkan bahwazip
versi tersebut mengalokasikan lebih dari tiga kali lipatzipped
.Implementasi imperatif
Jika saya tahu bahwa metode ini akan dipanggil dalam konteks yang sangat sensitif terhadap kinerja, saya mungkin akan menerapkannya seperti ini:
Perhatikan bahwa tidak seperti versi yang dioptimalkan dalam salah satu jawaban lain, ini menggunakan
while
alih-alihfor
karenafor
akan tetap masuk ke operasi koleksi Scala. Kita dapat membandingkan implementasi ini (withWhile
), implementasi yang lain dioptimalkan (tetapi bukan di tempat) (withFor
), dan dua implementasi asli:Itu perbedaan yang sangat besar antara versi imperatif dan fungsional, dan semua tanda tangan metode ini persis identik dan implementasinya memiliki semantik yang sama. Ini tidak seperti implementasi imperatif menggunakan negara global, dll. Sementara
zip
danzipped
versi lebih mudah dibaca, saya pribadi tidak berpikir ada arti di mana versi imperatif menentang "semangat Scala", dan saya tidak akan ragu untuk menggunakannya sendiri.Dengan tabulasi
Pembaruan: Saya menambahkan
tabulate
implementasi ke tolok ukur berdasarkan komentar di jawaban lain:Ini jauh lebih cepat daripada
zip
versi, meskipun masih jauh lebih lambat daripada versi imperatif:Inilah yang saya harapkan, karena tidak ada yang secara inheren mahal untuk memanggil fungsi, dan karena mengakses elemen array dengan indeks sangat murah.
sumber
Mempertimbangkan
lazyZip
dari pada
zip
Scala 2.13 ditambahkan
lazyZip
untuk mendukung.zipped
zipped
(dan karenanyalazyZip
) lebih cepat daripadazip
karena, seperti yang dijelaskan oleh Tim dan Mike Allen ,zip
diikuti olehmap
akan menghasilkan dua transformasi terpisah karena ketatnya, sementarazipped
diikuti olehmap
akan menghasilkan satu transformasi yang dijalankan dalam sekali jalan karena kemalasan.zipped
memberiTuple2Zipped
, dan menganalisisTuple2Zipped.map
,kita melihat dua koleksi
coll1
dancoll2
diiterasi berulang dan pada setiap iterasi fungsif
dilewatkan untukmap
diterapkan di sepanjang jalantanpa harus mengalokasikan dan mengubah struktur perantara.
Menerapkan Travis' metode benchmarking, di sini adalah perbandingan antara baru
lazyZip
dan ditinggalkanzipped
di manamemberi
lazyZip
tampaknya melakukan sedikit lebih baik daripadazipped
diArraySeq
. Menariknya, melihat kinerja terdegradasi secara signifikan ketika menggunakanlazyZip
padaArray
.sumber
Anda harus selalu berhati-hati dengan pengukuran kinerja karena kompilasi JIT, tetapi kemungkinan alasannya adalah karena
zipped
malas dan mengekstrak elemen dariArray
vaules asli selamamap
panggilan, sedangkanzip
membuatArray
objek baru dan kemudian memanggilmap
objek baru.sumber