เคยเขียน Function ที่ต้อง Process นาน ๆ แต่เรียกใช้บ่อย ๆ ไหมครับ
เมื่อเจอเหตุการนี้ เรามักจะเอาผลลัพธ์ที่ได้จาก Function ไปเก็บไว้สักที่ เช่น ใน Dictionary
พอเวลาเรียกใช้ Function นั้นอีก ก็ไปหาคำตอบใน Dictionary แทน ซึ่งเร็วกว่า
การทำให้ Function จำคำตอบได้แบบนี้ เราเรียกกันว่า Memoization

ข่าวดีคือ คุณไม่ต้องไปแก้ไข Function ของคุณเพื่อทำ Memoization
ผมมีวิธีการง่าย ๆ มานำเสนอ ซึ่งจะทำให้ Function ของคุณจำคำตอบได้แบบไม่เคยเป็นมาก่อน
เพียงแค่คุณเพิ่ม Code ข้างล่างนี้ ไปไว้ใน Class สำหรับทำ Extension Methods ของคุณ

public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> func) {
    var dict = new Dictionary<T, TResult>();
    return arg => {
        TResult value;
        if (!dict.TryGetValue(arg, out value)) {
            value = func(arg);
            dict.Add(arg, value);
        }
        return value;
    };
}

แต่มีข่าวร้ายคือ Method ด้านบน ใช้ได้กับ Function ที่เป็น anonymous method เท่านั้น
มาดูวิธีใช้กัน สมมติว่าเรามี Function นึง ใช้สำหรับหาค่าของลำดับ Fibonacci
โดยที่ Input เป็น ลำดับของ Fibonacci

สูตรของ Fibonacci มีอยู่ว่า


(รูปจาก wikipedia.org)

ถ้าเราจะหาลำดับที่ 38 เขียนดังนี้

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Console.WriteLine(fib(38));
//39088169
//ใช้เวลา 2.35 วินาที

ทำไมใช้ตั้ง 2 วินาทีกว่า !?
เนื่องจาก Function นี้ เป็น Function ที่เป็น Recursion มีการเรียกตัวเองหลายครั้ง
เรามาลองทำ Memoization กัน เผื่อช่วยได้

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
fib = fib.Memoize();
Console.WriteLine(fib(38));
//39088169
//ใช้เวลาแค่ 0.01 วินาที!!

เพิ่มแค่บรรทัดที่ 3 เข้าไป เร็วขึ้นกว่าเดิมทันตาเห็น!
เรามาดูกันว่ามันเร็วขึ้นได้อย่างไร
โดยการเพิ่มตัวแปร i เข้าไป โดยที่ i จะเพิ่มทุก ๆ ครั้งที่เรียก Function

Func<int, int> fib = null;
int i = 0;
fib = n => (n > 1 ? fib(n - 1) + fib(n - 2) : n) + (0 * i++);
Console.WriteLine(fib(38));
Console.WriteLine(i);
//39088169
//126491971

เมื่อดูผลลัพธ์ จะเห็นว่ามีการเรียก Function ถึง 126 ล้านครั้ง !!!
คราวนี้มาลองทำ Memoization ดูบ้าง

Func<int, int> fib = null;
int i = 0;
fib = n => (n > 1 ? fib(n - 1) + fib(n - 2) : n) + (0 * i++);
fib = fib.Memoize();
Console.WriteLine(fib(38));
Console.WriteLine(i);
//39088169
//39

หลังจากทำ Memoization มีการเรียก Function แค่ 39 ครั้ง!
น้อยกว่ากันกว่า 3 ล้านเท่า!!
ที่เป็นอย่างนี้เพราะว่า Function Fibonacci มีการเรียกตัวเองซ้ำไปซ้ำมา เช่น

fib(38) = fib(37) + fib(36)
fib(38) = [fib(36) + fib(35)] + [fib(35) + fib(34)]
fib(38) = [[fib(35) + fib(34)] + [fib(34) + fib(33)]] +
          [[fib(34) + fib(33)] + [fib(33) + fib(32)]]

จะเห็นว่านี่แตก Function ออกมาแค่ 3 ระดับ ก็พบการเรียกซ้ำมากมาย
เมื่อแตกไปเรื่อย ๆ จะมีการเรียกตัวเองถึง 126 ล้านครั้ง!!
การเติบโตของ Function นี้ เรียกได้ว่าเป็นการเติบโตแบบ Exponential เลยทีเดียว

คราวนี้มาดูการทำงานของ Memoization

fib(38) = fib(37) + M(36)
fib(38) = [fib(36) + M(35)] + M(36)
fib(38) = [[fib(35) + M(34)] + M(35)] + M(36)

