Hierarki koleksi

Seq, Set, Map, dan Vector pada pustaka bawaan immutable beserta pertimbangan pemilihannya.

Daftar isi

Pustaka bawaan Scala menyediakan tiga keluarga koleksi (collection), yaitu Seq untuk barisan elemen berurutan, Set untuk himpunan tanpa duplikat, dan Map untuk pasangan kunci-nilai. Topik ini memperkenalkan hierarki versi immutable, yakni struktur yang isinya tidak dapat diubah setelah dibuat, beserta perilaku literal koleksi secara default, biaya operasi utama setiap jenis, dan konversi di antara koleksi-koleksi tersebut. Setelah membacanya, pemilihan List, Vector, Set, atau Map untuk sebuah kebutuhan dapat ditentukan dengan dasar yang jelas.

Tiga keluarga besar: Seq, Set, dan Map#

Ketiga keluarga berada di bawah satu leluhur yang sama, yaitu scala.collection.Iterable, sehingga operasi umum seperti foreach, size, dan isEmpty tersedia di semua koleksi. Perbedaannya terletak pada jaminan yang diberikan masing-masing keluarga terhadap isinya.

Seq menjamin urutan elemen, sehingga posisi setiap elemen bermakna dan elemen dapat diakses melalui indeks. Dua implementasi yang paling sering digunakan adalah List dan Vector. Set hanya menyimpan satu salinan untuk setiap nilai yang sama, sedangkan urutan iterasinya tidak dijamin mengikuti urutan penyisipan. Map menyimpan pasangan kunci-nilai dengan kunci yang unik, sehingga sebuah kunci menghasilkan tepat satu nilai.

Pada pustaka immutable, metode yang tampak mengubah koleksi sebenarnya mengembalikan koleksi baru, sedangkan koleksi lama tetap utuh. Sifat ini membuat satu koleksi dapat dibagikan dengan aman ke banyak bagian program tanpa risiko isinya berubah secara tidak sengaja. Diagram berikut merangkum posisi keempat jenis yang paling sering digunakan.

Hierarki utama pustaka koleksi immutable bawaan Scala

Pustaka bawaan yang immutable secara default#

Objek Predef yang otomatis tersedia pada setiap berkas Scala memuat alias untuk koleksi immutable. Penulisan List, Vector, Set, dan Map tanpa impor apa pun menunjuk ke scala.collection.immutable.List dan seterusnya, sehingga kode paling ringkas sekaligus memilih versi immutable. Versi mutable tetap tersedia di scala.collection.mutable, tetapi penggunaannya menuntut impor eksplisit, sehingga setiap pilihan yang memungkinkan mutasi tampak jelas di dalam kode.

Program berikut membuat satu koleksi dari setiap keluarga lalu mencetaknya. Isi Set dan Map diurutkan lebih dahulu dengan toSeq.sorted dan toSeq.sortBy(_._1) karena urutan iterasi HashSet dan HashMap tidak dijamin, sedangkan urutan List dan Vector dijamin oleh definisi Seq.

scala hierarki.scala

// Empat koleksi immutable bawaan: List, Vector, Set, dan Map
@main def hierarki(): Unit =
  val nilai: List[Int] = List(72, 85, 90)
  val titik: Vector[(Int, Int)] = Vector((0, 0), (3, 4), (6, 8))
  val terdaftar: Set[String] = Set("Ali", "Budi", "Citra")
  val skor: Map[String, Int] = Map("Ali" -> 88, "Budi" -> 79)

  println(nilai)
  println(titik)
  println(terdaftar.toSeq.sorted)
  println(skor.toSeq.sortBy(_._1))

bash

# menjalankan program hierarki.scala
scala-cli run hierarki.scala

text Keluaran

List(72, 85, 90)
Vector((0,0), (3,4), (6,8))
List(Ali, Budi, Citra)
List((Ali,88), (Budi,79))

Keluaran memperlihatkan perilaku masing-masing keluarga. List dan Vector dicetak apa adanya menurut urutan penyimpanannya, sedangkan Set dan Map ditampilkan sebagai barisan yang sudah diurutkan karena pencetakan dilakukan setelah konversi ke Seq. Anotasi tipe pada setiap val juga menegaskan jenis koleksi yang sedang dipegang, bukan sekadar isinya.

Biaya operasi utama dan pemilihan koleksi#

