Kisah Masalah: Memoizer JavaScript Terpendek

Itu di malam hari, pada malam konferensi tahunan HolyJS di St. Petersburg. Perusahaan kami telah menjadi sponsor selama beberapa tahun: karenanya, ia juga memiliki pendirian sendiri dengan minat yang menarik bagi pikiran ingin tahu pengembang yang peduli. Ketika hidangan utama sudah siap dan semua tugas ditinjau dan diselesaikan oleh pengacara, saya memutuskan untuk memberikan makanan intelektual kepada teman-teman saya di malam hari:

Menulis memoizer - fungsi dekorator yang menyimpan hasil menjalankan fungsi yang dibungkus untuk mencegah perhitungan berulang. Anda hanya memiliki 50 karakter.

Bahasanya, tentu saja, JavaScript . Tugas itu sendiri adalah klasik, tetapi batas 50 karakter berubah menjadi tantangan nyata.

Di sela-sela hari pertama konferensi, kami membahas opsi untuk mencapai tujuan, secara bertahap mengurangi respons. Semua hype dimahkotai dengan gagasan berbagi tugas dengan semua peserta konferensi, dan pada hari kedua kami memvisualisasikan tugas (lihat lampiran) dan mulai membagikan formulir kepada mereka yang ingin. Akibatnya, kami mendapat sekitar 40 solusi dan sekali lagi menjadi yakin dengan komunitas luar biasa pengembang js, tetapi catatan Dmitry Kataev (SEMrush) dari 53 karakter tetap ada. Mari kita cari tahu!

Implementasi kebiasaan

function memoize(f) { let cache = {}; return function ret() { let key = JSON.stringify(arguments); if (!cache.hasOwnProperty(key)) { cache[key] = f.apply(this, arguments); } return cache[key]; } } 

Hasil: ~ 190 karakter

• memoize - memoizer kami
• f - didekorasi, fungsi dibungkus
• fungsi ret - result

Untuk mendapatkan jawaban - ukuran fungsi - kami menggunakan:

 memoize.toString().replace(/\s+/g, ' ').length 

Saat mengevaluasi ukuran suatu fungsi, kami memperhatikan tubuhnya dan daftar parameter. Jika fungsinya anonim, maka deklarasi tidak diperhitungkan.

Tes sederhana untuk menguji kesehatan setelah pelecehan:

 const log = memoize(console.log); const inc = memoize(o => ox + 1); 

Selanjutnya, hasil dari setiap implementasi akan ditandai oleh hasil tes.

Implementasi bersih

Pertama-tama, saya ingin menyingkirkan Deklarasi Fungsi untuk mendukung fungsi panah, karena kami tidak tertarik dengan konteks ini , kami tidak menarik argumen, dan sebagai konstruktor kami tidak bermaksud untuk memanggil melalui yang baru . Pada saat yang sama, kami akan mengurangi nama-nama variabel lokal yang digunakan:

 const memoize = f => { let c = {}; return function() { let k = JSON.stringify(arguments); if (!c.hasOwnProperty(k)) { c[k] = f.apply(this, arguments); } return c[k]; } } 

Hasil: 154 , tes lulus

Kemudian kita dapat melakukan operasi yang sama dengan fungsi yang dihasilkan, tetapi kita membutuhkan argumen . Di sini operator spread datang untuk menyelamatkan, memungkinkan kami untuk mengganti objek iterable argumen yang dilewatkan dengan variabel array a . Selain itu, kami tidak akan lagi meneruskan konteks ini ke fungsi yang sedang didekorasi: jika perlu, Function.prototype.bind atau polyfil kami akan membantu.

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); if (!c.hasOwnProperty(k)) { c[k] = f(...a); } return c[k]; } } 

Hasil: 127 , tes lulus

Sekarang kita beralih ke tubuh fungsi yang dihasilkan. Jelas, menemukan kunci dalam cache dan mengembalikan nilainya merepotkan. Mari kita coba kurangi caranya:

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return c[k] || (c[k] = f(...a)); } } 