ดูเรียบง่ายมากเลยใช่ไหมครับ
M หมายถึง การอ่านจาก Dictionary ไม่ต้อง Process Function
ทำให้เกิดการเรียกตัวเองแค่ 39 ครั้งเท่านั้น
เปลี่ยนจากการเติบโตแบบ Exponential เป็นแบบ Linear แทน

Code Memoization ด้านบน เป็น Code สำหรับ Function ที่มี Parameter แค่ตัวเดียว
ถ้าจะเพิ่ม Parameter เป็น 2 ตัว ก็เพิ่ม Method นี้เข้าไปใน Class สำหรับทำ Extension Methods

public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(this Func<T1, T2, TResult> func) {
    Func<T1, Func<T2, TResult>> curried = arg1 => func.Partial(arg1).Memoize();
    curried = curried.Memoize();
    return curried.Uncurry();
}

Code ด้านบนต้องการ Function ใน Post ที่แล้ว ด้วย
ในที่นี้เราใช้ Curry สำหรับแบ่ง Func(a1,a2) เป็น Func(a1)(a2)
ซึ่งในส่วนของ Curry มีการทำ Memoization กับ Func(a2) ก่อน 1 ที
แล้วค่อยมาทำ Memoization กับ Func(a1) อีก 1 ที
ทำให้ Func(a1)(a2) เป็น Memoization โดยสมบูรณ์
เสร็จแล้วก็ทำ Uncurry เพื่อแปลง Func(a1)(a2) กลับไปเป็น Func(a1, a2)

มาดูตัวอย่าง Memoization แบบ 2 Parameters กัน

คำถามจาก projecteuler.net นะครับ
สมมติว่ามีขี้เมาคนนึง เดินกลับบ้านซึ่งจากจุดเริ่มต้น ถึงบ้าน ห่างกัน 2x2 ซอย
ขี้เมาสามารถเดินกลับบ้าน (แบบไม่เดินวกกลับ) ได้ 6 วิธี ดังนี้


(รูปจาก projecteuler.net)

แต่ถ้าขี้เมาคนนั้นอยู่ห่างจากบ้าน 20x20 ซอยล่ะ
มีวิธีเดินกลับบ้านกี่วิธี?

จริง ๆ ข้อนี้มีสูตรการคิดคือ [(m + n)!]/[m! * n!]
แต่เราจะไม่ใช้สูตรนี้ เนื่องจากมันง่ายไป

เราลองมาสร้างสูตรคล้าย ๆ Fibonacci ด้านบนดู
ยึด F_m,n เป็นหลัก m คือ ความห่างจากบ้านในแนวนอน n คือ ความห่างจากบ้านในแนวตั้ง
แล้วดูความสัมพันธ์ที่จุด F_m,n กับจุดอื่น ๆ
จะพบว่าจุด F_m,n จะเชื่อมโยงกับจุด F_m-1,n และ F_m,n-1
นั่นคือการเดินไปทางขวา และการเดินลง
ดังนั้น ผลลัพธ์ของ F_m,n มาจาก 2 แหล่งคือ F_m-1,n กับ F_m,n-1
ทำให้เกิดสูตรดังนี้



เขียนเป็น Function ได้ดังนี้

Func<int, int, long> func = null;
func = (m, n) => func(m - 1, n) + func(m, n - 1);
func = func.When((m, n) => n == 0, (m, n) => func(m - 1, 0));
func = func.When((m, n) => m == 0, (m, n) => func(0, n - 1));
func = func.When((m, n) => m == 0 && n == 0, (m, n) => 1L);
func = func.Memoize();
Console.WriteLine(func(20, 20));
//137846528820

Method ชื่อ When เอามาจาก Post ที่แล้ว
Function ด้านบน ถ้าไม่มี Memoize จะเกิดการ Recursion กันมหาศาล
ซึ่งอาจใช้เวลาคำนวนนานเป็นวัน!!!
แต่ถ้ามี Memoize แล้ว ใช้เวลาคำนวนแค่เสี้ยววินาที

ถ้าใครสนใจวิธีการแตก Function เป็น Function ย่อย ๆ
แล้วใช้ Memoization ในการบันทึกค่าเพื่อเพิ่มความเร็ว แบบด้านบน
วิธีการแบบนี้เค้าเรียกกันว่า Dynamic Programming (DP) ครับ
สนใจลองศึกษาเพิ่มดูครับ :)

Post หน้า เกี่ยวกับ Linq แบบถึงกึ๋น!!

* อ่านจบแล้ว กรุณา Comment ด้วยครับ เพื่อเป็น Feedback และเป็นกำลังใจ
* บทความนี้คัดลอกได้ แต่ต้องมี Link หรือ Url กลับมาที่หน้านี้ และเมื่อคัดลอกแล้วกรุณา Comment แจ้งด้วยครับ

Create Date : 09 สิงหาคม 2551
Last Update : 23 สิงหาคม 2551 15:55:18 น.		7 comments
Counter : 2429 Pageviews.
Share Tweet