HolyJS 2019: Pembekalan dari SEMrush (Bagian 2)

Ini adalah bagian kedua dari analisis tugas dari stan kami di konferensi HolyJS , yang diadakan di St. Petersburg pada 24-25 Mei. Untuk konteks yang lebih besar, Anda disarankan untuk terlebih dahulu membaca bagian pertama dari materi ini. Dan jika Countdown Expression telah selesai, selamat datang di langkah berikutnya.

Tidak seperti obskurantisme dalam tugas pertama, dua berikutnya sudah memiliki beberapa petunjuk tentang penerapan aplikasi normal dalam kehidupan. JavaScript masih berkembang cukup cepat dan solusi untuk masalah yang disarankan menyoroti beberapa fitur baru bahasa.

Tugas 2 ~ Dilakukan oleh Yang

Diasumsikan bahwa kode akan menjalankan dan mencetak jawaban ke konsol dalam menanggapi tiga permintaan, dan kemudian "selesai". Tapi ada yang tidak beres ... Perbaiki situasinya.

;(function() { let iter = { [Symbol.iterator]: function* iterf() { let fs = ['/1', '/2', '/3']; for (const req in fs) { yield fetch(req); } } }; for (const res of iter) { console.log(res); } console.log('done'); })(); 

Masalah penelitian

Apa yang kita punya di sini? Ini adalah objek iterable iter yang memiliki simbol Symbol.iterator terkenal yang didefinisikan melalui fungsi generator . Array fs dideklarasikan di badan fungsi, elemen-elemen yang jatuh ke dalam fungsi ambil pada gilirannya untuk mengirim permintaan dan hasil dari setiap panggilan fungsi dikembalikan melalui hasil . Permintaan apa yang dikirim fungsi ambil ? Semua elemen array fs adalah jalur relatif ke sumber daya dengan angka 1, 2, dan 3, masing-masing. Jadi URL lengkap akan diperoleh dengan menggabungkan location.origin dengan nomor berikutnya, misalnya:

GET https://www.example.com/1

Selanjutnya, kita ingin mengulangi objek iter melalui for-of , untuk mengeksekusi setiap permintaan secara bergantian dengan output dari hasilnya, setelah semua - cetak "selesai". Tapi itu tidak berhasil! Masalahnya adalah bahwa mengambil adalah hal yang tidak sinkron dan mengembalikan janji, bukan respons. Karenanya, di konsol kita akan melihat sesuatu seperti ini:

Promise {pending}
Promise {pending}
Promise {pending}
done

Sebenarnya, tugas turun untuk menyelesaikan janji-janji yang sama ini.

Kami memiliki async / menunggu

Pikiran pertama mungkin bermain dengan Promise.all : berikan objek iterable kami, maka output ke konsol “selesai”. Tetapi dia tidak akan memberi kami eksekusi permintaan yang berurutan (seperti yang dipersyaratkan oleh kondisi), tetapi cukup kirimkan semuanya dan tunggu jawaban terakhir sebelum resolusi umum.

Solusi paling sederhana di sini akan menunggu di - tubuh untuk menunggu resolusi janji berikutnya sebelum output ke konsol:

 for (const res of iter) { console.log(await res); } 

Agar menunggu untuk bekerja dan "selesai" untuk ditampilkan di akhir, Anda perlu membuat fungsi utama asinkron melalui async :

 ;(async function() { let iter = { /* ... */ }; for (const res of iter) { console.log(await res); } console.log('done'); })(); 

Dalam hal ini, masalahnya sudah diselesaikan (hampir):

GET 1st
Response 1st
GET 2nd
Response 2nd
GET 3rd
Response 3rd
done


Asynchronous Iterator dan Generator

Kami akan meninggalkan fungsi utama asinkron, tetapi untuk menunggu ada tempat yang lebih elegan dalam tugas ini daripada di for-of body: ini adalah penggunaan iterasi sinkron melalui for-waiting-of , yaitu:

 for await (const res of iter) { console.log(res); } 

