Kapan saya harus memilih Vector di Scala?

200

Tampaknya Vectorsudah terlambat ke pesta koleksi Scala, dan semua posting blog berpengaruh sudah pergi.

Di Jawa ArrayListadalah koleksi default - saya mungkin menggunakan LinkedListtetapi hanya ketika saya sudah memikirkan algoritma dan cukup peduli untuk mengoptimalkan. Dalam Scala saya harus menggunakan Vectorsebagai default saya Seq, atau mencoba bekerja ketika Listsebenarnya lebih tepat?

scala vector scala-collections Duncan McGregor
sumber
1
Saya kira apa yang saya maksud di sini adalah bahwa di Jawa saya akan membuat menulis List<String> l = new ArrayList<String>()blog Scala akan membuat Anda percaya bahwa semua orang menggunakan Daftar untuk mendapatkan kebaikan koleksi persisten - tetapi apakah Vector bertujuan umum cukup bahwa kita harus menggunakannya di tempat Daftar?
Duncan McGregor
9
@ Debilski: Saya ingin tahu apa yang Anda maksud dengan itu. Saya mendapatkan Listketika saya mengetik Seq()di REPL.
missingfaktor
1
Hmm, well, katanya di dokumen. Mungkin ini hanya berlaku untuk IndexedSeq.
Debilski
1
Komentar mengenai jenis beton standar Seqadalah lebih dari tiga tahun. Pada Scala 2.11.4 (dan sebelumnya), tipe konkret default Seqadalah List.
Mark Canlas
3
Untuk akses acak, vektor lebih baik. Untuk akses head, tail, daftar lebih baik. Untuk operasi massal, seperti peta, filter, vektor lebih disukai karena vektor diatur dengan 32 elemen sebagai chunk sedangkan daftar mengatur elemen dengan pointer satu sama lain, tidak ada jaminan elemen ini dekat satu sama lain.
johnsam

Jawaban:

280

Sebagai aturan umum, standar untuk menggunakan Vector. Ini lebih cepat daripada Listuntuk hampir semua hal dan lebih hemat memori untuk urutan berukuran lebih dari sepele. Lihat dokumentasi kinerja relatif Vector ini dibandingkan dengan koleksi lainnya. Ada beberapa kelemahan untuk dilakukan Vector. Secara khusus:

  • Pembaruan di kepala lebih lambat dari List(meskipun tidak sebanyak yang Anda kira)

Kelemahan lain sebelum Scala 2.10 adalah bahwa dukungan pencocokan pola lebih baik untuk List, tetapi ini diperbaiki pada 2.10 dengan generalisasi +:dan :+ekstraktor.

Ada juga cara aljabar yang lebih abstrak untuk mendekati pertanyaan ini: urutan seperti apa yang secara konseptual Anda miliki? Juga, apa yang Anda lakukan secara konseptual dengannya? Jika saya melihat fungsi yang mengembalikanOption[A] , saya tahu fungsi itu memiliki beberapa lubang di domainnya (dan karenanya sebagian). Kita bisa menerapkan logika yang sama ini ke koleksi.

Jika saya memiliki urutan tipe List[A], saya secara efektif menegaskan dua hal. Pertama, algoritma saya (dan data) sepenuhnya terstruktur-tumpukan. Kedua, saya menegaskan bahwa satu-satunya hal yang akan saya lakukan dengan koleksi ini adalah penuh, O (n) traversal. Keduanya benar-benar berjalan seiring. Sebaliknya, jika saya memiliki sesuatu jenis Vector[A], satu - satunya hal yang saya tegaskan adalah bahwa data saya memiliki urutan yang jelas dan panjang yang terbatas. Dengan demikian, pernyataan lebih lemah Vector, dan ini mengarah pada fleksibilitas yang lebih besar.

