ลองใช้ Recursive ในปัญหา Pascal Triangle

ลองเอาโจทย์ pascal triangle มาให้ทีมลองเล่นกันตอนทำ code kata รายละเอียดคือ ให้แสดง pascal triangle ตามความสูงที่กำหนด โดยหน้าตาของ pascal triangle จะเป็นแบบนี้

นั่นคือที่ความสูง 1 (h = 1) จะแสดงแค่ “1” ออกมาเฉย ๆ และเมื่อ h = 2 จะแสดงบรรทัดแรกเป็น “1” และบรรทัดที่ 2 เป็น “1 1” ส่วนบรรทัดที่เหลือ จะมีแค่ตัวแรก และตัวสุดท้ายเป็น 1 ส่วนตัวตรงกลาง จะเป็นผลบวกที่เกิดจาก 2 ตัวด้านบนของบรรทัดก่อนหน้ามาบวกกัน

ยกตัวอย่างจากในรูป ที่ h = 6 ในบรรทัดล่างสุดที่เป็นเลข 10 จะเกิดจาก 4 กับ 6 ที่อยู่ด้านบนมาบวกกันนั่นเอง

เล่นกับโจทย์ด้วยลูปธรรมดา

ทีนี้ถ้าเรามองโจทย์นี้แล้วมาเขียนลูปก็น่าจะออกมาประมาณนี้

func printPascalLoop(lines int) {
    arr := [][]int{}

    for line := 0; line < lines; line++ {
        arr = append(arr, []int{})
        for i := 0; i <= line; i++ {
            if i == 0 || i == line {
                arr[line] = append(arr[line], 1)
            } else {
                arr[line] = append(arr[line], arr[line-1][i-1]+arr[line-1][i])
            }
            if i > 0 {
                fmt.Print(" ")
            }
            fmt.Print(arr[line][i])
        }
        fmt.Println()
    }
}

เล่นกับโจทย์ด้วย recursive function

ทีนี้ ถ้าลองมองโจทย์นี้ทีละบรรทัด คือ มี function ที่บอกได้ว่า ที่บรรทัดที่ h ควรจะต้อง print ค่าอะไรออกมา นั่นคือ ตอนเราจะ print pascal triangle เราก็แค่วนลูปเรียกทีละบรรทัดนั่นเอง แบบนี้

func printPascal(lines int) {
    for i := 1; i <= lines; i++ {
        line := pascaltriangle.PascalLine(i)
        for j, n := 0, len(line); j < n; j++ {
            if j > 0 {
                fmt.Print(" ")
            }
            fmt.Print(line[j])
        }
        fmt.Println()
    }
}

ดังนั้นประเด็นมันจะอยู่ที่ PascalLine จะต้องคืนค่าอะไรกลับมา จากนิยามของ pascal triangle เราจะเห็นลักษณะของ 2 บรรทัดแรก และลักษณะของบรรทัดที่ 3 เป็นต้นไป กับบรรทัดก่อนหน้า เราเลยสามารถเขียนเป็น recursive function ได้แบบนี้

func PascalLineRecursive(line int) []int {
    if line == 1 {
        return []int{1}
    }
    if line == 2 {
        return []int{1, 1}
    }

    prevLine := PascalLineRecursive(line - 1)
    result := []int{1}

    for i, n := 0, len(prevLine)-1; i < n; i++ {
        result = append(result, prevLine[i]+prevLine[i+1])
    }

    result = append(result, 1)

    return result
}

โดยมี line เป็น 1 และ 2 เป็น base case ส่วน line ตั้งแต่ 3 ขึ้นไปเป็น recursion ทีนี้ ถ้าเราสังเกตให้ดี เราจะเห็นว่าใน recursive นี้มี cost ที่สูงมาก เพราะที่บรรทัดที่ n มันจะต้องไปคำนวณค่าของบรรทัดที่ n – 1 มาก่อน ทั้ง ๆ ที่บรรทัดก่อนหน้านี้มันได้เคยคำนวณไว้แล้ว

ใส่ cache

เทคนิคหนึ่งที่เราสามารถเอามาใช้ได้คือการใส่ cache เพื่อเพิ่มความเร็วในการคำนวณ เทคนิคนี้มีชื่ออย่างเป็นทางการว่า Memoization หรือ Tabling เป็นการทำ table หรือ array มาใช้ในการเก็บผลลัพธ์จากการคำนวณที่มี cost ในการคำนวณสูง ๆ เราจะได้ recursive ที่มี cache หน้าตาแบบนี้

var memoTable = map[int][]int{}

func PascalLineMemo(line int) []int {
    if v, ok := memoTable[line]; ok {
        return v
    }

    if line == 1 {
        return []int{1}
    }
    if line == 2 {
        return []int{1, 1}
    }

    prevLine := PascalLineMemo(line - 1)
    result := []int{1}

    for i, n := 0, len(prevLine)-1; i < n; i++ {
        result = append(result, prevLine[i]+prevLine[i+1])
    }

    result = append(result, 1)

    memoTable[line] = result

    return result
}

ประสิทธิภาพก่อน cache และหลัง cache

ทดสอบด้วย benchmark ได้ผลลัพธ์แบบนี้

จะเห็นได้ว่า หลังจากใส่ cache แล้ว ประสิทธิภาพเพิ่มขึ้นทั้งด้านความเร็ว และ memory ที่ใช้เลย

แค่นี้แหละ จบ

โค้ด

https://github.com/chonla/pascaltriangle

Leave a Reply

Your email address will not be published. Required fields are marked *