Advanced Generator Functions – Python Iterables Part 3 of N

หากผู้อ่านท่านใดเคยอ่านบทความตอนเก่าในซีรีส์นี้ ก็คงจะเคยหมดแรงกันมาแล้ว ( ⁠ผู้เขียนเองก็หอบจนหมดเวลาไปหลายเดือนอะ คิดดูสิ ⁠)

ในบทความนี้ ผู้เขียนเองก็จะลองนำเสนอเนื้อหาในรูปแบบใหม่ ๆ ดูบ้าง

บทความนี้จะพูดถึงอะไร

ส่วนหนึ่งในบทความที่แล้ว ผู้เขียนกล่าวถึงการเขียน generator function ขึ้นมาใช้งานเพื่อช่วยประมวลผลชุดลำดับของข้อมูลได้อย่างมีอิสระมากขึ้น ซึ่งได้ทั้งประสิทธิภาพการทำงานของโค้ดที่ดี ( ⁠efficiency ⁠) มีความยืดหยุ่นในการใช้งาน ( ⁠flexibility ⁠) และทำให้โค้ดแกนกลางของเราอ่านเข้าใจง่ายคล้ายภาษามนุษย์มากขึ้น ( ⁠readability ⁠)

ในบทความนี้เราจะมาโชว์ให้ดูวิธีการเขียน generator function ที่ซับซ้อนมากขึ้น  แต่เราจะพูดเรื่องนามธรรมลอย ๆ ได้ไม่ชัดเจนหากเราไม่มีตัวอย่างของโจทย์ที่จะช่วยทำให้ผู้อ่านเห็นภาพได้ง่ายขึ้น  ฉะนั้นแล้ว ขอแนะนำให้รู้จักกับโจทย์ตัวอย่างดังต่อไปนี้กันก่อนเลย

โจทย์ Tower of Hanoi

โจทย์ Tower of Hanoi นี้เป็นโจทย์คลาสสิกที่มักใช้เพื่อสอนไอเดียพื้นฐานเกี่ยวกับความสัมพันธ์เวียนเกิด ( ⁠recursion ⁠) ซึ่งเป็นพื้นฐานในการเขียนโปรแกรมอย่างหนึ่ง

โจทย์มีอยู่ว่าเรามีเสาอยู่ 3 ต้น โดยที่เสาที่อยู่ทางซ้ายมือจะมีแผ่นจานเสียบอยู่ $n$ แผ่น ซึ่งวางซ้อนเรียงกันจากขนาดเล็กไปหาใหญ่ ดังที่แสดงในรูปข้างล่างนี้ ( ⁠ยกตัวอย่างสำหรับกรณี $n = 6$ ⁠)

เป้าหมายของเราคือ เราต้องการย้ายแผ่นจานทั้งหมด จากเสาที่อยู่ทางซ้ายมือ ไปยังเสาต้นทางด้านขวามือ โดยที่แผ่นจานทั้งหมดจะต้องวางซ้อนกันตามลำดับเดิม ดังรูปนี้

โดยเรามีเงื่อนไขว่า “เราสามารถย้ายแผ่นจานได้คราวละ 1 แผ่นเท่านั้น โดยจะต้องหยิบแผ่นจานจากบนสุดของกอนจานจากเสาต้นหนึ่ง ไปวางทับบนกองจานที่อยู่ที่เสาอีกต้นหนึ่ง และห้ามวางแผ่นจานขนาดใหญ่บนจานที่ขนาดเล็กกว่าโดยเด็ดขาด”

หากผู้อ่านอยากลองเล่น สามารถลองค้นหา Tower of Hanoi แบบที่เป็น online game เล่นดูก่อนได้  ในบทความนี้จะไม่ขอพูดถึงวิธีการแก้ปัญหานี้ มีบทความอื่น ๆ มากมายในอินเตอร์เน็ตที่พูดถึงหัวข้อนี้ได้ดีกว่าผู้เขียนเสียอีก แต่ผู้เขียนจะขอกล่าวถึงเทคนิคในการ implement recursive solution ด้วย generator function ซึ่งจะกล่าวเป็นลำดับถัดไป