Semuanya akan berhasil! Tetapi jika Anda beralih ke deskripsi proposal ini tentang iterasi asinkron, maka inilah yang menarik:

Kami memperkenalkan variasi pernyataan iterasi for-of yang beriterasi pada objek iterable yang aser. Pernyataan async hanya diperbolehkan dalam fungsi async dan fungsi generator async

Artinya, objek kita seharusnya bukan hanya dapat diubah, tetapi "asyncIterable" melalui simbol Symbol.asyncIterator baru yang terkenal dan, dalam kasus kami, sudah menjadi fungsi generator asinkron:

 let iter = { [Symbol.asyncIterator]: async function* iterf() { let fs = ['/1', '/2', '/3']; for (const req in fs) { yield await fetch(req); } } }; 

Lalu bagaimana cara kerjanya pada iterator dan generator reguler? Ya, secara tersirat, seperti lebih banyak dalam bahasa ini. Ini untuk menunggu adalah rumit: jika objek hanya iterable , maka ketika iterating secara tidak sinkron, itu "mengubah" objek menjadi asyncIterable dengan membungkus elemen (jika perlu) dalam Janji dengan harapan resolusi. Dia berbicara lebih detail dalam sebuah artikel oleh Axel Rauschmayer .

Mungkin, melalui Symbol.asyncIterator masih akan lebih benar, karena kami secara eksplisit membuat objek asyncIterable untuk iterasi asinkron kami melalui for-waiting-of , sambil meninggalkan kesempatan untuk melengkapi objek dengan iterator reguler untuk , jika perlu. Jika Anda ingin membaca sesuatu yang bermanfaat dan memadai dalam satu artikel tentang iterasi sinkron dalam JavaScript, maka ini dia !

Asynchronous for-of masih sebagian dalam konsep, tetapi sudah didukung oleh browser modern (kecuali Edge) dan Node.js dari 10.x. Jika ini mengganggu seseorang, Anda selalu dapat menulis polifile kecil Anda sendiri untuk rantai janji, misalnya, untuk objek yang dapat diubah :

 const chain = (promises, callback) => new Promise(resolve => function next(it) { let i = it.next(); i.done ? resolve() : i.value.then(res => { callback(res); next(it); }); }(promises[Symbol.iterator]()) ); ;(async function() { let iter = { /* iterable */ }; await chain(iter, console.log); console.log('done'); })(); 

Dengan cara ini dan itu, kami menemukan mengirimkan permintaan dan memproses tanggapan pada gilirannya. Namun dalam masalah ini ada satu lagi masalah kecil tapi menjengkelkan ...

Tes kesadaran

Kami begitu terbawa oleh semua asinkronisme ini sehingga, seperti yang sering terjadi, kami kehilangan satu detail kecil. Apakah permintaan itu dikirim oleh skrip kami? Mari kita lihat jaringannya :

GET https://www.example.com/0
GET https://www.example.com/1
GET https://www.example.com/2

Tetapi angka kami adalah 1, 2, 3. Seakan terjadi penurunan. Kenapa begitu Hanya dalam kode sumber tugas ada masalah lain dengan iterasi, di sini:

 let fs = ['/1', '/2', '/3']; for (const req in fs) { yield fetch(req); } 

Di sini for-in digunakan , yang alih-alih nilai array mem-bypass properti enumerasinya: dan ini adalah indeks elemen dari 0 hingga 2. Fungsi fetch masih mengarahkan mereka ke string dan, meskipun tidak ada garis miring sebelumnya (ini bukan lagi jalur ), ia menyelesaikan relatif URL halaman saat ini. Untuk memperbaikinya jauh lebih mudah daripada memperhatikan. Dua opsi:

 let fs = ['/1', '/2', '/3']; for (const req of fs) { yield fetch(req); } let fs = ['/1', '/2', '/3']; for (const req in fs) { yield fetch(fs[req]); } 