Hasil: 101 , tes 3 dan 4 jatuh

Di sini kita meninggalkan metode hasOwnProperty . Kita dapat membelinya, karena hasil serialisasi array argumen melalui JSON.stringify akan selalu menjadi "[...]" dan tidak mungkin bahwa properti seperti itu akan muncul dalam cache prototipe ( Obyek ).

Selanjutnya, kami menggunakan fitur operator "logis" ATAU untuk mengembalikan ekspresi pertama jika dapat dikonversi ke true , atau yang kedua, dengan perhitungan fungsi sebelumnya.

Dan di sini kita jatuh tes 3 dan 4. Ini terjadi karena fungsi console.log yang dihiasi tidak mengembalikan nilai: hasilnya akan tidak ditentukan . Kami memasukkan ini ke dalam cache, dan ketika kami mencoba memeriksa fitur disjunctor ketika kami menyebutnya lagi, secara implisit kami menampilkan false di operan pertama dan, karenanya, masuk ke yang kedua, yang mengarah ke pemanggilan fungsi. Efek ini akan terjadi untuk semua hasil dikurangi menjadi false : 0, "", null, NaN , dll.

Alih-alih ATAU dan jika pernyataan, kita dapat menggunakan operator ternary bersyarat:

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return c.hasOwnProperty(k) ?c[k] :c[k] = f(...a); } } 

Hasil: 118 , tes lulus

Mengurangi sangat sedikit. Tetapi bagaimana jika Anda menggunakan Peta sebagai penyimpanan alih-alih objek sederhana? Ada juga metode singkat:

 const memoize = f => { let c = new Map; return (...a) => { let k = JSON.stringify(a); return (c.has(k) ?c :c.set(k, f(...a))).get(k); } } 

Hasil: 121 , tes lulus

Mengurangi sepenuhnya gagal. Tapi segera buang Peta tidak layak. Implementasi penyimpanan nilai-kunci ini memungkinkan Anda untuk menggunakan objek sebagai kunci. Dan itu berarti, haruskah kita melepaskan JSON. Perjelas sama sekali?

 const memoize = f => { let c = new Map; return (...a) => (c.has(a) ?c :c.set(a, f(...a))).get(a); } 

Hasil: 83 , tes 3 dan 4 jatuh

Itu terlihat sangat menjanjikan! Namun, tes 3 dan 4 mulai turun lagi, ini karena perbandingan kunci dalam objek Peta diimplementasikan menggunakan algoritma SameValueZero . Jika Anda menghilangkan detail dengan NaN, -0 dan 0 , maka itu bekerja sama dengan operator perbandingan ketat ( === ). Dan kami memiliki array argumen baru (dan karenanya sebuah objek) untuk setiap panggilan dari fungsi yang dibungkus, bahkan dengan nilai yang sama. Perbandingan terjadi sesuai dengan referensi objek dan oleh karena itu metode Map.prototype.has tidak akan pernah menemukan apa pun.

Dengan demikian, penggunaan Peta tidak mengurangi kami hasOwnProperty atau JSON.stringify .

Dalam operator datang ke penyelamatan, yang memeriksa keberadaan properti di suatu objek atau dalam rantai prototipe. Mengapa kita tidak perlu takut dengan pencarian prototipe telah dijelaskan di atas.

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return k in c ?c[k] :c[k] = f(...a); } } 

Hasil: 105 , tes lulus

Badan memoizer dan fungsi yang dihasilkan terdiri dari dua ekspresi dengan kebutuhan untuk mendeklarasikan dan menginisialisasi variabel lokal sebelum logika dalam pernyataan kembali . Apakah mungkin untuk mengurangi isi fungsi panah menjadi satu ekspresi di sini? Tentu saja, menggunakan pola IIFE ( Ekspresi Fungsi Langsung ):

 const memoize = f => (c => (...a) => (k => k in c ?c[k] : c[k] = f(...a))(JSON.stringify(a)) )({}); 