Setiap jenis koleksi unggul pada operasi yang berbeda, sehingga pemilihannya sebaiknya mengikuti pola akses program. Tabel berikut merangkum biaya operasi yang paling sering menjadi pertimbangan pada versi immutable. Notasi $O(n)$ dan $O(\log n)$ menyatakan kelas kompleksitas terhadap jumlah elemen $n$ , dan $O(\log n)$ pada Vector berbasis 32 sehingga hampir tidak dapat dibedakan dari konstan pada ukuran data sehari-hari.

Operasi	`List`	`Vector`	`Set`	`Map`
Akses elemen pertama	konstan	konstan	tidak berlaku	tidak berlaku
Akses menurut indeks	$O(n)$	$O(\log n)$	tidak berlaku	tidak berlaku
Penambahan di depan	konstan	$O(\log n)$	tidak berlaku	tidak berlaku
Keanggotaan atau pencarian kunci	$O(n)$	$O(n)$	$O(\log n)$	$O(\log n)$

Aturan praktisnya dapat dirangkum sebagai berikut. List dipilih apabila program memproses elemen dari depan, misalnya menumpuk data melalui :: lalu memindainya secara berurutan. Vector dipilih apabila akses menurut indeks sering terjadi atau penambahan berlangsung di kedua ujung. Set dipilih apabila keunikan dan pemeriksaan keanggotaan menjadi kebutuhan utama, sedangkan Map dipilih apabila nilai dicari menurut kuncinya. Apabila kebutuhannya campuran, Vector umumnya menjadi pilihan netral yang baik pada pustaka immutable.

Konversi antarkoleksi#

Karena setiap keluarga memiliki keunggulan yang berbeda, pustaka bawaan menyediakan konversi eksplisit berupa toList, toVector, toSet, dan toMap. Konversi ini menyalin struktur ke jenis tujuan, sehingga biayanya sebanding dengan jumlah elemen. Di antara konversi tersebut, toSet memiliki efek tambahan berupa penyusutan duplikat karena Set tidak menyimpan nilai yang sama dua kali.

Program berikut mengonversi sebuah List yang memuat nilai ganda ke Vector dan Set, lalu mengonversinya kembali.

scala konversi.scala

// Konversi antarkoleksi dengan toList, toVector, dan toSet
@main def konversi(): Unit =
  val nilai: List[Int] = List(72, 85, 90, 72)

  val vektor: Vector[Int] = nilai.toVector
  val unik: Set[Int] = nilai.toSet
  val kembali: List[Int] = vektor.toList

  println(vektor)
  println(unik.toSeq.sorted)
  println(kembali)

bash

# menjalankan program konversi.scala
scala-cli run konversi.scala

text Keluaran

Vector(72, 85, 90, 72)
List(72, 85, 90)
List(72, 85, 90, 72)

Nilai 72 yang muncul dua kali pada List menyusut menjadi satu setelah toSet, dan baris pertama beserta baris ketiga menunjukkan bahwa Vector maupun List mempertahankan seluruh elemen termasuk duplikatnya. Dengan demikian, penyusutan duplikat terjadi hanya karena pilihan jenis koleksi tujuan, bukan karena operasi terpisah yang perlu ditulis sendiri.

Ringkasan#

Pustaka bawaan Scala menyediakan tiga keluarga koleksi immutable, yaitu Seq, Set, dan Map, dengan List dan Vector sebagai implementasi Seq yang utama.
Literal List, Set, dan Map tanpa impor menunjuk ke versi scala.collection.immutable melalui alias Predef, sehingga operasi pengubahan menghasilkan koleksi baru.
List cepat pada operasi di depan dan lambat pada akses indeks, Vector efektif konstan untuk indeks, sedangkan Set dan Map unggul untuk keanggotaan dan pencarian kunci.
toList, toVector, dan toSet mengonversi antarjenis dengan biaya yang sebanding dengan jumlah elemen, dan toSet sekaligus menyusutkan duplikat.

Referensi#

Collections Overview — Scala Documentation — Ringkasan arsitektur dan hierarki pustaka koleksi Scala yang berlaku juga pada Scala 3.
Performance Characteristics — Scala Documentation — Tabel biaya operasi setiap koleksi immutable yang menjadi dasar tabel di atas.
List — Scala Standard Library — Dokumentasi API List immutable pada pustaka baku 3.x.
Vector — Scala Standard Library — Dokumentasi API Vector immutable pada pustaka baku 3.x.