Dalam yang pertama, kami menggunakan for-of yang sama untuk beralih pada nilai-nilai array, yang kedua - akses ke elemen array dengan indeks.

Motivasi

Kami mempertimbangkan 3 solusi: 1) melalui penantian dalam for-of body, 2) melalui for-waiting-of, dan 3) melalui polyfile kami (fungsi rekursif, pipa pipa, dll.). Sangat mengherankan bahwa opsi-opsi ini membagi peserta konferensi kurang lebih sama dan tidak ada favorit yang jelas terungkap. Dalam proyek-proyek besar, untuk tugas-tugas nyata seperti itu, perpustakaan reaktif (misalnya, RxJS ) biasanya digunakan, tetapi perlu diingat tentang fitur asli bahasa modern dengan sifat asinkron.

Sekitar setengah dari peserta tidak melihat kesalahan dalam pengulangan atas daftar sumber daya, yang juga merupakan pengamatan yang menarik. Berfokus pada masalah yang tidak sepele tetapi jelas, kita dapat dengan mudah melewatkan hal yang tampaknya sepele ini, tetapi dengan konsekuensi serius yang potensial.

Soal 3 ~ Faktor 19

Berapa kali dalam catatan angka 2019! (faktorial dari 2019) apakah angka 19 terjadi? Bersamaan dengan jawabannya, berikan solusi JavaScript.

Masalah penelitian

Masalahnya ada di permukaan: kita membutuhkan catatan dari jumlah yang sangat besar untuk menemukan di dalamnya jumlah semua kejadian dari substring "19". Memecahkan masalah pada angka , kami sangat cepat mengalami Infinity (setelah 170) dan tidak mendapatkan apa pun. Selain itu, format untuk mewakili angka float64 menjamin keakuratan hanya 15-17 karakter, dan kita harus mendapatkan tidak hanya data yang lengkap, tetapi juga catatan yang akurat. Karenanya, kesulitan utama adalah menentukan struktur untuk akumulasi jumlah besar ini.

Bilangan bulat besar

Jika Anda mengikuti inovasi bahasa, tugas diselesaikan dengan sederhana: alih-alih nomor jenis , Anda dapat menggunakan tipe baru BigInt (tahap 3) , yang memungkinkan Anda untuk bekerja dengan angka presisi acak. Dengan fungsi rekursif klasik untuk menghitung faktorial dan menemukan kecocokan melalui String.prototype.split, solusi pertama terlihat seperti ini:

 const fn = n => n > 1n ? n * fn(n - 1n) : 1n; console.log(fn(2019n).toString().split('19').length - 1); // 50 

Namun, dua ribu panggilan fungsi pada stack sudah bisa berbahaya . Bahkan jika Anda membawa solusi untuk rekursi ekor , maka optimasi panggilan Tail masih hanya mendukung Safari. Masalah faktorial di sini lebih menyenangkan untuk diselesaikan melalui siklus aritmatika atau Array.prototype.reduce :

 console.log([...Array(2019)].reduce((p, _, i) => p * BigInt(i + 1), 1n).toString().match(/19/g).length); // 50 

Ini mungkin tampak seperti prosedur yang sangat panjang. Tapi kesan ini menipu. Jika Anda memperkirakan, maka kami hanya perlu menghabiskan sedikit lebih dari dua ribu perkalian. Pada i5-4590 3.30GHz di chrome, masalahnya diselesaikan rata-rata dalam 4-5ms (!).

Pilihan lain untuk menemukan kecocokan dalam string dengan hasil perhitungan adalah String.prototype.match dengan ekspresi reguler dengan bendera pencarian global: / 19 / g .

Aritmatika besar