Hasil: 82 , tes lulus

Saatnya untuk menyingkirkan ruang ekstra:

 f=>(c=>(...a)=>(k=>k in c?c[k]:c[k]=f(...a))(JSON.stringify(a)))({}); 

Hasil: 68 , tes lulus

Jelas, bottleneck sekarang adalah metode JSON.stringify panjang, yang secara serial membuat objek menjadi string JSON, yang kami gunakan sebagai kuncinya. Sebenarnya, kita tidak memerlukan fungsi serialisasi, tetapi fungsi hash yang dengannya kita bisa memeriksa kesetaraan objek, karena berfungsi dalam bahasa lain. Tapi, sayangnya, tidak ada solusi asli dalam JavaScript, dan kode hashCode yang ditulis sendiri dalam prototipe Object jelas di luar ruang lingkup.

Hmm, kenapa kita harus membuat cerita bersambung? Saat menambahkan elemen ke objek dengan kunci, toStringnya akan dipanggil secara implisit. Karena kami menolak untuk menggunakan objek argumen iterable yang mendukung array melalui operator spread , panggilan ke String tidak akan berasal dari Object.prototype , tetapi dari Array.prototype , di mana ia didefinisikan ulang dan dipisahkan oleh elemen-elemennya. Jadi, untuk serangkaian argumen yang berbeda, kami mendapatkan kunci yang berbeda.

 f=>(c=>(...a)=>a in c?c[a]:c[a]=f(...a))({}); 

Hasil: 44 , tes 6 jatuh

Tes 6 baru saja mulai turun. Tampaknya nilai kembali adalah hasil dari panggilan fungsi sebelumnya dalam tes 5. Mengapa ini terjadi? Ya, kami melewati panggilan toString untuk objek argumen , tetapi kami tidak memperhitungkan bahwa argumen apa pun bisa menjadi objek yang kompleks, memanggil toString dari mana kami mendapatkan [objek objek] favorit semua orang. Ini berarti bahwa argumen {x: 1} dan {x: 2} akan menggunakan kunci yang sama dalam hash.

Btoa yang digunakan untuk mengkonversi ke base64 tampak seperti pesaing yang baik untuk fungsi serialisasi. Tapi dia memimpin dulu ke tali, jadi tidak ada peluang. Kami berpikir ke arah menghasilkan URI, dan membentuk ArrayBuffer , fungsi apa pun untuk mendapatkan nilai hash atau serial. Tapi mereka tetap di tempatnya.

Ngomong-ngomong, JSON.stringify memiliki kekhasan sendiri: Infinity, NaN, undefined, Symbol akan dilemparkan ke nol . Hal yang sama berlaku untuk fungsi. Jika memungkinkan, panggilan implisit ke JSON dari objek terjadi, dan Map dan Set akan diwakili oleh elemen yang hanya disebutkan. Dapat dimengerti, mengingat format terakhir: JSON.

Apa selanjutnya

Modifikasi beracun

Kita semua tentu menyukai fitur murni, tetapi dalam menghadapi tugas, persyaratan ini tidak sepadan. Dan ini berarti sudah saatnya menambahkan sejumput efek samping.

Pertama, mengapa tidak memulai cache sebagai berikut:

 (f,c={})=>(...a)=>(k=>k in c?c[k]:c[k]=f(...a))(JSON.stringify(a)); 

Hasil: 66 , tes lulus

Di sini kita menggunakan parameter default dalam fungsi panah. Tentu saja, kami memberi klien kesempatan untuk mengatur cache mereka, jadi apa? Tapi kami mengurangi 2 karakter.