1st Implementation: พิมพ์คำตอบโดยตรง

ก่อนอื่นเลย เราจะมาดู implementation อย่างง่ายที่สุด ซึ่งจะพิมพ์ move operation move operation หมายถึง ขั้นตอนวิธีแต่ละขั้นตอนที่เราขยับแผ่นจานจากเสาต้นหนึ่งไปสู่อีกต้นหนึ่ง ออกมาอย่างละหนึ่งบรรทัดจากภายในฟังก์ชันโดยตรง

def tower_of_hanoi_v1(n: int, src, dest, aux):
    """
    Solves Tower of Hanoi problem with n discs by moving all discs
    from the source rod to the destination rod while using
    the auxiliary rod as the helper rod.
    """
    assert n >= 1
    if n == 1:
        print(f"Move {src} to {dest}")
    else:
        tower_of_hanoi_v1(n - 1, src, aux, dest)
        print(f"Move {src} to {dest}")
        tower_of_hanoi_v1(n - 1, aux, dest, src)

>>> tower_of_hanoi_v1(3, 'A', 'B', 'C')
Move A to B
Move A to C
Move B to C
Move A to B
Move C to A
Move C to B
Move A to B

แม้ว่าโค้ดข้างตันจะถูกต้องและเรียบง่าย แต่ปัญหาใหญ่เลยคือเราไม่สามารถเอาขั้นตอน move operation ที่ใช้แก้ปัญหา Tower of Hanoi จากฟังก์ชันดังกล่าว ออกมาเป็นข้อมูลที่เอาไปใช้งานต่อได้

ดังนั้นแล้วในสเต็ปถัดไปเราจะเปลี่ยน print statement ภายในฟังก์ชัน ให้กลายเป็นการสร้างและรีเทิร์นลำดับของ move operation ทั้งหมดแทน

2nd Implementation: สร้าง list มาต่อกัน

ในโค้ดชุดใหม่นี้ เราจะเปลี่ยนให้ฟังก์ชัน tower_of_hanoi คืนคำตอบเป็น list ของ move operation ซึ่งเป็นคู่อันดับของเสาสองเสาว่า  จะต้องย้ายแผ่นจานจากเสาต้นใดไปยังเสาต้นใดตามลำดับ

from typing import Any, List, Tuple

def tower_of_hanoi_v1(n: int, src, dest, aux):
def tower_of_hanoi_v2(n: int, src, dest, aux) -> List[Tuple[Any, Any]]:
    """
    Solves Tower of Hanoi problem with n discs by moving all discs
    from the source rod to the destination rod while using
    the auxiliary rod as the helper rod.

    The result is a list of tuple pairs specifying the sequence
    of move operations (from_rod, to_rod).
    """
    assert n >= 1
    if n == 1:
        print(f"Move {src} to {dest}")
        ops = [(src, dest)]
    else:
        tower_of_hanoi_v1(n - 1, src, aux, dest)
        print(f"Move {src} to {dest}")
        tower_of_hanoi_v1(n - 1, aux, dest, src)
        ops = tower_of_hanoi_v2(n - 1, src, aux, dest)
        ops += [(src, dest)]
        ops += tower_of_hanoi_v2(n - 1, aux, dest, src)
    return ops

>>> ops = tower_of_hanoi_v2(3, 'A', 'B', 'C')
>>> ops
[('A', 'B'), ('A', 'C'), ('B', 'C'), ('A', 'B'), ('C', 'A'), ('C', 'B'), ('A', 'B')]
>>> for src, dest in ops:
...     print(f"Move {src} to {dest}")
Move A to B
Move A to C
Move B to C
Move A to B
Move C to A
Move C to B
Move A to B