Tetapi bagaimana jika kita belum memiliki BigInt ini (dan perpustakaan juga)? Dalam hal ini, Anda bisa melakukan aritmatika panjang sendiri. Untuk menyelesaikan masalah, cukup bagi kita untuk menerapkan hanya fungsi mengalikan besar dengan kecil (kita kalikan dengan angka dari 1 hingga 2019). Kita dapat menyimpan jumlah besar dan hasil penggandaan, misalnya, di baris:

 /** * @param {string} big * @param {number} int * @returns {string} */ const mult = (big, int) => { let res = '', carry = 0; for (let i = big.length - 1; i >= 0; i -= 1) { let prod = big[i] * int + carry; res = prod % 10 + res; carry = prod / 10 | 0; } return (carry || '') + res; } console.log([...Array(2019)].reduce((p, _, i) => mult(p, i + 1), '1').match(/19/g).length); // 50 

Di sini kita cukup mengalikan kolom dalam bit dari ujung garis ke awal, seperti yang diajarkan di sekolah. Tetapi solusinya sudah membutuhkan sekitar 170ms.

Kami dapat meningkatkan algoritme dengan memproses lebih dari satu digit dalam catatan angka setiap kali. Untuk melakukan ini, kami memodifikasi fungsi dan pada saat yang sama pergi ke array, agar tidak dipusingkan dengan garis setiap kali:

 /** * @param {Array<number>} big * @param {number} int * @param {number} digits * @returns {Array<number>} */ const mult = (big, int, digits = 1) => { let res = [], carry = 0, div = 10 ** digits; for (let i = big.length - 1; i >= 0 || carry; i -= 1) { let prod = (i < 0 ? 0 : big[i] * int) + carry; res.push(prod % div); carry = prod / div | 0; } return res.reverse(); } 

Di sini, sejumlah besar diwakili oleh array, masing-masing elemen yang menyimpan informasi tentang digit digit dari catatan angka, menggunakan nomor . Misalnya, angka 2016201720182019 dengan angka = 3 akan direpresentasikan sebagai:

'2|016|201|720|182|019' => [2,16,201,720,182,19]

Saat mengonversi ke baris sebelum bergabung, Anda harus mengingat nol di depannya. Fungsi faktor mengembalikan faktorial yang dihitung oleh string, menggunakan fungsi mult dengan jumlah digit yang diproses pada waktu tertentu dalam representasi "besar-besaran" angka ketika menghitung:

 const factor = (n, digits = 1) => [...Array(n)].reduce((p, _, i) => mult(p, i + 1, digits), [1]) .map(String) .map(el => '0'.repeat(digits - el.length) + el) .join('') .replace(/^0+/, ''); console.log(factor(2019, 3).match(/19/g).length); // 50 

Implementasi "knee-length" melalui array ternyata lebih cepat daripada melalui string, dan dengan digit = 1 itu menghitung jawaban sudah rata-rata dalam 90ms, digit = 3 dalam 35ms, digit = 6 hanya dalam 20ms. Namun, ingatlah bahwa meningkatkan jumlah digit, kami mendekati situasi di mana mengalikan angka dengan angka "di bawah tenda" mungkin di luar brankas MAX_SAFE_INTEGER . Anda bisa bermain dengannya di sini . Berapa nilai digit maksimum yang kami mampu untuk tugas ini?

Hasilnya sudah cukup indikatif, BigInt sangat cepat:

Motivasi

Sangat menyenangkan bahwa 2/3 dari peserta konferensi menggunakan tipe BigInt baru dalam solusi (seseorang mengakui bahwa ini adalah pengalaman pertama). Sepertiga sisanya dari solusi berisi implementasi aritmatika panjang mereka sendiri pada string atau array. Sebagian besar fungsi yang diimplementasikan dikalikan angka besar dengan yang besar, ketika untuk solusi itu cukup untuk dikalikan dengan angka "kecil" dan menghabiskan sedikit waktu lebih sedikit. Oke tugas, apakah Anda sudah menggunakan BigInt dalam proyek Anda?

Ucapan Terima Kasih

Dua hari konferensi ini sangat penuh dengan diskusi dan mempelajari sesuatu yang baru. Saya ingin mengucapkan terima kasih kepada komite program untuk konferensi tak terlupakan berikutnya dan semua peserta atas jaringan yang unik dan suasana hati yang baik.