Ada banyak opsi saat menerapkan antrian di JavaScript. Salah satu implementasi yang mungkin adalah dengan menggunakan Array, menambahkan elemen ke antrian dengan Array.push dan menghapusnya dari antrian dengan Array.shift. Implementasi lain yang mungkin adalah dengan menggunakan Linked List dan menambahkan ke ekor dan menghapus dari kepala.

Melalui pengujian untuk implementasi Stacks, saya telah menentukan bahwa Array.push dan Array.pop, berapa pun ukuran Arraynya, 3-5 kali lebih cepat daripada menambahkan atau menghapus elemen ke ekor Linked List. Oleh karena itu, dalam JavaScript, tidak masuk akal untuk menggunakan Daftar Tertaut untuk mengimplementasikan tumpukan. Tapi saya bertanya-tanya, dalam kasus Antrian, apa perbedaan kinerja saat menghapus elemen dari depan array menggunakan Array.shift vs menghapus elemen dari depan daftar?

0
snowfrogdev 2 Januari 2018, 19:05

1 menjawab

Jawaban Terbaik

Pengujian berjalan di Chrome v63, di Windows 10.

Koleksi 50.000 elemen atau kurang
Array.shift 38%-40% lebih lambat dari operasi yang setara pada Daftar Tertaut.

Koleksi lebih dari 50.000 elemen
Array.shift pada dasarnya 100% lebih lambat dari operasi yang setara pada Daftar Tertaut.

Kesimpulan dan rekomendasi
Array.shift, bahkan pada array kecil, lebih lambat daripada di Daftar Tertaut, tetapi jika semua yang harus Anda lakukan adalah sedikit menambah atau menghapus operasi di sana-sini, hit kinerja mungkin tidak cukup signifikan untuk menjamin penerapan Daftar Tertaut. Pergi dengan Array. Di sisi lain, jika Anda memiliki koleksi lebih dari 50 ribu elemen atau sering menambah dan menghapus item dalam jumlah besar, mungkin ada baiknya menerapkan Daftar Tertaut.

Sangat menarik untuk melihat bahwa V8 jelas menerapkan beberapa pengoptimalan di belakang layar untuk membuat Array.shift lebih cepat, tetapi pengoptimalan itu tampaknya hanya diterapkan pada Array berukuran 50.000 atau kurang. Lihat saja tes benchmark ini, cukup jelas: https://jsperf.com/likedlistvsarray/1

3
snowfrogdev 2 Januari 2018, 16:05