Array dinamis

Array statis menuntut ukuran yang diputuskan di awal, sedangkan kebutuhan nyata jarang bisa ditebak seketat itu. Array dinamis menyelesaikan ketegangan itu dengan mengatur kapasitas di belakang layar, menggandakan area penyimpanan setiap kali penuh, dan terus menampung elemen baru tanpa terkendala batas ukuran. Topik ini membedah mekanisme penggandaan tersebut, menghitung total salinannya lewat simulasi dari nol, lalu membuktikan bahwa biaya rata-rata satu append tetap $O(1)$.

Kenapa array statis terasa sempit#

Panjang array int[] pada Java terkunci sejak dibuat, dan penuhnya tidak terlihat dari luar sampai penulisan elemen berikutnya gagal. Mengatur ukuran secara manual berarti mengulang resep yang sama setiap kali kapasitas terlampaui, yaitu mengalokasikan array baru, menyalin seluruh isi, lalu meninggalkan array lama. Kebutuhan seperti daftar nilai ujian yang jumlahnya baru diketahui setelah semua berkas terbaca menjadikan pola ini melelahkan dan rawan salah.

List Python dan ArrayList Java mengambil alih pekerjaan tersebut. Keduanya menyimpan data dalam array biasa yang kapasitasnya lebih besar dari jumlah elemen yang terlihat, lalu mengatur perluasan secara otomatis ketika ruang habis. Dari luar, penambahannya terasa tanpa biaya, nilai.append(50) selesai dalam satu baris tanpa kekhawatiran kapasitas. Yang perlu dipahami bukan cara memakainya, melainkan harganya, karena kerja yang tersembunyi itu tetap dibayar dan sesekali terasa.

Mekanisme penggandaan kapasitas#

Operasi paling sering pada array dinamis adalah append, menambah satu elemen di ujung. Selama kapasitas masih tersisa, append hanyalah menulis satu sel lalu menaikkan penghitung ukuran, biayanya $O(1)$. Saat array penuh, terjadi resize, yaitu array baru yang lebih besar dialokasikan, seluruh isi lama disalin, lalu array lama dibuang. Penghitung salinan pada ekspansi itu menjadi satu-satunya biaya tersembunyi yang perlu ditelusuri.

Penggandaan kapasitas (doubling), yaitu kapasitas yang bergerak melalui 1, 2, 4, 8, dan seterusnya, menjadi pilihan klasik karena mudah dianalisis. Angka penggandanya bukan satu-satunya pilihan, karena Java menaikkan kapasitas ArrayList sekitar 1,5 kali lipat dan Python memakai faktor pertumbuhan yang lebih kecil. Analisis di bawah memakai penggandaan penuh karena perhitungannya paling bersih, dan kesimpulannya berlaku untuk setiap faktor pertumbuhan yang konstan. Kuncinya satu, ekspansi semakin jarang seiring array bertambah besar, karena kapasitas yang tersisa ikut melipat ganda.

Menghitung salinan secara nyata#

Klaim tentang efisiensi sebaiknya tidak diambil mentah-mentah, karena salinan di balik layar tidak terlihat dari pemanggilannya. Simulasi berikut meniru array dinamis dari nol dengan array tetap sebagai area penyimpanan, tanpa bergantung pada perilaku internal list Python, lalu menghitung setiap elemen yang tersalin saat ekspansi.

"""Simulasi array dinamis: kapasitas digandakan setiap kali penuh."""

kapasitas = 4                    # banyak slot yang disediakan array
ukuran = 0                       # banyak slot yang benar-benar terisi
total_salin = 0                  # penghitung salinan saat pindah ke array baru

data = [0] * kapasitas           # area penyimpanan tetap dari awal

for nilai in range(1, 21):       # append 20 elemen satu per satu
    if ukuran == kapasitas:      # penuh: pindah ke array dua kali lebih besar
        kapasitas *= 2
        data_baru = [0] * kapasitas
        for i in range(ukuran):  # setiap elemen lama disalin sekali
            data_baru[i] = data[i]
        total_salin += ukuran
        data = data_baru
    data[ukuran] = nilai         # elemen baru diletakkan di slot kosong
    ukuran += 1

print("ukuran akhir    :", ukuran)
print("kapasitas akhir :", kapasitas)
print("total salinan   :", total_salin)