Daniel Spiewak
sumber
2
2.10 telah keluar untuk sementara waktu sekarang, apakah pencocokan pola Daftar masih lebih baik daripada Vektor?
Tim Gautier
3
Pencocokan pola daftar tidak lagi lebih baik. Bahkan, itu justru sebaliknya. Misalnya, untuk mendapatkan kepala dan ekor yang dapat dilakukan case head +: tailatau case tail :+ head. Untuk mencocokkan dengan kosong, Anda dapat melakukan case Seq()dan sebagainya. Semua yang Anda butuhkan ada di API, yang lebih fleksibel daripada List's
Kai Sellgren
Listdiimplementasikan dengan daftar yang terhubung sendiri. Vectordiimplementasikan sesuatu seperti Java ArrayList.
Josiah Yoder
6
@JosiahYoder Diimplementasikan tidak seperti ArrayList. ArrayList membungkus array yang secara dinamis mengubah ukurannya. Vektor adalah trie , di mana kunci adalah indeks nilai.
John Colanduoni
1
Saya minta maaf. Saya menggunakan sumber web yang tidak jelas tentang detailnya. Haruskah saya memperbaiki pernyataan saya sebelumnya? Atau apakah itu bentuk buruk?
Josiah Yoder
93

Yah, a Listbisa sangat cepat jika algoritme hanya dapat diimplementasikan dengan ::, headdan tail. Saya mendapat pelajaran objek tentang hal itu baru-baru ini, ketika saya mengalahkan Java splitdengan menghasilkan Listbukan Array, dan tidak bisa mengalahkan itu dengan hal lain.

Namun, Listmemiliki masalah mendasar: tidak bekerja dengan algoritma paralel. Saya tidak dapat membagi Listmenjadi beberapa segmen, atau menggabungkannya kembali, secara efisien.

Ada beberapa koleksi lain yang dapat menangani paralelisme dengan lebih baik - dan Vectormerupakan salah satunya. Vectorjuga memiliki lokalitas besar - yang Listtidak - yang dapat menjadi nilai tambah nyata untuk beberapa algoritma.

Jadi, semua hal dipertimbangkan, Vectoradalah pilihan terbaik kecuali jika Anda memiliki pertimbangan khusus yang membuat salah satu koleksi lain lebih disukai - misalnya, Anda dapat memilih Streamjika Anda ingin evaluasi dan caching yang malas ( Iteratorlebih cepat tetapi tidak menembolok), atau Listjika Algoritma secara alami diimplementasikan dengan operasi yang saya sebutkan.

Ngomong-ngomong, lebih baik menggunakan Seqatau IndexedSeqkecuali Anda menginginkan bagian tertentu dari API (seperti Listitu ::), atau bahkan GenSeqatau GenIndexedSeqjika algoritma Anda dapat dijalankan secara paralel.

Daniel C. Sobral
sumber
3
Terima kasih atas jawabannya. Apa yang Anda maksud dengan "memiliki lokalitas yang bagus"?
Ngoc Dao
10
@ngocdaothanh Ini berarti bahwa data dikelompokkan dalam memori, meningkatkan kemungkinan data akan berada dalam cache saat Anda membutuhkannya.
Daniel C. Sobral
1
@ user247077 Ya, Daftar dapat mengalahkan Vektor dalam kinerja mengingat rincian yang saya sebutkan. Dan tidak semua aksi vektor diamortisasi O (1). Bahkan, pada struktur data yang tidak dapat diubah (yang merupakan kasusnya), penyisipan / penghapusan alternatif di kedua ujungnya tidak akan diamortisasi sama sekali. Dalam hal ini, cache tidak berguna karena Anda selalu menyalin vektor.
Daniel C. Sobral
1
@ user247077 Mungkin Anda tidak sadar bahwa itu Vectoradalah struktur data yang tidak berubah di Scala?
Daniel C. Sobral
1
@ user247077 Ini jauh lebih rumit dari itu, termasuk beberapa hal yang bisa berubah secara internal untuk membuat menambahkan lebih murah, tetapi ketika Anda menggunakannya sebagai tumpukan, yang merupakan daftar skenario optimal yang tetap, Anda masih memiliki karakteristik memori yang sama dari daftar yang ditautkan, tetapi dengan profil alokasi memori yang jauh lebih besar.
Daniel C. Sobral
29

