Array

Membaca nilai kesejuta dalam array butuh satu langkah, tetapi menaruh nilai baru di depan array yang sama memindahkan sejuta nilai.

Apa itu struktur data

Program yang menyimpan daftar nama, antrean pekerjaan cetak, atau tabel harga harus menyimpan data itu di suatu tempat, dan harus bisa menjawab pertanyaan tentangnya: apa butir ketiga, apakah nama ini ada di daftar, pekerjaan mana yang berikutnya? Struktur data adalah cara menyimpan data bersama metode-metode yang menjawab pertanyaan itu. Mata kuliah 6.006 MIT memisahkan dua gagasan di sini. Antarmuka (interface) menyatakan operasi apa saja yang bisa kamu minta, seperti "ambil butir di posisi i" atau "tambahkan butir di ujung". Struktur data adalah cara operasi itu benar-benar dijalankan di memori. Satu antarmuka bisa punya beberapa struktur data di belakangnya, dan kecepatannya bisa sangat berbeda.

Kursus ini menghitung langkah, seperti kursus algoritma, supaya dua struktur bisa dibandingkan tanpa stopwatch. Di unit ini, satu langkah adalah membaca atau menulis satu sel memori. Laboratorium di bawah menghitungnya untukmu.

Satu blok sel, berdampingan

Array menyimpan nilai-nilainya dalam satu blok memori yang tidak terputus, setiap nilai dalam sel berukuran sama, diberi nomor mulai dari 0. Tata letak inilah yang membuat array cepat dibaca. Kalau blok dimulai di alamat s dan setiap sel memakan c byte, maka a[i] berada di alamat s + i × c. Komputer menghitungnya dengan satu perkalian dan satu penjumlahan lalu langsung melompat ke sana, entah i bernilai 3 atau 3 000 000. Catatan MIT mencantumkan "get at(i)" dan "set at(i, x)" untuk array sebagai Θ(1), artinya biayanya tidak bertambah seiring panjang array.

Tata letak yang sama membuat perubahan di tengah menjadi lambat. Misalkan array berisi 7, 3, 9, 4, 6 dan kamu ingin menaruh 1 di depan. Tidak ada celah di depan 7, jadi setiap nilai harus lebih dulu bergeser satu sel ke kanan, dimulai dari yang terakhir supaya tidak ada yang tertimpa. Itu 5 pemindahan dan 1 penulisan: 6 langkah. Menghapus nilai terdepan adalah kebalikannya: baca nilainya, lalu geser 4 nilai lainnya satu sel ke kiri. Menyisipkan di posisi i dalam array berisi n nilai memakan n − i pemindahan ditambah satu penulisan, jadi bagian depan adalah tempat terburuk dan ujung adalah tempat terbaik.

Saat bloknya penuh

Blok memori punya ukuran tetap, jadi apa yang terjadi kalau kamu menambahkan nilai padahal setiap sel sudah terisi? Array harus meminta blok baru yang lebih besar dan menyalin setiap nilai ke sana sebelum bisa menulis nilai baru. Di laboratorium, push ke blok penuh berisi 5 memakan 5 penyalinan dan 1 penulisan. Kalau array hanya bertambah satu sel setiap kali, setiap push akan menyalin semuanya, dan n kali push akan memakan sekitar n²/2 penyalinan.

Perbaikan yang dijelaskan catatan MIT adalah memperbesar banyak sekaligus, misalnya dengan menggandakan. Mulai dari kapasitas 1, penyalinan terjadi saat array berisi 1, 2, 4, 8, dan 16 nilai, jadi 17 kali push memakan total 1 + 2 + 4 + 8 + 16 = 31 penyalinan, kurang dari 2 per push. Satu push tertentu tetap bisa lambat, tetapi serangkaian panjang push rata-rata memakan biaya konstan per push. Ini disebut waktu Θ(1) teramortisasi (amortized). Array JavaScript berperilaku seperti ini dari luar: MDN menyebut array dapat diubah ukurannya, dan push serta pop bekerja di ujung, yaitu ujung yang murah.

const a = [7, 3, 9, 4, 6];
console.log(a[3]);      // 4, satu langkah
a.push(8);              // murah: ujung
a.unshift(1);           // setiap nilai bergeser satu sel ke kanan
console.log(a.join(" ")); // 1 7 3 9 4 6 8