ดูเผิน ๆ ว่าโค้ดใหม่นี้จะไม่มีปัญหาอะไร แต่หากเราลองวิเคราะห์โค้ดอย่างถี่ถ้วน จะพบว่า tower_of_hanoi_v2 ใช้เวลารันเป็น $O( ⁠n \cdot 2^n ⁠)$ เมื่อเทียบกับโค้ดเก่าอย่าง tower_of_hanoi_v1 ซึ่งใช้เวลาเพียง $O( ⁠2^n ⁠)$ เท่านั้น แต่หากผู้อ่านลองรันเองจริง อาจให้ผลลัพธ์ที่ต่างออกไป ตรงนี้เนื่องจาก bottleneck ที่เกิดจากการเขียนข้อความลงใน standard output buffer นั่นก็เพราะว่าการนำ list มาต่อกันแต่ละครั้งมีค่าใช้จ่ายเป็นเวลาแบบเชิงเส้น ( ⁠linear ⁠) ไม่ใช่ค่าคงที่ ( ⁠constant ⁠)

    else:
        ops = tower_of_hanoi(n - 1, src, aux, dest)
        ops += [(src, dest)]
        ops += tower_of_hanoi(n - 1, aux, dest, src)
    return ops

เรามีทางแก้อยู่หลายวิธีด้วยกัน วิธีที่ได้ผลทันทีคือ เราย้ายไปใช้งาน linked list แทน ซึ่งจะมีค่าใช้จ่ายในการนำ list มาต่อกันเป็น constant  แต่ว่าการบริหารจัดการ linked list ในภาษา Python ไม่สามารถทำได้ง่าย

ดังนั้นในสเต็ปถัดไป เราจะปรับเปลี่ยนฟังก์ชันให้มีการส่ง accumulator accumulator เป็นศัพท์เทคนิคที่หมายถึงลิสต์ที่เอาไว้เก็บสะสมข้อมูล โดยเฉพาะอย่างยิ่งในการทำงานของ recursive function ข้ามไป-มาหากันใน recursion เพื่อเก็บสะสม move operation ที่พบตามลำดับ

3rd Implementation: สร้าง list เก็บสะสม

ในโค้ดชุดใหม่นี้ เราจะสร้างฟังก์ชันอีกอัน ชื่อว่า _rec_tower_of_hanoi เพื่อทำ recursion แทนฟังก์ชัน tower_of_hanoi หลัก และอนุญาตให้มีการส่งต่อ accumulator ข้ามไป-มาหากันได้

from typing import Any, List, Tuple

def tower_of_hanoi_v2(n: int, src, dest, aux) -> List[Tuple[Any, Any]]:
def tower_of_hanoi_v3(n: int, src, dest, aux) -> List[Tuple[Any, Any]]:
    """
    Solves Tower of Hanoi problem with n discs by moving all discs
    from the source rod to the destination rod while using
    the auxiliary rod as the helper rod.

    The result is a list of tuple pairs specifying the sequence
    of move operations (from_rod, to_rod).
    """
    accm = []
    _rec_tower_of_hanoi(accm, n, src, dest, aux)
    return accm

def _rec_tower_of_hanoi(accm: List[Tuple[Any, Any]], n: int, src, dest, aux):
    assert n >= 1
    if n == 1:
        ops = [(src, dest)]
        accm.append((src, dest))
    else:
        ops = tower_of_hanoi_v2(n - 1, src, aux, dest)
        ops += [(src, dest)]
        ops += tower_of_hanoi_v2(n - 1, aux, dest, src)
        _rec_tower_of_hanoi(accm, n - 1, src, aux, dest)
        accm.append((src, dest))
        _rec_tower_of_hanoi(accm, n - 1, aux, dest, src)

>>> ops = tower_of_hanoi_v3(3, 'A', 'B', 'C')
>>> ops
[('A', 'B'), ('A', 'C'), ('B', 'C'), ('A', 'B'), ('C', 'A'), ('C', 'B'), ('A', 'B')]
>>> for src, dest in ops:
...     print(f"Move {src} to {dest}")
Move A to B
Move A to C
Move B to C
Move A to B
Move C to A
Move C to B
Move A to B