Beberapa pernyataan di sini membingungkan atau bahkan salah, terutama gagasan yang tidak dapat diubah. Vektor di Scala mirip dengan ArrayList. Daftar dan Vektor keduanya tidak berubah, persisten (yaitu "murah untuk mendapatkan salinan yang dimodifikasi") struktur data. Tidak ada pilihan default yang masuk akal karena mereka mungkin untuk struktur data yang bisa berubah, tetapi lebih tergantung pada apa yang dilakukan algoritma Anda. Daftar adalah daftar yang ditautkan secara tunggal, sementara Vector adalah trie integer basis-32, yaitu jenis pohon pencarian dengan node derajat 32. Dengan menggunakan struktur ini, Vector dapat menyediakan operasi yang paling umum dengan cukup cepat, yaitu dalam O (log_32 ( n)). Itu berfungsi untuk prepend, append, update, akses acak, dekomposisi di head / tail. Iterasi dalam urutan berurutan adalah linear. Daftar di sisi lain hanya menyediakan iterasi linier dan waktu yang konstan, dekomposisi di kepala / ekor.

Ini mungkin terlihat seolah-olah Vector adalah pengganti yang baik untuk Daftar di hampir semua kasus, tetapi tergantung, dekomposisi dan iterasi sering merupakan operasi penting pada urutan dalam program fungsional, dan konstanta dari operasi ini (jauh) lebih tinggi untuk vektor karena untuk struktur yang lebih rumit. Saya membuat beberapa pengukuran, jadi iterasi sekitar dua kali lebih cepat untuk daftar, prepend sekitar 100 kali lebih cepat pada daftar, dekomposisi di kepala / ekor sekitar 10 kali lebih cepat pada daftar dan generasi dari yang dapat dilalui sekitar 2 kali lebih cepat untuk vektor. (Ini mungkin, karena Vector dapat mengalokasikan array 32 elemen sekaligus ketika Anda membangunnya menggunakan builder alih-alih menambahkan atau menambahkan elemen satu per satu).

Jadi struktur data mana yang harus kita gunakan? Pada dasarnya, ada empat kasus umum:

  • Kita hanya perlu mengubah urutan dengan operasi seperti peta, filter, lipat dll: pada dasarnya itu tidak masalah, kita harus memprogram algoritma kita secara umum dan bahkan mungkin mendapat manfaat dari menerima urutan paralel. Untuk operasi berurutan Daftar mungkin sedikit lebih cepat. Tetapi Anda harus membandingkannya jika Anda harus mengoptimalkan.
  • Kami membutuhkan banyak akses acak dan pembaruan yang berbeda, jadi kami harus menggunakan vektor, daftar akan sangat lambat.
  • Kami beroperasi pada daftar dengan cara fungsional klasik, membangunnya dengan menambahkan dan mengulangi dengan dekomposisi rekursif: daftar penggunaan, vektor akan lebih lambat oleh faktor 10-100 atau lebih.
  • Kami memiliki algoritme kinerja kritis yang pada dasarnya imperatif dan melakukan banyak akses acak pada daftar, sesuatu seperti quick-sort di tempat: gunakan struktur data imperatif, misalnya ArrayBuffer, secara lokal dan salin data Anda dari dan ke sana.
dth
sumber
24

Untuk koleksi yang tidak berubah, jika Anda menginginkan urutan, keputusan utama Anda adalah apakah akan menggunakan a IndexedSeqatau a LinearSeq, yang memberikan jaminan kinerja yang berbeda. IndexedSeq menyediakan akses acak cepat elemen dan operasi panjang cepat. LinearSeq menyediakan akses cepat hanya ke elemen pertama via head, tetapi juga memiliki tailoperasi cepat . (Diambil dari dokumentasi Seq.)

Untuk IndexedSeqAnda biasanya akan memilih a Vector. RangedanWrappedString s juga IndexedSeqs.

Untuk LinearSeqAnda biasanya akan memilih Listatau setara dengan malas Stream. Contoh lain adalah Queues dan Stacks.

