[ที่อยู่บทความนี้] http://cuimingda.com/2009/02/speed-up-your-javascript-part-3.html
Recursion เป็นหนึ่งในศัตรูที่ทำให้ความเร็วในการรันสคริปต์ช้าลง การเรียกซ้ำมากเกินไปจะทำให้เบราว์เซอร์ช้าลงเรื่อยๆ จนกระทั่งเบราว์เซอร์ตายหรือออกโดยอัตโนมัติอย่างกะทันหันและอธิบายไม่ได้ ดังนั้นเราจึงต้องแก้ไขปัญหาประสิทธิภาพการทำงานชุดนี้ใน JavaScript ในบทความที่สองของชุดนี้ ฉันได้แนะนำสั้น ๆ ถึงวิธีการใช้เทคโนโลยีการบันทึกเพื่อแทนที่การโทรซ้ำมากเกินไปในฟังก์ชันต่างๆ การท่องจำเป็นเทคนิคที่แคชผลลัพธ์ของการคำนวณก่อนหน้านี้ เพื่อที่เราจะได้ไม่ต้องคำนวณผลลัพธ์ที่ได้คำนวณไปแล้วใหม่ สำหรับฟังก์ชันที่ทำการคำนวณผ่านการเรียกซ้ำ การบันทึกช่วยจำมีประโยชน์มากเกินไป บันทึกช่วยจำที่ฉันใช้อยู่ในปัจจุบันเขียนโดย Crockford และส่วนใหญ่จะใช้ในการดำเนินการแบบเรียกซ้ำที่ส่งกลับจำนวนเต็ม แน่นอนว่าไม่ใช่ว่าฟังก์ชันแบบเรียกซ้ำทั้งหมดจะส่งคืนจำนวนเต็ม ดังนั้นเราจึงจำเป็นต้องมีฟังก์ชัน memoizer() ทั่วไปกว่านี้เพื่อจัดการกับฟังก์ชันแบบเรียกซ้ำประเภทต่างๆ มากขึ้น
ฟังก์ชั่น memoizer (พื้นฐาน, แคช){ cache = cache ||. {} var shell = function(arg){ if (!(arg in cache)){ cache[arg] = basic(shell, arg) } return cache[arg] ; }; return shell;} ฟังก์ชันเวอร์ชันนี้แตกต่างจากเวอร์ชันที่เขียนโดย Crockford เล็กน้อย ขั้นแรก ลำดับของพารามิเตอร์จะถูกย้อนกลับ ฟังก์ชันดั้งเดิมจะถูกตั้งค่าเป็นพารามิเตอร์ตัวแรก และพารามิเตอร์ตัวที่สองคือออบเจ็กต์แคช ซึ่งเป็นทางเลือก เนื่องจากฟังก์ชันแบบเรียกซ้ำบางฟังก์ชันเท่านั้นที่มีข้อมูลเริ่มต้น ภายในฟังก์ชันนี้ ฉันแปลงประเภทของวัตถุแคชจากอาร์เรย์ไปยังวัตถุเพื่อให้เวอร์ชันนี้สามารถรองรับฟังก์ชันแบบเรียกซ้ำที่ไม่ส่งคืนจำนวนเต็ม ในฟังก์ชันเชลล์ ฉันใช้ตัวดำเนินการ in เพื่อตรวจสอบว่าพารามิเตอร์รวมอยู่ในแคชแล้วหรือไม่ วิธีการเขียนนี้ปลอดภัยกว่าการทดสอบว่าประเภทนั้นไม่ได้ถูกกำหนดไว้ เนื่องจากไม่ได้กำหนดไว้เป็นค่าที่ส่งคืนที่ถูกต้อง เรายังคงใช้ลำดับฟีโบนักชีที่กล่าวถึงก่อนหน้านี้เพื่อแสดง:
var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, {"0": 0, "1" :1}); ในทำนองเดียวกัน การเรียกใช้ฟังก์ชัน fibonacci(40) จะเรียกใช้ฟังก์ชันดั้งเดิมเพียง 40 ครั้ง แทนที่จะเป็นเกินจริง 331,160,280 ครั้ง การท่องจำเหมาะอย่างยิ่งสำหรับอัลกอริธึมแบบเรียกซ้ำพร้อมชุดผลลัพธ์ที่กำหนดไว้อย่างเคร่งครัด อย่างไรก็ตาม มีอัลกอริธึมแบบเรียกซ้ำจำนวนมากที่ไม่เหมาะสำหรับการเพิ่มประสิทธิภาพโดยใช้วิธีการบันทึก
อาจารย์คนหนึ่งของฉันในโรงเรียนยืนกรานเสมอว่าสถานการณ์ใดก็ตามที่มีการใช้การเรียกซ้ำสามารถแทนที่ได้ด้วยการวนซ้ำหากจำเป็น ในความเป็นจริง การเรียกซ้ำและการวนซ้ำมักใช้เป็นวิธีการชดเชยซึ่งกันและกัน โดยเฉพาะอย่างยิ่งเมื่ออีกวิธีหนึ่งผิดพลาด เทคโนโลยีการแปลงอัลกอริธึมแบบเรียกซ้ำเป็นอัลกอริธึมแบบวนซ้ำก็ไม่ขึ้นอยู่กับภาษาการพัฒนาด้วย อย่างไรก็ตาม ความสำคัญใน JavaScript นั้นยิ่งใหญ่กว่า เนื่องจากทรัพยากรของสภาพแวดล้อมการดำเนินการนั้นมีข้อจำกัดมาก เรามาทบทวนอัลกอริทึมแบบเรียกซ้ำทั่วไป เช่น การใช้การเรียงลำดับแบบผสาน การใช้อัลกอริทึมนี้ใน JavaScript ต้องใช้โค้ดต่อไปนี้:
function merge(left, right.length){ var result = []; while (left.length > 0 && right.length > 0) { if (left[0] < right[0]){ result.push(left.shift()); } else { result.push(right.shift()); } } ส่งคืน result.concat(left ).concat (right);}//ผสานฟังก์ชันอัลกอริธึมการเรียงลำดับ mergeSort(items){ if (items.length == 1) { return items; } var middle = Math.floor(items.length / 2) โดยใช้การเรียกซ้ำ , left = items Slice(0, middle), right = items.slice(middle); return merge(mergeSort(left), mergeSort(right));} เรียกใช้ฟังก์ชัน mergeSort() เพื่อประมวลผลอาร์เรย์ และคุณสามารถส่งคืนอาร์เรย์ที่เรียงลำดับแล้วได้ โปรดทราบว่าทุกครั้งที่เรียกใช้ฟังก์ชัน mergeSort() จะมีการเรียกซ้ำสองครั้ง อัลกอริธึมนี้ไม่สามารถปรับให้เหมาะสมโดยใช้การจดจำ เนื่องจากแต่ละผลลัพธ์ได้รับการคำนวณและใช้เพียงครั้งเดียว และแม้แต่การบัฟเฟอร์ผลลัพธ์ก็ไม่มีประโยชน์ หากคุณใช้ฟังก์ชัน mergeSort() กับอาร์เรย์ที่มี 100 องค์ประกอบ จะมีการเรียกทั้งหมด 199 ครั้ง อาร์เรย์ที่มีองค์ประกอบ 1,000 รายการจะดำเนินการเรียกในปี 1999 ในกรณีนี้ วิธีแก้ไขของเราคือการแปลงอัลกอริธึมแบบเรียกซ้ำให้เป็นอัลกอริธึมแบบวนซ้ำ ซึ่งหมายถึงการแนะนำลูปบางส่วน (สำหรับอัลกอริธึม คุณสามารถอ้างอิงถึงบทความนี้ "การประมวลผลรายการ: เรียงลำดับอีกครั้งโดยธรรมชาติ"):
// ใช้การดำเนินการวนซ้ำ ฟังก์ชันอัลกอริทึมการเรียงลำดับผสาน mergeSort(items){ if (items.length == 1) { return items; } var work = []; for (var i=0, len=items.length; i < len; i++){ work .push([items[i]]); } work.push([]); //ในกรณีที่มีจำนวนรายการคี่สำหรับ (var lim=len; lim > 1; lim = (lim+1)/2 ) { สำหรับ (var j=0,k=0; k <lim; j++, k+=2){ งาน[j] = ผสาน(งาน[k], งาน[k+1]); } งาน[j] = [ ]; // ในกรณีที่มีจำนวนรายการเป็นคี่ } return work[0];}การใช้อัลกอริทึมการเรียงลำดับแบบผสานนี้ใช้ชุดของลูปแทนการเรียกซ้ำสำหรับการเรียงลำดับ เนื่องจากการเรียงลำดับแบบผสานจะแยกอาร์เรย์ออกเป็นหลายอาร์เรย์โดยมีเพียงองค์ประกอบเดียวเท่านั้น วิธีนี้จะดำเนินการนี้อย่างชัดเจนยิ่งขึ้น แทนที่จะใช้ฟังก์ชันแบบเรียกซ้ำโดยปริยาย อาร์เรย์งานถูกเตรียมใช้งานเพื่อให้มีอาร์เรย์ของอาร์เรย์องค์ประกอบเดียว แต่ละครั้งที่อยู่ในลูป อาร์เรย์ทั้งสองจะถูกรวมเข้าด้วยกัน และผลลัพธ์ที่ผสานจะถูกใส่กลับเข้าไปในอาร์เรย์งาน เมื่อฟังก์ชันถูกดำเนินการ ผลลัพธ์ที่เรียงลำดับจะถูกส่งกลับผ่านองค์ประกอบแรกในอาร์เรย์งาน ในการใช้งานการเรียงลำดับแบบผสานนี้ อัลกอริธึมจะถูกนำไปใช้โดยไม่ต้องใช้การเรียกซ้ำใดๆ อย่างไรก็ตาม สิ่งนี้ทำให้เกิดการวนซ้ำจำนวนมาก และจำนวนการวนซ้ำจะขึ้นอยู่กับจำนวนขององค์ประกอบในอาร์เรย์ที่จะเรียงลำดับ ดังนั้นเราอาจจำเป็นต้องแก้ไขโดยใช้เทคนิคที่กล่าวถึงในบทความก่อนหน้านี้เพื่อจัดการกับค่าใช้จ่ายเพิ่มเติมนี้ .
เพื่อสรุปหลักการพื้นฐาน คุณควรระมัดระวังทุกครั้งในการใช้การเรียกซ้ำ การท่องจำและการวนซ้ำเป็นสองวิธีในการแทนที่การเรียกซ้ำ ผลลัพธ์ที่ตรงที่สุดคือการหลีกเลี่ยงกล่องโต้ตอบที่แจ้งให้สคริปต์ไม่อยู่ในการควบคุม