JavaScript: Memoization

Function สามารถเก็บผลลัพย์ที่เคยผ่านการประมวลผลมาก่อนหน้านี้แล้วไว้ที่ object ได้ นี่คือวิธีการเพิ่มประสิทธิภาพที่เรียกกันว่า Memoization

เราลองทำตัวอย่าง function คำนวณอนุกรมแบบ Fibonacci ดู

var times = 0;// ไว้นับจำนวนครั้งที่เรียก function
var fibonacci = function (n) {

++times;
return n < 2 ? n : fibonacci(n – 1) + fibonacci(n – 2);// ที่คือการเขียนแบบ recursive  ปกติ

};

จากตัวอย่าง เรากำหนดตัวแปร times ไว้นับครั้งที่เรียกผ่าน function Fibonacci ไว้ด้วย เมื่อลองเรียกให้คำนวณดูละ

var result = fibonacci(10);
console.log(“fibonacci(10) = ” + result + “, call = ” + times + ” times”);// fibonacci(10) = 55, call = 177 times

จะได้จำนวนครั้งที่เรียก function fibonacci นี้ 177 ครั้ง

แล้วเมื่อเพิ่มประสิทธิภาพด้วยการใช้ Memoization ดู โดยเริ่มจาก เขียน function memoizer เพื่อไว้จดจำผลลัพย์ที่เคยคำนวณแล้วไว้ก่อน

var memoizer = function (memo, formula) {

var recur = function (n) {

var result = memo[n];
if (typeof result !== ‘number’) {

result = formula(recur, n);
memo[n] = result;

}
return result;

};
return recur;

};

นำ function memoizer มาประยุกต์ใช้เข้ากับการคำนวณอนุกรมแบบ fibonacci แบบนี้

var fibonacci = memoizer([0, 1], function (recur, n) {

++times;
return recur(n – 1) + recur(n – 2);

});

เมื่อลองเรียกใช้ดูอีกครั้ง

var result = fibonacci(10);
console.log(“fibonacci(10) = ” + result + “, call = ” + times + ” times”);// fibonacci(10) = 55, call = 9 times

จะเห็นว่าลดเวลาเรียก function เหลือแค่ 9 ครั้งเท่านั้น

ตัวอย่างประยุกต์ใช้ function memoizer กับการคำนวณค่า factorial ได้ด้วย แบบนี้

var factorial = memoizer([1, 1], function (recur, n) {

return n * recur(n – 1);

});

ขอบคุณความรู้จาก

JavaScript: The Good Parts

บันทึกโดย

— #:P —

Advertisements

#javascript