Kinerja: rekursi vs. iterasi dalam Javascript

24

Saya telah membaca beberapa artikel baru-baru ini (mis. Http://dailyjs.com/2012/09/14/functional-programming/ ) tentang aspek fungsional Javascript dan hubungan antara Skema dan Javascript (yang terakhir dipengaruhi oleh yang pertama, yang adalah bahasa fungsional, sedangkan aspek OO diwarisi dari Self yang merupakan bahasa berbasis prototyping).

Namun pertanyaan saya lebih spesifik: Saya bertanya-tanya apakah ada metrik tentang kinerja rekursi vs iterasi dalam Javascript.

Saya tahu bahwa dalam beberapa bahasa (di mana dengan iterasi desain berkinerja lebih baik) perbedaannya minimal karena interpreter / kompiler mengubah rekursi menjadi iterasi, namun saya kira mungkin ini bukan kasus Javascript karena, setidaknya sebagian, fungsional bahasa.

javascript functional-programming recursion mastazi
sumber
3
Lakukan tes Anda sendiri dan temukan langsung di jsperf.com
TehShrike
dengan hadiah dan satu jawaban yang menyebutkan TCO. Tampaknya ES6 menentukan TCO tetapi sejauh ini tidak ada yang mengimplementasikannya jika kami percaya kangax.github.io/compat-table/es6 Apakah saya kehilangan sesuatu?
Matthias Kauer

Jawaban:

28

JavaScript tidak melakukan optimisasi rekursi ekor , jadi jika rekursi Anda terlalu dalam, Anda mungkin mendapatkan stack stack overflow. Iterasi tidak memiliki masalah seperti itu. Jika Anda berpikir Anda akan berulang terlalu banyak, dan Anda benar-benar membutuhkan rekursi (misalnya, untuk mengisi banjir), ganti rekursi dengan tumpukan Anda sendiri.

Kinerja rekursi mungkin lebih buruk daripada kinerja iterasi, karena pemanggilan fungsi dan pengembalian membutuhkan pelestarian dan pemulihan keadaan, sementara iterasi hanya melompat ke titik lain dalam suatu fungsi.

Triang3l
sumber
Hanya ingin tahu ... Saya telah melihat sedikit kode di mana array kosong dibuat dan situs fungsi rekursif ditugaskan ke posisi ke dalam array dan kemudian nilai yang disimpan ke dalam array dikembalikan. Apakah itu yang Anda maksud dengan "mengganti rekursi dengan tumpukan Anda sendiri"? Contoh: var stack = []; var factorial = function(n) { if(n === 0) { return 1 } else { stack[n-1] = n * factorial(n - 1); return stack[n-1]; } }
mastazi
@ Mastazi: Tidak, ini akan membuat tumpukan panggilan yang tidak berguna bersama dengan yang internal. Maksud saya seperti mengisi banjir berdasarkan antrian dari Wikipedia .
Triang3l
Perlu dicatat bahwa suatu bahasa tidak melakukan TCO, tetapi sebuah implementasi mungkin. Cara orang mengoptimalkan JS berarti bahwa mungkin TCO dapat muncul dalam beberapa implementasi
Daniel Gratzer
1
@mastazi Ganti elsefungsi itu dengan else if (stack[n-1]) { return stack[n-1]; } elsedan Anda memiliki memoisasi . Siapa pun yang menulis kode faktorial memiliki implementasi yang tidak lengkap (dan mungkin seharusnya digunakan di stack[n]mana-mana, bukan stack[n-1]).
Izkata
Terima kasih @Izkata, saya sering melakukan optimasi seperti itu tetapi sampai hari ini saya tidak tahu namanya. Saya seharusnya belajar CS bukan IT ;-)
mastazi
20

Pembaruan : sejak ES2015, JavaScript memiliki TCO , jadi bagian dari argumen di bawah ini tidak berlaku lagi.

Meskipun Javascript tidak memiliki optimasi panggilan ekor, rekursi seringkali merupakan cara terbaik untuk melakukannya. Dan dengan tulus, kecuali dalam kasus tepi, Anda tidak akan mendapatkan panggilan stack overflow.

Kinerja adalah sesuatu yang perlu diingat, tetapi optimasi prematur juga. Jika Anda berpikir rekursi lebih elegan daripada iterasi, maka lakukanlah. Jika ternyata ini adalah hambatan Anda (yang mungkin tidak akan pernah terjadi), maka Anda dapat menggantinya dengan beberapa iterasi yang jelek. Tetapi sebagian besar waktu, bottleneck terletak pada manipulasi DOM atau lebih umum I / O, bukan kode itu sendiri.

Rekursi selalu lebih elegan 1 .

1 : Pendapat pribadi.