โค้ด tower_of_hanoi_v3 นี้สามารถทำงานให้ผลลัพธ์ได้เหมือนกัน tower_of_hanoi_v2 และมีประสิทธิภาพดีเทียบเท่า tower_of_hanoi_v1 ได้สำเร็จ

เอาล่ะ พูดมาเสียยาว แต่เรายังไม่ได้เสนอวิธีแก้ปัญหา Tower of Hanoi โดยใช้ generator function เลย  เรามาดูกันดีกว่าว่าหากเราต้องการให้ฟังก์ชัน tower_of_hanoi รีเทิร์นลำดับของ move operation ออกมาเป็นวัตถุ iterable จะทำได้อย่างไร

4th Implementation: ใช้ generator function

เราข้ามไปดูโค้ดกันก่อนเลย

from typing import Any, Iterator, Tuple

def tower_of_hanoi_v4(n: int, src, dest, aux) -> Iterator[Tuple[Any, Any]]:
    """
    Solves Tower of Hanoi problem with n discs by moving all discs
    from the source rod to the destination rod while using
    the auxiliary rod as the helper rod.

    The result is an iterator of tuple pairs specifying the sequence
    of move operations (from_rod, to_rod).
    """
    assert n >= 1
    if n == 1:
        yield src, dest
    else:
        yield from tower_of_hanoi_v4(n - 1, src, aux, dest)
        yield src, dest
        yield from tower_of_hanoi_v4(n - 1, aux, dest, src)

>>> ops = tower_of_hanoi_v4(3, 'A', 'B', 'C')
>>> ops
<generator object tower_of_hanoi_v4 at 0x7fc0dec0ffee>
>>> for src, dest in ops:
...     print(f"Move {src} to {dest}")
Move A to B
Move A to C
Move B to C
Move A to B
Move C to A
Move C to B
Move A to B

ฮั่นแน่ ⁠… อย่างที่สังเกตเห็น ฟังก์ชัน tower_of_hanoi_v4 นี้มีความคล้ายคลึงกับโค้ด 2 เวอร์ชันแรกมากกว่าโค้ดชุดล่าสุดอย่างฟังก์ชัน tower_of_hanoi_v3 เสียด้วยซ้ำ

แต่ผู้อ่านอาจจะสงสัยว่า คำสั่ง yield from ในภาษา Python คืออะไรและมีการทำงานอย่างไร  จะขออธิบายโดยนำคำสั่งดังกล่าวมาเปรียบเทียบกับคำสั่ง yield ดังนี้

• คำสั่ง yield <item_expression> ทำหน้าที่คืนค่าวัตถุที่เกิดจากการประมวลผล <item_expression> ออกเป็นสมาชิกค่าหนึ่งของ generator object
• คำสั่ง yield from <iterable_expression> ทำหน้าที่คืนค่าวัตถุหลายค่าที่เกิดจากการประมวลผล <iterable_expression> ออกมาเป็นสมาชิกของ generator object ทีละตัว

ฟังก์ชัน tower_of_hanoi_v4 นี้ นอกจากจะดูเรียบง่ายกว่า tower_of_hanoi_v3 แล้วนั้น ยังให้ผลลัพธ์เป็น generator object ซึ่งเป็นวัตถุ iterable ที่มีประโยชน์ใช้สอยได้หลากหลายกว่าการที่ฟังก์ชันรีเทิร์นค่าเป็น list ดังที่เคยเล่าในบทความตอนนี้แล้ว

>>> list(tower_of_hanoi_v4(3, 'A', 'B', 'C'))
[('A', 'B'), ('A', 'C'), ('B', 'C'), ('A', 'B'), ('C', 'A'), ('C', 'B'), ('A', 'B')]

แบบฝึกหัด: โจทย์ Binary Tree Traversal

ผู้อ่านสามารถลองทำแบบฝึกหัดนี้ง่าย ๆ ใน Google Colab หรืออาจจะเข้าถึงไฟล์ Notebook โดยตรง ( ⁠คำใบ้: เขียนไม่เกิน 5 บรรทัดต่อ 1 ฟังก์ชัน ⁠)

แล้วพบกันในโอกาสต่อไปครับ