Bagaimana lagi saya bisa memulai cache untuk fungsi yang akan dihiasi? Jawaban yang benar: mengapa kita perlu memulainya? Mengapa tidak menggunakan sesuatu yang siap dalam konteks fungsi yang akan dibungkus. Namun bagaimana jika fungsinya sendiri? Kita semua tahu bahwa fungsi dalam JavaScript juga objek:

 f=>(...a)=>(k=>k in f?f[k]:f[k]=f(...a))(JSON.stringify(a)); 

Hasil: 59 , tes lulus

Di sini JSON.stringify akan melindungi kita dari berpotongan dengan properti dan metode lain dari objek (fungsi), membungkus argumen dalam "[...]".

Pada saat ini, pola IIFE yang diterapkan sebelumnya tidak lagi membenarkan dirinya sendiri. Tetapi menjaga satu ekspresi untuk fungsi panah sangat diperlukan untuk menghindari pernyataan kembali :

 f=>(...a)=>(k=JSON.stringify(a),k in f?f[k]:f[k]=f(...a)); 

Hasil: 57 , tes lulus

Karena kita tidak menggunakan pernyataan blok dalam fungsi panah, kita tidak dapat mendeklarasikan variabel ( var atau let ), tetapi kita dapat menggunakan konteks global - efek samping! Di sini konflik sudah memiliki beberapa peluang.

Menggunakan operator koma, kami menggabungkan dua ekspresi menjadi satu: operan dievaluasi dari kiri ke kanan, dan hasilnya adalah nilai yang terakhir.

 f=>(...a)=>(k=JSON.stringify(a))in f?f[k]:f[k]=f(...a); 

Hasil: 54 , tes lulus

Jadi, dengan mengatur ulang hanya satu braket, kami menyingkirkan tiga karakter sekaligus. Operator pengelompokan dalam menghitung kunci memungkinkan kami untuk menggabungkan kedua operan dari ekspresi menjadi hanya satu ekspresi, dan braket penutup menghilangkan ruang sebelum operator masuk .

Dan akhirnya:

 f=>(...a)=>f[k=JSON.stringify(a)]=k in f?f[k]:f(...a); 

Hasil: 53 , tes lulus

Mengapa tidak menghitung kunci saat mengakses nilai. Dan kemudian - operator dan tugas ternary yang sama. Total: 53 karakter!

Apakah mungkin untuk menghapus 3 karakter yang tersisa?

Pemahaman

Kenapa semua ini? Tugas sederhana ini dan rangkaian konversi dari kebiasaan menjadi tidak senonoh menunjukkan sejumlah besar fitur bahasa JavaScript. Dalam diskusi kami, kami menyentuh hal-hal seperti:

• Ekspresi fungsi panah
• Pelingkupan leksikal & IIFE
• Objek argumen seperti array
• Sebarkan, koma, atau operator
• Operator perbandingan ketat
• JSON.stringify & toString
• Di operator & hasOwnProperty
• Pengelompokan operator & pernyataan blokir
• Objek peta
• dan sesuatu yang lain

Kisah-kisah semacam itu adalah alasan yang baik untuk membenamkan diri dalam studi spesifik suatu bahasa, membantu untuk lebih memahaminya (atau sebaliknya). Dan tentu saja, hanya untuk bersenang-senang!

Aplikasi

Dalam petualangannya, Rick sering kali harus mengkalibrasi pistol portalnya. Prosedur ini membutuhkan waktu, tetapi inputnya sering diulang. Ilmuwan itu mencoba menghafal hasil yang sudah diperoleh sekali agar tidak membuat perhitungan berulang kali, tetapi alkoholisme dan pikun sangat mempengaruhi ingatannya. Dia meminta Morty untuk meningkatkan modul pengaturan senjata, menambahkan fungsi memoizer. Fungsi ini harus menyimpan hasil fungsi yang sedang didekorasi untuk mencegah perhitungan berulang. Hanya Morty yang panik dan takut akan fungsi panjang. Bantu dia memecahkan masalah sepadat mungkin . Fungsi yang sedang didekorasi dapat menggunakan integer, string, Boolean, dan objek sebagai argumen.