Florian Margaine
sumber
3
Saya setuju bahwa rekursi lebih elegan, dan keanggunan penting karena keterbacaan serta pemeliharaan (ini subjektif, tetapi menurut saya rekursi sangat mudah dibaca, sehingga dapat dipertahankan). Namun, terkadang kinerja penting; dapatkah Anda mendukung klaim bahwa rekursi adalah cara terbaik untuk dilakukan, bahkan berdasarkan kinerja?
mastazi
3
@ Majazi seperti yang dikatakan dalam jawaban saya, saya ragu rekursi akan menjadi hambatan Anda. Sebagian besar waktu, itu adalah manipulasi DOM, atau lebih umum I / O. Dan jangan lupa bahwa optimasi prematur adalah akar dari semua kejahatan;)
Florian Margaine
+1 untuk manipulasi DOM menjadi hambatan sebagian besar waktu! Saya ingat sebuah wawancara yang sangat menarik dengan Yehuda Katz (Ember.js) tentang ini.
mastazi
1
@ Mike Definisi "prematur" adalah "matang atau matang sebelum waktu yang tepat." Jika Anda tahu bahwa melakukan sesuatu secara rekursif akan menyebabkan stackoverflow, maka itu bukan prematur. Namun, jika Anda berasumsi dengan kemauan (tanpa data aktual), maka itu terlalu dini.
Zirak
2
Dengan Javascript Anda tidak tahu berapa banyak tumpukan program yang akan tersedia. Anda bisa memiliki tumpukan kecil di IE6 atau tumpukan besar di FireFox. Algoritma rekursif jarang memiliki kedalaman yang pasti kecuali Anda melakukan loop rekursif gaya Scheme. Sepertinya bukan rekursi non-loop yang cocok untuk menghindari optimasi prematur.
mike30
7

Saya sangat ingin tahu tentang kinerja ini dalam javascript juga, jadi saya melakukan beberapa percobaan (walaupun pada versi yang lebih tua dari node). Saya menulis kalkulator faktorial secara rekursif vs iterasi dan menjalankannya beberapa kali secara lokal. Hasilnya tampak sangat condong ke arah rekursi memiliki pajak (diharapkan).

Kode: https://github.com/j03m/trickyQuestions/blob/master/factorial.js

Result:
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:557
Time:126
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:519
Time:120
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:541
Time:123
j03m-MacBook-Air:trickyQuestions j03m$ node --version
v0.8.22
Dr.HappyPants
sumber
Anda dapat mencoba ini "use strict";dan melihat apakah ada bedanya. (Ini akan menghasilkan jumps alih-alih urutan panggilan standar)
Burdock
1
Pada versi terbaru dari node (6.9.1) saya mendapat hasil yang sangat mirip. Ada sedikit pajak atas rekursi, tapi saya menganggapnya sebagai kasus tepi - perbedaan 400 ms untuk 1.000.000 loop adalah 0,0025 ms per loop. Jika Anda melakukan 1.000.000 loop, itu adalah sesuatu yang perlu diingat.
Kelz
6

Sesuai permintaan OP, saya akan ikut serta (tanpa membodohi diri sendiri, semoga: P)

Saya pikir kita semua sepakat bahwa rekursi hanyalah cara pengkodean yang lebih elegan. Jika dilakukan dengan baik dapat membuat kode lebih mudah dikelola, yang merupakan IMHO sama pentingnya (jika tidak lebih) yang mengurangi 0,0001ms.

Sejauh argumen bahwa JS tidak melakukan optimasi Tail-call: itu tidak sepenuhnya benar lagi, menggunakan mode ketat ECMA5 memungkinkan TCO. Itu adalah sesuatu yang saya tidak terlalu senang tentang beberapa waktu yang lalu, tapi setidaknya sekarang saya tahu mengapa arguments.calleemelempar kesalahan dalam mode ketat. Saya tahu tautan di atas tautan ke laporan bug, tetapi bug tersebut diatur ke WONTFIX. Selain itu, TCO standar akan datang: ECMA6 (Desember 2013).

Secara naluriah, dan berpegang pada sifat fungsional JS, saya akan mengatakan bahwa rekursi adalah gaya pengkodean yang lebih efisien 99,99% dari waktu. Namun, Florian Margaine ada benarnya ketika dia mengatakan bahwa kemacetan kemungkinan akan ditemukan di tempat lain. Jika Anda memanipulasi DOM, Anda mungkin lebih baik memfokuskan pada penulisan kode Anda sebisa mungkin dipertahankan. API DOM adalah apa adanya: lambat.

Saya pikir hampir tidak mungkin untuk menawarkan jawaban yang pasti sebagai pilihan yang lebih cepat. Akhir-akhir ini, banyak jspref yang saya lihat menunjukkan bahwa mesin V8 Chrome sangat cepat di beberapa tugas, yang berjalan 4x lebih lambat pada SpiderMonkey FF dan sebaliknya. Mesin JS modern memiliki segala macam trik untuk mengoptimalkan kode Anda. Saya bukan ahli, tapi saya merasa bahwa V8, misalnya, sangat dioptimalkan untuk penutupan (dan rekursi), sedangkan mesin MS's JScript tidak. SpiderMonkey sering berkinerja lebih baik ketika DOM terlibat ...

Singkatnya: Saya akan mengatakan teknik mana yang akan lebih performant, seperti biasa di JS, hampir mustahil untuk diprediksi.

Elias Van Ootegem
sumber
3

Tanpa mode ketat, kinerja iterasi biasanya sedikit lebih cepat daripada rekursi ( selain membuat JIT bekerja lebih banyak ). Optimasi rekursi ekor pada dasarnya menghilangkan perbedaan nyata karena mengubah seluruh urutan panggilan menjadi lompatan.

Contoh: Jsperf

Saya akan menyarankan lebih mengkhawatirkan tentang kejelasan dan kesederhanaan kode ketika datang untuk memilih antara rekursi dan iterasi.

Burdock
sumber