Tampaknya selalu ada kesalahpahaman di lingkaran front-end: front-end tidak dapat menggunakan pengetahuan algoritma. Untuk waktu yang lama, semua orang mungkin telah dipengaruhi oleh pernyataan ini. Sampai saya menemukan permintaan produk beberapa waktu yang lalu, saya melihat ke belakang dan menemukan bahwa ini bukan masalahnya.
Penyortiran front-end
Skenario penyortiran front-end
Front-end meneruskan kondisi penyortiran ke back-end sebagai parameter permintaan, dan back-end mengembalikan hasil penyortiran sebagai respons permintaan ke front-end, yang merupakan desain umum. Tapi itu tidak cocok untuk beberapa produk.
Bayangkan sebuah skenario: Ketika Anda menggunakan aplikasi makanan, apakah Anda sering mengganti metode penyortiran, mengurutkannya berdasarkan harga, dan kemudian mengurutkan berdasarkan peringkat.
Dalam produksi aktual, karena faktor-faktor seperti biaya server, ketika satu kueri data menjadi hambatan kinerja keseluruhan, ia juga dianggap mengoptimalkan kinerja dengan mengurutkannya di front-end.
Algoritma penyortiran
Saya merasa tidak perlu memperkenalkan ini. Sebagai algoritma dasar dalam ilmu komputer, deskripsi akan disalin langsung dari Wikipedia .
Paragraf ini ada di sini murni untuk tujuan mewarisi yang pertama (manusia) dan yang kedua (SHU).
Penyortiran JavaScript
Karena kita berbicara tentang penyortiran front-end, kita secara alami akan memikirkan Array.prototype.sort antarmuka asli Javascript.prototype.sort.
Antarmuka ini telah ada sejak ECMAScript 1st Edition . Mari kita lihat seperti apa deskripsi itu dalam spesifikasi terbaru.
Spesifikasi array.prototype.sort
Array.prototype.sort(compareFn)
Salinan kode adalah sebagai berikut:
Elemen -elemen dari array ini diurutkan. Jenisnya tidak perlu stabil (yaitu, elemen yang membandingkan sama tidak harus tetap dalam urutan aslinya). Jika dibandingkan tidak tidak terdefinisi, itu harus menjadi fungsi yang menerima dua argumen x dan y dan mengembalikan nilai negatif jika x <y, nol jika x = y, atau nilai positif jika x> y.
Jelas, spesifikasinya tidak membatasi apa yang diimplementasikan oleh algoritma sort secara internal. Bahkan implementasi antarmuka tidak perlu diurutkan yang stabil . Ini sangat penting dan akan terlibat berkali -kali berikutnya.
Dalam konteks ini, penyortiran front-end sebenarnya tergantung pada implementasi spesifik dari setiap browser. Jadi, bagaimana browser arus utama menerapkan penyortiran? Selanjutnya, kami masing -masing membandingkan Chrome , Firefox , dan Microsoft Edge secara singkat.
Implementasi di Chrome
Mesin JavaScript Chrome adalah V8. Karena ini adalah open source, Anda dapat melihat kode sumber secara langsung.
Seluruh array.js diimplementasikan dalam bahasa JavaScript. Bagian metode penyortiran jelas jauh lebih rumit daripada jenis cepat yang saya lihat, tetapi jelas algoritma inti masih cepat menyortir. Alasan untuk algoritma yang kompleks adalah bahwa V8 telah membuat banyak optimasi untuk pertimbangan kinerja. (Saya akan membicarakannya selanjutnya)
Implementasi di Firefox
Tidak mungkin untuk menentukan apa algoritma penyortiran array yang akan digunakan oleh mesin JavaScript Firefox. [3]
Menurut informasi yang ada, Spidermoney mengimplementasikan penyortiran secara internal.
Implementasi di Microsoft Edge
Bagian inti dari kode untuk chakra mesin JavaScript dari Microsoft Edge dibuka bersumber di GitHub pada awal 2016.
Dengan melihat kode sumber, kita dapat menemukan bahwa algoritma penyortiran array Chakra juga mengimplementasikan penyortiran cepat. Dan dibandingkan dengan V8, itu hanya mengimplementasikan penyortiran murni cepat, tanpa jejak optimasi kinerja di V8 sama sekali.
Masalah dengan penyortiran array javascript
Seperti yang kita semua tahu, penyortiran cepat adalah algoritma penyortiran yang tidak stabil, sementara penggabungan penyortiran adalah algoritma penyortiran yang stabil. Karena perbedaan dalam pemilihan algoritma dari mesin yang berbeda, front-end bergantung pada kode JavaScript yang diimplementasikan oleh antarmuka array.prototype.sort, dan efek penyortiran aktual yang dilakukan di browser tidak konsisten.
Perbedaan dalam pengurutan stabilitas perlu dipicu oleh skenario spesifik sebelum ada masalah; Dalam banyak kasus, penyortiran yang tidak stabil tidak akan berdampak.
Jika tidak perlu stabilitas dalam penyortiran array dalam pengembangan proyek yang sebenarnya, maka Anda benar -benar dapat melihat ini, dan perbedaan implementasi antara browser tidak begitu penting.
Tetapi jika proyek mensyaratkan bahwa jenis itu harus stabil, maka keberadaan perbedaan -perbedaan ini tidak akan memenuhi permintaan. Kita perlu melakukan beberapa pekerjaan tambahan untuk ini.
Misalnya:
Aturan kemenangan terakhir untuk sistem lelang lisensi kendaraan bermotor di kota tertentu adalah:
1. Urutkan berdasarkan harga secara terbalik;
2. Harga yang sama akan diurutkan secara positif sesuai dengan pesanan penawaran (mis. Waktu pengiriman harga).
Jika penyortiran dilakukan di ujung depan, pemenang yang ditampilkan di browser menggunakan jenis cepat cenderung tidak konsisten dengan harapan.
Jelajahi perbedaan
Sebelum menemukan solusi, perlu untuk mengeksplorasi alasan masalah tersebut.
Mengapa Chrome Menggunakan Penyortiran Cepat
Bahkan, situasi ini ada sejak awal.
Chrome Beta dirilis pada 2 September 2008. Namun, tak lama setelah dirilis, beberapa pengembang mengirimkan umpan balik bug #90 ke Grup Pengembangan Chromium. Implementasi penyortiran array V8 tidak stabil.
Diskusi edisi bug ini sangat membentang. Hingga 10 November 2015, pengembang masih mengomentari implementasi penyortiran array di V8.
Pada saat yang sama, kami juga memperhatikan bahwa masalah ini telah ditutup. Namun, itu dibuka kembali oleh anggota tim pengembangan pada Juni 2013 sebagai referensi untuk diskusi spesifikasi ecmascript selanjutnya.
Dan kesimpulan terakhir dari ES-Diskus adalah
Salinan kode adalah sebagai berikut:
Itu tidak berubah. Stabil adalah subset dari tidak stabil. Dan sebaliknya, setiap algoritma yang tidak stabil mengembalikan hasil yang stabil untuk beberapa input. Maksud Mark adalah bahwa yang membutuhkan "selalu tidak stabil" tidak memiliki arti, apa pun bahasa yang Anda pilih.
/Andreas
Seperti yang dijelaskan dalam spesifikasi ECMascript 2015 yang difinalisasi yang dikutip sebelumnya dalam artikel ini.
Karakteristik zaman
IMHO, masalah ini dilaporkan pada awal rilis Chrome, yang mungkin memiliki karakteristik khusus zamannya.
Seperti disebutkan di atas, versi pertama Chrome dirilis pada September 2008. Menurut statistik dari Statcounter, dua browser dengan pangsa pasar tertinggi selama periode itu adalah IE (hanya IE6 dan IE7 pada waktu itu) dan Firefox, dengan pangsa pasar masing -masing mencapai 67,16% dan 25,77%. Dengan kata lain, pangsa pasar gabungan dari dua browser melebihi 90%.
Menurut statistik algoritma penyortiran browser lain, dua browser ini dengan lebih dari 90% pangsa pasar mengadopsi penyortiran array yang stabil. Oleh karena itu, masuk akal untuk ditanyai oleh pengembang di awal rilis Chrome.
Mematuhi spesifikasinya
Dari diskusi masalah bug, kami dapat secara kasar memahami beberapa pertimbangan anggota tim pengembangan dalam menggunakan penyortiran implementasi mesin yang cepat.
Salah satunya adalah bahwa mereka percaya bahwa mesin harus mematuhi spesifikasi ecmascript. Karena spesifikasi tidak memerlukan deskripsi penyortiran yang stabil, mereka percaya bahwa implementasi V8 sepenuhnya sejalan dengan spesifikasi.
Pertimbangan kinerja
Selain itu, mereka percaya bahwa pertimbangan penting dalam desain V8 adalah kinerja mesin.
Penyortiran cepat melakukan kinerja keseluruhan yang lebih baik daripada menggabungkan penyortiran:
Efisiensi komputasi yang lebih tinggi. Penyortiran cepat lebih cepat dalam lingkungan eksekusi komputer yang sebenarnya daripada algoritma penyortiran lainnya dengan kompleksitas waktu yang sama (jika tidak mencapai kombinasi terburuk)
Biaya ruang yang lebih rendah. Yang pertama hanya memiliki kompleksitas ruang O (n), dibandingkan dengan kompleksitas ruang O (n) yang terakhir, konsumsi memori lebih sedikit selama runtime.
Optimalisasi kinerja V8 dalam algoritma penyortiran array
Karena V8 sangat tertarik dengan kinerja mesin, apa yang dilakukannya dalam penyortiran array?
Dengan membaca kode sumber, saya masih belajar beberapa pengetahuan dasar.
Sort Sisipan Campuran
Penyortiran cepat adalah gagasan untuk membagi dan menaklukkan, membusuk array besar dan mengulanginya ke lapisan demi lapis. Namun, jika kedalaman rekursi terlalu besar, konsumsi sumber daya memori dari tumpukan panggilan rekursif juga akan sangat besar. Optimalisasi yang buruk bahkan dapat menyebabkan tumpukan overflow.
Implementasi V8 saat ini adalah untuk mengatur ambang batas dan menggunakan penyortiran insert untuk array kecil 10 atau kurang panjang di lapisan terendah.
Menurut komentar dan deskripsi kode di wikipedia, meskipun kompleksitas waktu rata -rata dari jenis penyisipan adalah O (n²) lebih buruk daripada jenis o (nn) yang cepat. Namun, di lingkungan yang sedang berjalan, efisiensi menggunakan penyisipan penyisipan array kecil lebih efisien daripada penyortiran cepat, sehingga tidak akan diperluas di sini.
Contoh kode V8
var quicksort = function quicksort (a, from, to) {...... while (true) {// sort sorsi penyisipan lebih cepat untuk array pendek. if (to - from <= 10) {insersionsort (a, from, to); kembali; } ......} ......};Tiga angka ada
Seperti yang diketahui, tumit Achilles yang menyortir cepat adalah bahwa algoritma merosot dalam kombinasi array terburuk.
Inti dari algoritma penyortiran cepat adalah memilih pivot, dan menguraikan array yang telah dibandingkan dan dipertukarkan ke dua area angka sesuai dengan referensi untuk rekursi berikutnya. Bayangkan jika, untuk array yang sudah dipesan, elemen pertama atau terakhir selalu dipilih setiap kali elemen referensi dipilih, maka akan ada area angka yang kosong setiap kali, dan jumlah lapisan rekursif akan mencapai N, yang pada akhirnya akan menyebabkan degradasi kompleksitas waktu algoritma menjadi O (n²). Oleh karena itu, pilihan pivot sangat penting.
V8 menggunakan optimalisasi median-of-three : Selain dua elemen di awal dan akhir, elemen lain dipilih untuk berpartisipasi dalam kompetisi elemen benchmark.
Strategi seleksi untuk elemen ketiga adalah secara kasar:
Ketika panjang array kurang dari atau sama dengan 1000, pilih elemen pada posisi setengah sebagai elemen target.
Ketika panjang array melebihi 1000, pilih satu elemen pada jarak 200-215 (non-fix, berubah dengan panjang array) untuk menentukan batch elemen kandidat terlebih dahulu. Kemudian urutkan elemen kandidat dalam batch ini, dan gunakan nilai median yang dihasilkan sebagai elemen target.
Akhirnya, ambil nilai median dari tiga elemen sebagai pivot.
Contoh kode V8
var getThirdIndex = function (a, from, to) {var t_array = new internalArray (); // Gunakan kedua 'dari' dan 'untuk' untuk menentukan kandidat pivot. var increment = 200 + ((ke - from) & 15); var j = 0; dari += 1; ke -= 1; untuk (var i = from; i <to; i += increment) {t_array [j] = [i, a [i]]; j ++; } t_array.sort (function (a, b) {return comparefn (a [1], b [1]);}); var ketiga_index = t_array [t_array.length >> 1] [0]; kembalikan ketiga_index;}; var quicksort = function quicksort (a, from, to) {...... while (true) {...... if (to - from> 1000) {Third_index = getHirdIndex (a, from, to); } else {ketiga_index = dari + ((ke - from) >> 1); }} ......};Urutkan di tempatnya
Saat meninjau algoritma penyortiran cepat, saya melihat banyak contoh implementasi menggunakan JavaScript di internet.
Tetapi saya menemukan bahwa sebagian besar implementasi kode adalah sebagai berikut
var quicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var left = []; var right = []; untuk (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} return quicksort (kiri) .concat ([pivot], quicksort (kanan));};Masalah utama dengan kode di atas adalah: menggunakan dua area angka kiri dan kanan untuk menyimpan subarray rekursif, sehingga membutuhkan ruang penyimpanan tambahan O (n). Ini adalah perbedaan besar dibandingkan dengan kompleksitas spasial rata -rata teoritis O (n).
Overhead ruang tambahan juga akan mempengaruhi kecepatan keseluruhan runtime yang sebenarnya. Ini juga salah satu alasan mengapa penyortiran cepat dapat berkinerja pada runtime yang sebenarnya di luar tingkat kompleksitas waktu yang sama. Oleh karena itu, secara umum, penyortiran cepat dengan kinerja yang lebih baik akan mengadopsi penyortiran di tempat.
Implementasi dalam kode sumber V8 adalah untuk bertukar elemen pada array asli.
Mengapa Firefox Menggunakan Gabungan Penyortiran
Ada juga cerita di baliknya.
Bahkan, ketika Firefox dirilis pada awalnya, itu tidak menggunakan algoritma penyortiran yang stabil untuk menerapkan penyortiran array, yang didokumentasikan dengan baik.
Algoritma penyortiran array yang diimplementasikan oleh versi asli Firefox (Firebird) adalah penyortiran tumpukan, yang juga merupakan algoritma penyortiran yang tidak stabil. Karena itu, seseorang kemudian mengirimkan bug.
Tim pengembangan Mozilla telah melakukan serangkaian diskusi tentang masalah ini.
Dari proses diskusi, kita dapat menggambar beberapa poin
1. Pesaing Mozilla selama periode yang sama adalah IE6. Dari statistik di atas, kita dapat melihat bahwa IE6 stabil dalam penyortiran.
2.Brendan Eich, bapak JavaScript, menganggap stabilitas itu bagus
3. Firefox menggunakan penyortiran cepat sebelum penyortiran tumpukan
Berdasarkan premis utama bahwa anggota kelompok pengembangan cenderung menerapkan algoritma penyortiran yang stabil, Firefox3 mengambil gabungan penyortiran sebagai implementasi baru dari penyortiran array.
Menyelesaikan perbedaan dalam penyortiran stabilitas
Saya telah mengatakan jauh di atas terutama untuk mengatakan perbedaan dalam implementasi penyortiran masing -masing browser, dan untuk menjelaskan beberapa alasan yang lebih dangkal mengapa perbedaan ini ada.
Tetapi setelah membaca ini, pembaca mungkin masih memiliki pertanyaan: Apa yang harus saya lakukan jika proyek saya hanya perlu mengandalkan penyortiran yang stabil?
Larutan
Faktanya, gagasan menyelesaikan masalah ini relatif sederhana.
Browser memilih berbagai algoritma penyortiran untuk pertimbangan yang berbeda. Beberapa mungkin cenderung mengejar kinerja ekstrem, sementara yang lain cenderung memberikan pengalaman pengembangan yang baik, tetapi ada aturan yang harus diikuti.
Dilihat dari situasi yang diketahui saat ini, semua browser arus utama (termasuk IE6, 7, 8) pada dasarnya dapat menyebutkan implementasi algoritma penyortiran array:
1. Gabungkan penyortiran/timsort
2. Sortir Cepat
Jadi, kita bisa mengubah penyortiran cepat menjadi penyortiran yang stabil?
Secara umum, menggunakan penyortiran yang tidak stabil untuk array objek akan mempengaruhi hasil. Sementara jenis array lain sendiri menggunakan hasil penyortiran yang stabil atau tidak stabil adalah sama. Oleh karena itu, rencananya kira -kira sebagai berikut:
Preprocess Array untuk disortir dan menambahkan atribut orde alami untuk setiap objek yang akan diurutkan, agar tidak bertentangan dengan atribut lain dari objek.
Metode Perbandingan Penyortiran Kustom Comparefn selalu menggunakan urutan alami sebagai dimensi penilaian kedua ketika pra-penilaian sama.
Saat menghadapi implementasi seperti menggabungkan penyortiran, karena algoritma itu sendiri stabil, perbandingan urutan alami tambahan tidak akan mengubah hasil penyortiran, sehingga kompatibilitas skema lebih baik.
Namun, ini melibatkan memodifikasi array yang akan diurutkan, dan ruang tambahan diperlukan untuk menyimpan properti pesanan alami. Dapat dibayangkan bahwa mesin seperti V8 tidak boleh menggunakan metode serupa. Namun, itu layak sebagai rencana penyortiran yang disesuaikan oleh pengembang.
Contoh Kode Skema
'gunakan ketat'; const index = simbol ('index'); function getComparer (bandingkan) {return function (kiri, kanan) {let hasil = bandingkan (kiri, kanan); Hasil pengembalian === 0? Kiri [Indeks] - Kanan [Indeks]: Hasil; };} function sort (array, bandingkan) {array = array.map ((item, index) => {if (typeof item === 'objek') {item [index] = index;} return item;}); return array.sort (getComparer (bandingkan));}Di atas hanyalah contoh modifikasi algoritma sederhana yang memenuhi penyortiran yang stabil.
Alasan mengapa sederhana adalah bahwa struktur data sebagai input array dalam lingkungan produksi aktual adalah kompleks, dan perlu untuk menilai apakah lebih banyak jenis pra-pemesanan diperlukan berdasarkan situasi aktual.
Menandai
1. Front-end sekarang menjadi konsep yang relatif luas. Front-end dalam artikel ini terutama mengacu pada lingkungan menggunakan browser sebagai operator dan javascript sebagai bahasa pemrograman.
2. Artikel ini tidak bermaksud melibatkan algoritma secara keseluruhan. Saya ingin menggunakan algoritma penyortiran umum sebagai titik masuk.
3. Saat mengkonfirmasi algoritma yang diimplementasikan oleh Firefox Array Sorting, bug yang berhubungan dengan sortir ditemukan di Spidermoney. Secara umum, selama diskusi, seseorang menyarankan menggunakan algoritma TimSort dengan kinerja yang lebih baik dalam kasus -kasus ekstrem untuk menggantikan penyortiran gabungan, tetapi insinyur Mozilla mengatakan bahwa karena masalah otorisasi lisensi dari algoritma Timsort, tidak ada cara untuk secara langsung menggunakan algoritma dalam perangkat lunak Mozilla dan menunggu balasan pihak lain.
Meringkaskan
Di atas adalah ringkasan dan solusi untuk masalah yang dihadapi dalam penyortiran front-end. Dalam beberapa tahun terakhir, semakin banyak proyek berubah menuju aplikasi klien yang kaya, dan proporsi front-end dalam proyek telah meningkat. Dengan peningkatan lebih lanjut dari daya komputasi browser di masa depan, ini memungkinkan untuk beberapa perhitungan yang lebih kompleks. Dengan perubahan tanggung jawab, formulir front-end juga dapat mengalami beberapa perubahan besar. Saat berjalan di dunia, Anda harus selalu memiliki keterampilan.