Jadi dalam istilah Jawa, ArrayListdigunakan mirip dengan Scala Vector, dan LinkedListmirip dengan Scala List. Tetapi dalam Scala saya cenderung menggunakan Daftar lebih sering daripada Vektor, karena Scala memiliki dukungan yang jauh lebih baik untuk fungsi-fungsi yang mencakup melintasi urutan, seperti pemetaan, lipat, iterasi dll. Anda akan cenderung menggunakan fungsi-fungsi ini untuk memanipulasi daftar sebagai keseluruhan, daripada mengakses elemen individual secara acak.

Luigi Plinge
sumber
Tetapi jika iterasi Vector lebih cepat daripada List, dan saya dapat memetakan flip dll juga, maka terlepas dari beberapa kasus khusus (pada dasarnya semua algoritma FP yang dikhususkan untuk Daftar) tampaknya List pada dasarnya adalah warisan.
Duncan McGregor
@Duncan di mana Anda pernah mendengar bahwa pengulangan Vector lebih cepat? Sebagai permulaan, Anda perlu melacak dan memperbarui indeks saat ini, yang Anda tidak perlu dengan daftar tertaut. Saya tidak akan menyebut fungsi daftar "kasus khusus" - mereka adalah roti dan mentega dari pemrograman fungsional. Tidak menggunakannya sama dengan mencoba memprogram Java tanpa for atau while loop.
Luigi Plinge
2
Aku cukup yakin Vector's iterasi adalah lebih cepat, tapi seseorang kebutuhan untuk patokan itu untuk memastikan.
Daniel Spiewak
Saya pikir (?) Elemen-elemen secara Vectorfisik ada bersama-sama di RAM dalam kelompok 32, yang lebih sepenuhnya sesuai dalam cache CPU ... jadi ada lebih sedikit cache miss
richizy
2

Dalam situasi yang melibatkan banyak akses acak dan mutasi acak, a Vector(atau - seperti kata dokumen - a Seq) tampaknya merupakan kompromi yang baik. Ini juga yang disarankan karakteristik kinerja .

Juga, Vectorkelas tampaknya bermain dengan baik di lingkungan terdistribusi tanpa banyak duplikasi data karena tidak perlu melakukan copy-on-write untuk objek lengkap. (Lihat: http://akka.io/docs/akka/1.1.3/scala/stm.html#persistent-datastructures )

Debilski
sumber
1
Begitu banyak yang harus dipelajari ... Apa arti vektor sebagai Seq default? Jika saya menulis Seq (1, 2, 3) saya mendapatkan Daftar [Int] bukan Vektor [Int].
Duncan McGregor
2
Jika Anda memiliki akses acak, gunakan a IndexedSeq. Yang juga Vector, tapi itu masalah lain.
Daniel C. Sobral
@DuncanMcGregor: Vektor adalah default IndexedSeqyang mengimplementasikan Seq. Seq(1, 2, 3)adalah LinearSeqyang diimplementasikan menggunakan List.
pathikrit
0

Jika Anda sedang pemrograman dan membutuhkan akses acak, Seq adalah cara untuk pergi (kecuali Anda menginginkan Set, yang sering Anda lakukan). Kalau tidak, Daftar berfungsi dengan baik, kecuali operasinya tidak dapat diparalelkan.

Jika Anda tidak memerlukan struktur data yang tidak dapat diubah, tetap menggunakan ArrayBuffer karena itu adalah Scala yang setara dengan ArrayList.

Joshua Hartman
sumber
Saya berpegang teguh pada ranah koleksi abadi dan tak berkesudahan. Maksud saya adalah, bahwa bahkan jika saya tidak memerlukan akses acak, apakah Vector telah secara efektif menggantikan List?
Duncan McGregor
2
Tergantung sedikit pada use case. Vektor lebih seimbang. Iterasi lebih cepat dari daftar dan akses acak jauh lebih cepat. Pembaruan lebih lambat karena itu bukan hanya daftar prepend, kecuali pembaruan massal dari flip yang dapat dilakukan dengan pembangun. Yang mengatakan, saya pikir Vector adalah pilihan default terbaik karena sangat fleksibel.
Joshua Hartman
Yang saya pikir sampai ke inti pertanyaan saya - Vektor sangat baik sehingga kita bisa menggunakannya di mana contoh biasanya menunjukkan Daftar.
Duncan McGregor