O besar array JavaScript

Array dalam JavaScript sangat mudah dimodifikasi dengan menambah dan menghapus item. Ini agak menutupi fakta bahwa kebanyakan array bahasa berukuran tetap, dan membutuhkan operasi kompleks untuk mengubah ukurannya. Tampaknya JavaScript mempermudah penulisan kode array yang berperforma buruk. Ini mengarah pada pertanyaan:

Kinerja apa (dalam hal kompleksitas waktu O besar) yang dapat saya harapkan dari implementasi JavaScript terkait dengan kinerja array?

Saya berasumsi bahwa semua implementasi JavaScript yang masuk akal memiliki paling banyak O besar berikut.

• Akses - O (1)
• Menambahkan - O (n)
• Mempersiapkan - O (n)
• Penyisipan - O (n)
• Penghapusan - O (n)
• Swapping - O (1)

JavaScript memungkinkan Anda mengisi array ke ukuran tertentu, menggunakan new Array(length) sintaks. (Pertanyaan bonus: Apakah membuat larik dengan cara ini O (1) atau O (n)) Ini lebih seperti larik konvensional, dan jika digunakan sebagai larik berukuran sebelumnya, dapat memungkinkan O (1) menambahkan. Jika logika buffer melingkar ditambahkan, Anda dapat mencapai O (1) prepending. Jika array yang berkembang secara dinamis digunakan, O (log n) akan menjadi kasus rata-rata untuk keduanya.

Dapatkah saya mengharapkan kinerja yang lebih baik untuk beberapa hal daripada asumsi saya di sini? Saya tidak berharap ada yang diuraikan dalam spesifikasi apa pun, tetapi dalam praktiknya, bisa jadi semua implementasi utama menggunakan array yang dioptimalkan di belakang layar. Apakah ada larik yang berkembang secara dinamis atau beberapa algoritme peningkatan kinerja lainnya yang bekerja?

PS

Alasan saya bertanya-tanya ini adalah karena saya sedang meneliti beberapa algoritme pengurutan, yang sebagian besar berasumsi bahwa menambahkan dan menghapus adalah operasi O (1) saat menjelaskan O besar mereka secara keseluruhan.

_{CATATAN: Meskipun jawaban ini benar pada tahun 2012, mesin menggunakan representasi internal yang sangat berbeda untuk objek dan larik saat ini. Jawaban ini mungkin benar atau mungkin tidak benar.}

Berbeda dengan kebanyakan bahasa, yang mengimplementasikan array dengan, yah, array, di Javascript Array adalah objek, dan nilai disimpan dalam hashtable, seperti nilai objek biasa. Dengan demikian:

• Akses - O (1)
• Menambahkan - Amortisasi O (1) (terkadang mengubah ukuran hashtable diperlukan; biasanya hanya penyisipan yang diperlukan)
• Mempersiapkan - O (n) lewat unshift, karena memerlukan penugasan ulang semua indeks
• Penyisipan - Amortisasi O (1) jika nilainya tidak ada. O (n) jika Anda ingin menggeser nilai yang ada (Misalnya, menggunakan splice).
• Penghapusan - Amortisasi O (1) untuk menghapus nilai, O (n) jika Anda ingin menetapkan kembali indeks melalui splice.
• Swapping - O (1)

Secara umum, menyetel atau menghapus kunci apa pun dalam sebuah dict adalah diamortisasi O (1), dan hal yang sama berlaku untuk array, apa pun indeksnya. Setiap operasi yang membutuhkan penomoran ulang nilai yang ada adalah O (n) hanya karena Anda harus memperbarui semua nilai yang terpengaruh.

menjamin

Tidak ada jaminan kompleksitas waktu yang ditentukan untuk operasi array apa pun. Cara kerja array bergantung pada struktur data dasar yang dipilih mesin. Mesin mungkin juga memiliki representasi yang berbeda, dan beralih di antara keduanya bergantung pada heuristik tertentu. Ukuran array awal mungkin atau mungkin tidak seperti heuristik.

realitas

Misalnya, V8 menggunakan (mulai hari ini) baik hashtable dan daftar array untuk mewakili array. Ia juga memiliki berbagai representasi yang berbeda untuk objek, sehingga array dan objek tidak dapat dibandingkan. Oleh karena itu, akses array selalu lebih baik dari O (n), dan bahkan mungkin secepat akses array C ++. Menambahkan adalah O (1), kecuali Anda mencapai ukuran struktur data dan itu harus diskalakan (yaitu O (n)). Mempersiapkan lebih buruk. Penghapusan bisa menjadi lebih buruk jika Anda melakukan sesuatu seperti delete array[index](jangan!), Karena itu mungkin memaksa mesin untuk mengubah representasi itu.

nasihat

Gunakan array untuk struktur data numerik. Itulah tujuan mereka. Untuk itulah mesin akan mengoptimalkannya. Hindari sparse array (atau jika harus, mengharapkan kinerja yang lebih buruk). Hindari array dengan tipe data campuran (karena itu membuat representasi internal lebih kompleks ).

Jika Anda benar-benar ingin mengoptimalkan mesin (dan versi) tertentu, periksa kode sumbernya untuk jawaban mutlak.