ukuran akhir    : 20
kapasitas akhir : 32
total salinan   : 28

Menambahkan 20 elemen hanya memicu tiga ekspansi, yaitu saat ukuran menyentuh 4, 8, dan 16, dengan total 28 salinan. Angka 28 memang lebih besar dari 20, tetapi jauh di bawah 190 salinan yang akan terjadi bila array baru berukuran tambah satu dialokasikan pada setiap append. Penggandaan memastikan salinan tidak pernah mendekati kuadrat ukuran, dan setiap elemen yang sudah ada paling banyak disalin beberapa kali sepanjang hidupnya.

Analisis amortisasi#

Cara menghitung biaya pola murah-murah-mahal seperti ini disebut analisis amortisasi (amortized analysis), yaitu menghitung biaya rata-rata per operasi di atas seluruh rangkaian operasi, bukan pada satu operasi saja. Selama $n$ append dengan penggandaan, ekspansi menyalin array berukuran $1, 2, 4, \ldots, 2^k$ dengan $2^k < n$, sehingga total salinannya membentuk deret geometri berikut.

Total salinan selama $n$ append jadi kurang dari $2n$, dan ditambah $n$ penulisan append itu sendiri, seluruh rangkaian tetap selesai dalam $O(n)$. Rata-ratanya mendekati konstanta, itulah yang dinyatakan sebagai append beramortisasi $O(1)$. Biaya mahal ekspansi dibayar jarang, dan bebannya terdistribusi ke seluruh append murah yang mendahuluinya.

Kasus terburuk satu append tetap $O(n)$ karena ekspansi, dan pada sistem yang peka jeda seperti pemrosesan sinyal waktu-nyata, fluktuasi ini harus diperhitungkan. Salah satu penangkalnya adalah memesan kapasitas di awal saat ukurannya sudah kira-kira diketahui, misalnya [0] * n di Python atau new ArrayList<>(n) di Java. Dengan kapasitas awal yang memadai, ekspansi bahkan tidak perlu terjadi.

list Python dan ArrayList Java#

Kedua bahasa memaketkan array dinamis sebagai struktur siap pakai. Demo berikut membandingkan operasi di ujung dengan operasi di tengah pada list Python.

# append di ujung versus insert di tengah
nilai = [10, 20, 30, 40]
nilai.append(50)         # menambah di ujung, biasanya selesai dalam satu langkah
nilai.insert(1, 15)      # menyisipkan di tengah, elemen setelahnya digeser
print("list akhir:", nilai)

list akhir: [10, 15, 20, 30, 40, 50]

Tabel berikut merangkum biaya operasinya pada ketiga wujud array yang sudah dibahas dalam modul ini.

Kolom pertama menjadi pengingat bahwa kenyamanan list dibayar dengan lapisan pengelolaan. Untuk data numerik besar yang ukurannya sudah pasti di Java, int[] tetap lebih ringan daripada ArrayList<Integer> karena tidak ada pembungkus objek dan tidak ada ekspansi. Pemilihan strukturnya bukan soal mana yang unggul mutlak, melainkan kecocokan pola akses dengan biaya yang sudah dihitung di atas.

Ringkasan#

• Array dinamis adalah array plus kapasitas dan penghitung ukuran, dengan ekspansi yang menggandakan kapasitas lalu menyalin seluruh isi.
• Total salinan sepanjang $n$ append membentuk deret geometri yang jumlahnya kurang dari $2n$, sehingga biaya rata-ratanya $O(1)$ per append.
• Kasus terburuk satu append tetap $O(n)$ saat ekspansi, dan kapasitas awal yang memadai menangkalnya.
• list Python dan ArrayList Java menyediakan paket ini siap pakai, sementara biaya sisip di tengah tetap $O(n)$ pada semuanya.

Referensi#

• Dynamic array — Wikipedia — mekanisme penggandaan dan variasi faktor pertumbuhan antar implementasi.
• Amortized analysis — Wikipedia — definisi analisis amortisasi beserta contoh klasik array dinamisnya.
• ArrayList — Oracle — dokumentasi kelas ArrayList, termasuk jaminan waktu add yang amortisasi konstan.
• Data Structures — Python Software Foundation — dokumentasi list sebagai struktur yang tumbuh otomatis.