Array / String — พื้นฐาน & แนวคิด

list กับ string เป็นของสองอย่างที่เราใช้มาตั้งแต่วันแรกที่หัดเขียน Python จนรู้สึกว่าไม่มีอะไรต้องเรียนอีกแล้ว

แต่พอเจอโจทย์จริง หลายคนเขียนโค้ดที่ตอบถูกแต่ช้าเกินไป หรือเจอบั๊กที่ค่าในลิสต์เปลี่ยนเองทั้งที่ไม่ได้สั่ง อาการทั้งสองอย่างมาจากที่เดียวกัน คือเรารู้ว่า list กับ string ใช้ยังไง แต่ยังไม่รู้ว่ามันทำงานยังไง

หน้านี้จะพาไปดูตรงนั้น เริ่มจากความต่างข้อเดียวระหว่าง list กับ string แล้วค่อย ๆ ต่อยอดจนถึงวิธีแก้โจทย์ 6 แบบที่ใช้ครบทั้ง 9 ข้อในหมวดนี้

ส่วนที่ 1 · ความต่างข้อเดียวที่อธิบายทุกอย่างในหน้านี้

ลองนึกภาพ list เป็น แถวตู้ล็อกเกอร์ ที่มีเลขช่องติดอยู่ทุกช่อง เราเดินไปเปิดช่องที่ 3 แล้วเปลี่ยนของข้างในเป็นอย่างอื่นได้ ตู้ยังเป็นตู้แถวเดิม เลขช่องเดิม แค่ของข้างในเปลี่ยน

ส่วน string ให้นึกภาพเป็น ป้ายชื่อที่สลักด้วยเลเซอร์ ถ้าสลักคำว่า hello ไปแล้ว เราจะแก้ตัว h ให้เป็น H ไม่ได้เลย ทางเดียวคือทิ้งป้ายเดิมแล้วสลักป้ายใหม่ทั้งป้าย

ความต่างนี้มีชื่อเรียก: ของที่แก้ในที่เดิมได้เรียกว่า mutable (list เป็นแบบนี้) ของที่แก้ในที่เดิมไม่ได้เรียกว่า immutable (string เป็นแบบนี้) สองคำนี้จะโผล่ไปตลอดคอร์ส ตอนนี้ขอแค่จำภาพตู้ล็อกเกอร์กับป้ายสลักไว้ก่อน

มาดูของจริงกันว่าภาพสองภาพนี้ให้ผลต่างกันยังไงในโค้ด ลองเดาก่อนว่าบรรทัดที่ 3 (b.append(4)) จะทำให้ค่าของ a เปลี่ยนไหม

a = [1, 2, 3]
b = a                      # b ไม่ใช่สำเนา แค่ชื่ออีกชื่อของก้อนเดียวกัน
b.append(4)
print("a =", a, "| b =", b, "| a is b (ก้อนเดียวกันไหม):", a is b)

s = "hello"
t = s
before_id = id(t)
t = t + " world"           # += กับ str จริง ๆ คือสร้างสตริงใหม่ แล้วให้ชื่อ t ชี้ไปที่ใหม่
print("s =", repr(s), "| t =", repr(t))
print("s is t:", s is t, "| id(t) เปลี่ยนไหม:", id(t) != before_id)

try:
    s[0] = "H"
except TypeError as e:
    print("s[0] = 'H' ->", type(e).__name__ + ":", e)

a = [1, 2, 3, 4] | b = [1, 2, 3, 4] | a is b (ก้อนเดียวกันไหม): True
s = 'hello' | t = 'hello world'
s is t: False | id(t) เปลี่ยนไหม: True
s[0] = 'H' -> TypeError: 'str' object does not support item assignment

ถ้าเดาว่า a ไม่เปลี่ยน แปลว่าเดาผิด และไม่ต้องรู้สึกแย่เลย เพราะนี่คือจุดที่คนพลาดกันมากที่สุดเรื่องหนึ่งใน Python

สาเหตุคือบรรทัด b = a ไม่ได้สร้างตู้ล็อกเกอร์แถวใหม่ มันแค่ตั้งชื่อเล่นให้ตู้แถวเดิมอีกชื่อหนึ่ง ตอนนี้คำว่า a และ b หมายถึงตู้แถวเดียวกัน ใครไปเติมของเข้าไป อีกชื่อก็เห็นการเปลี่ยนแปลงนั้นด้วย

บรรทัด print(a is b) คือตัวยืนยัน คำว่า is ไม่ได้ถามว่า ค่าเท่ากันไหม แต่ถามว่า เป็นของก้อนเดียวกันไหม คำตอบ True บอกว่าใช่ ก้อนเดียวกันจริง

เรื่องนี้มีชื่อว่า aliasing (การมีหลายชื่อชี้ของก้อนเดียวกัน) และเป็นที่มาของบั๊กที่หาสาเหตุยากมาก แบบที่เจอบ่อยคือ: เราส่งลิสต์เข้าไปในฟังก์ชัน ฟังก์ชันแก้ลิสต์นั้น แล้วลิสต์ข้างนอกก็เปลี่ยนตามไปด้วยโดยที่เราไม่ได้สั่ง

ทีนี้มาดูฝั่ง string บรรทัด s[0] = "H" ขึ้น TypeError ทันที ตรงกับภาพป้ายสลักพอดี คือแก้ตัวอักษรเดี่ยว ๆ ไม่ได้

แต่บรรทัด t = t + " world" ทำงานได้ ทำไมล่ะ คำตอบคือมันไม่ได้แก้ป้ายเดิม มันสลักป้ายใหม่ทั้งป้ายแล้วย้ายชื่อ t ไปชี้ป้ายใหม่ ป้ายเก่ายังเป็น hello อยู่ไม่เปลี่ยน ซึ่งเห็นได้จาก s ที่ยังเป็น hello

บรรทัดที่ยืนยันเรื่องนี้คือ id(t) เปลี่ยนไหม ฟังก์ชัน id() บอกเลขประจำตัวของก้อนข้อมูล ถ้าเลขเปลี่ยน แปลว่าตอนนี้เป็นของคนละก้อนกับเมื่อกี้แล้ว ผลลัพธ์ True จึงเป็นหลักฐานว่ามีการสร้างก้อนใหม่จริง

ส่วนที่ 2 · การหยิบของออกมาดู: index กับ slice

กลับไปที่ภาพตู้ล็อกเกอร์ การหยิบของหนึ่งชิ้นคือเปิดช่องเดียว เขียนว่า nums[2] เรียกว่า indexing ส่วนการหยิบของหลายช่องติดกันมาทีเดียว เขียนว่า nums[1:3] เรียกว่า slicing

สองอย่างนี้ทุกคนเคยใช้ แต่มีสามพฤติกรรมที่คนมักไม่รู้ และทั้งสามอย่างจะกลับมาเป็นเรื่องสำคัญในโจทย์จริง ลองอ่านโค้ดข้างล่างแล้วเดาผลลัพธ์ทีละบรรทัดก่อนดูเฉลย

nums = [10, 20, 30, 40, 50]
print("nums          :", nums)
print("nums[-1]      :", nums[-1], " (ตัวสุดท้าย)")
print("nums[-2]      :", nums[-2])
print("nums[1:3]     :", nums[1:3], " (index 1,2 ไม่รวม 3)")
print("nums[:3]      :", nums[:3])
print("nums[2:]      :", nums[2:])
print("nums[::2]     :", nums[::2], " (ทุกตัวที่ 2)")
print("nums[::-1]    :", nums[::-1], " (กลับด้าน)")
print("nums[10:20]   :", nums[10:20], " (index เกินขอบ -> ไม่ error ได้ลิสต์ว่าง)")
print("nums[2:100]   :", nums[2:100], " (ปลายเกินขอบ -> ตัดแค่เท่าที่มี)")

nums          : [10, 20, 30, 40, 50]
nums[-1]      : 50  (ตัวสุดท้าย)
nums[-2]      : 40
nums[1:3]     : [20, 30]  (index 1,2 ไม่รวม 3)
nums[:3]      : [10, 20, 30]
nums[2:]      : [30, 40, 50]
nums[::2]     : [10, 30, 50]  (ทุกตัวที่ 2)
nums[::-1]    : [50, 40, 30, 20, 10]  (กลับด้าน)
nums[10:20]   : []  (index เกินขอบ -> ไม่ error ได้ลิสต์ว่าง)
nums[2:100]   : [30, 40, 50]  (ปลายเกินขอบ -> ตัดแค่เท่าที่มี)

สามพฤติกรรมที่ควรจดไว้จากผลลัพธ์ข้างบน

• index ติดลบ นับจากท้ายแถว nums[-1] คือตัวสุดท้าย nums[-2] คือตัวรองสุดท้าย ใช้แทนการเขียน nums[len(nums)-1] ที่ยาวกว่าและพลาดง่ายกว่า
• ตัวเลขท้ายของ slice ไม่ถูกนับรวม nums[1:3] ได้ช่อง 1 กับ 2 ไม่เอาช่อง 3 กฎนี้ทำให้ความยาวของผลลัพธ์เท่ากับ เลขท้าย ลบ เลขหน้า พอดี
• slice ไม่เคย error แม้ระบุเลขเกินขอบแถว nums[10:20] บนลิสต์ที่มี 5 ช่อง ได้ลิสต์ว่างเฉย ๆ ต่างจาก nums[10] ที่จะขึ้น IndexError ทันที

ข้อสุดท้ายนี้เป็นดาบสองคม ข้อดีคือโค้ดไม่พังกลางทาง ข้อเสียคือถ้าเราคำนวณช่วงผิด โปรแกรมจะไม่เตือนอะไรเลย แต่ได้ลิสต์ว่างมาแล้วคำตอบผิดแบบเงียบ ๆ

ต่อไปเป็นเรื่องที่สำคัญกว่าและคนไม่รู้กันเยอะ: เวลาเราเขียน part = nums[1:3] เราได้อะไรกลับมา — ได้หน้าต่างที่มองเข้าไปในลิสต์เดิม หรือได้ลิสต์ก้อนใหม่คนละก้อน

คำตอบคือ ได้ก้อนใหม่ กลับมาเสมอ ลองดูหลักฐาน

nums = [10, 20, 30, 40, 50]
part = nums[1:3]
part.append(999)
print("nums เดิม     :", nums, "<- ไม่กระทบ")
print("part          :", part)

arr = [1, 2, 3, 4, 5]
arr[1:3] = [7, 7, 7]        # แทน 2 ช่องด้วย 3 ช่อง
print("แทน 2 ช่องด้วย 3 ช่อง:", arr, "| ยาวขึ้นจาก 5 เป็น", len(arr))
arr[1:4] = []                # ลบช่วงออกด้วย slice assignment
print("ลบช่วงด้วย slice = []:", arr)

s = "python"
print('s[::-1]       :', s[::-1])
try:
    s[0:1] = "P"
except TypeError as e:
    print("s[0:1] = 'P' ->", type(e).__name__ + ":", e)

nums เดิม     : [10, 20, 30, 40, 50] <- ไม่กระทบ
part          : [20, 30, 999]
แทน 2 ช่องด้วย 3 ช่อง: [1, 7, 7, 7, 4, 5] | ยาวขึ้นจาก 5 เป็น 6
ลบช่วงด้วย slice = []: [1, 4, 5]
s[::-1]       : nohtyp
s[0:1] = 'P' -> TypeError: 'str' object does not support item assignment

ผลลัพธ์สองบรรทัดแรกยืนยันว่าได้ก้อนใหม่จริง เราเติม 999 ลงใน part แต่ nums ไม่กระทบเลย เพราะมันเป็นตู้คนละแถวแล้ว

แต่พอสลับข้างกัน เขียน slice ไว้ ทางซ้าย ของเครื่องหมายเท่ากับ เช่น arr[1:3] = [7, 7, 7] ความหมายเปลี่ยนไปเลย คราวนี้เป็นการสั่งแก้ลิสต์เดิมจริง ๆ และแก้ได้แรงถึงขั้นเปลี่ยนความยาวลิสต์ได้ด้วย (จาก 5 ช่องเป็น 6 ช่อง)

ท่านี้เรียกว่า slice assignment ใช้ลบของออกเป็นช่วงก็ได้ โดยกำหนดให้เป็นลิสต์ว่าง ตามที่เห็นในบรรทัด arr[1:4] = []

และตามที่คาดไว้ ฝั่ง string ทำท่านี้ไม่ได้ บรรทัด s[0:1] = "P" ขึ้น TypeError ตัวเดิม เพราะป้ายสลักแก้ไม่ได้

ส่วนที่ 3 · ทำไมบางคำสั่งบน list ถูก บางคำสั่งแพง

ตอนนี้มาถึงคำถามที่ทำให้โค้ดผ่านหรือไม่ผ่านเรื่องเวลา: ทำไม nums.append(x) ถึงเร็ว แต่ nums.insert(0, x) ถึงช้า ทั้งที่ดูเหมือนเป็นการเพิ่มของหนึ่งชิ้นเหมือนกัน

กลับไปที่ตู้ล็อกเกอร์อีกครั้ง แต่คราวนี้เพิ่มรายละเอียดสำคัญเข้าไป: ตู้แถวนี้ต้องเรียงติดกันเป็นแถวเดียวไม่มีเว้นช่อง และเลขช่องต้องเรียง 0, 1, 2, ... ไปเรื่อย ๆ ห้ามข้าม

กฎนี้ทำให้ การเปิดช่องไหนก็ได้ทันที เพราะรู้เลขช่องก็คำนวณได้เลยว่าต้องเดินไปตรงไหน ไม่ต้องไล่นับจากช่องแรก นี่คือเหตุผลที่ nums[500] เร็วเท่ากับ nums[0] เป๊ะ ๆ

แต่กฎเดียวกันนี้ก็ทำให้การ แทรกของที่หัวแถว แพงมาก เพราะถ้าจะยัดของใหม่ลงช่อง 0 ของเดิมทุกชิ้นต้องขยับไปทางขวาหนึ่งช่องก่อน ลิสต์มี 1,000 ช่องก็ต้องขยับ 1,000 ครั้ง เพื่อเพิ่มของแค่ชิ้นเดียว

เทียบให้เห็นภาพคือการเข้าคิว: ต่อท้ายคิว ทำได้เลยไม่รบกวนใคร แต่ แทรกหัวคิว ทำให้ทุกคนในคิวต้องถอยไปหนึ่งก้าว

ตารางข้างล่างสรุปราคาของคำสั่งที่ใช้บ่อย ตัวเลขในคอลัมน์ต้นทุนเขียนด้วยภาษา Big-O ซึ่งอ่านง่ายกว่าที่คิด: O(1) แปลว่าใช้เวลาเท่าเดิมไม่ว่าลิสต์จะยาวแค่ไหน ส่วน O(n) แปลว่าลิสต์ยาวขึ้นเท่าไหร่ งานก็เพิ่มขึ้นตามนั้น

สังเกตว่าช่อง append เขียนว่า "O(1) เฉลี่ย" ไม่ใช่ O(1) เฉย ๆ คำว่าเฉลี่ยตรงนี้ไม่ใช่การกันตัว แต่มีเหตุผลที่ต้องเข้าใจ

เพราะตู้ล็อกเกอร์ต้องเรียงติดกัน Python จึงไม่สามารถ ต่อ ช่องใหม่เข้าไปท้ายแถวได้เรื่อย ๆ (ข้าง ๆ อาจมีของอื่นจองที่อยู่แล้ว) ทางที่มันทำจริงคือ จองเผื่อไว้ล่วงหน้าหลายช่อง แล้วค่อย ๆ เติมของลงช่องที่เผื่อไว้

พอช่องที่เผื่อไว้เต็ม Python ต้องไปหาที่ว่างผืนใหม่ที่ใหญ่กว่า แล้ว ยกของทั้งแถวย้ายไปที่ใหม่ ครั้งนั้น append จึงแพงมาก ส่วนครั้งอื่น ๆ ที่ยังมีที่เผื่อเหลือ ก็ถูกมาก

เอามาเฉลี่ยกันแล้วยังถือว่าถูก คำที่ใช้เรียกสถานการณ์แบบนี้คือ amortized O(1) เทียบง่าย ๆ เหมือนค่าเช่าบ้านที่จ่ายก้อนใหญ่ปีละครั้ง ถ้าดูแค่เดือนที่จ่ายก็รู้สึกแพง แต่หารเฉลี่ยทั้งปีแล้วถือว่าคงที่

และเราวัดเรื่องนี้ให้เห็นตัวเลขได้จริง โดยใช้ sys.getsizeof ที่บอกว่าตอนนี้ Python จองที่ไว้เท่าไหร่ ถ้าตัวเลขนี้เปลี่ยน แปลว่าเพิ่งเกิดการย้ายของทั้งแถวไปที่ใหม่

import sys

def count_copies_append(n):
    """append: Python จองที่เผื่อไว้ล่วงหน้า พอเต็มต้องขยายและย้ายของทั้งก้อน"""
    lst, prev, copied, grows = [], sys.getsizeof([]), 0, 0
    for i in range(n):
        lst.append(i)
        cur = sys.getsizeof(lst)
        if cur != prev:              # ที่จองเปลี่ยน = เพิ่งขยาย = ย้ายของที่มีอยู่ i ตัว
            copied += i
            grows += 1
            prev = cur
    return grows, copied

def count_copies_insert_front(n):
    """insert(0, x): ต้องขยับของเดิมทุกตัวไปทางขวา 1 ช่อง ก่อนแทรกได้"""
    lst, copied = [], 0
    for i in range(n):
        copied += len(lst)
        lst.insert(0, i)
    return copied

print(f"{'n':>8} | {'append ขยาย':>12} | {'append ย้ายรวม':>15} | {'ต่อครั้ง':>9} | {'insert(0) ย้ายรวม':>18} | {'ต่อครั้ง':>9}")
for n in [1000, 10000, 100000]:
    grows, ca = count_copies_append(n)
    ci = count_copies_insert_front(n)
    print(f"{n:>8} | {grows:>12} | {ca:>15} | {ca/n:>9.1f} | {ci:>18} | {ci/n:>9.1f}")

       n |  append ขยาย |  append ย้ายรวม |  ต่อครั้ง |  insert(0) ย้ายรวม |  ต่อครั้ง
    1000 |           28 |            7556 |       7.6 |             499500 |     499.5
   10000 |           47 |           83136 |       8.3 |           49995000 |    4999.5
  100000 |           66 |          798128 |       8.0 |         4999950000 |   49999.5

คอลัมน์ที่ต้องดูคือคอลัมน์ ต่อครั้ง เพราะมันตอบคำถามว่า งานหนึ่งชิ้นแพงขึ้นตามขนาดข้อมูลไหม

ฝั่ง append ตัวเลขอยู่ราว ๆ 8 ค้างอยู่แค่นั้น ไม่ว่า n จะเป็นพันหรือแสน คือ ไม่โตตาม n เลย นั่นคือความหมายของ O(1) เฉลี่ย

ฝั่ง insert(0, x) ตัวเลขพุ่งจาก 500 เป็น 5,000 เป็น 50,000 คือ n ใหญ่ขึ้น 10 เท่า งานต่อครั้งก็หนักขึ้น 10 เท่าตาม นั่นคือ O(n) ต่อครั้ง

และถ้าเราเรียกของแพงชิ้นนี้ซ้ำ n ครั้งในลูป งานรวมก็กลายเป็น n คูณ n หรือ O(n²) ซึ่งคือจุดที่โค้ดเริ่มรันไม่ทันเวลาเมื่อข้อมูลใหญ่ขึ้น

อีกคอลัมน์ที่น่าดูคือ append ขยาย ซึ่งบอกว่าเรียก append หนึ่งล้านครั้ง เกิดการยกของย้ายที่แค่ 66 ครั้งเท่านั้น เพราะทุกครั้งที่ย้าย Python จะจองเผื่อมากขึ้นเรื่อย ๆ ไม่ได้เผื่อเท่าเดิมทุกครั้ง นี่คือกลไกที่ทำให้เฉลี่ยแล้วยังถูก

ส่วนที่ 4 · การต่อ string ในลูป — เรื่องที่ต้องรู้ก่อนเขียนโจทย์ string

เริ่มจากกฎที่เอาไปใช้ได้เลย แล้วค่อยดูเหตุผล: ถ้าต้องประกอบ string ทีละตัวอักษรในลูป อย่าเขียน s += c ให้เก็บชิ้นส่วนลง list ก่อน แล้วปิดท้ายด้วย "".join(...) ครั้งเดียว

เหตุผลย้อนกลับไปที่ส่วนที่ 1 ตรง ๆ string เป็นป้ายสลักที่แก้ไม่ได้ ดังนั้นการต่อ string หนึ่งครั้งไม่ใช่การเติมตัวอักษรลงป้ายเดิม แต่คือการสลักป้ายใหม่ที่ยาวขึ้นหนึ่งตัว แล้วคัดลอกตัวอักษรเดิมทั้งหมดลงป้ายใหม่

ลองคิดตามว่าถ้าทำแบบนี้ 5 รอบจะเกิดอะไรขึ้น รอบแรกคัดลอก 0 ตัว รอบสองคัดลอก 1 ตัว รอบสามคัดลอก 2 ตัว ไปเรื่อย ๆ ยิ่งสตริงยาว การคัดลอกแต่ละรอบยิ่งหนักขึ้น

ส่วน "".join(...) ต่างออกไป เพราะมันเห็นชิ้นส่วนทั้งหมดพร้อมกันตั้งแต่แรก จึงคำนวณความยาวรวมได้ทันที สลักป้ายเดียวจบ แล้วคัดลอกตัวอักษรแต่ละตัวแค่ครั้งเดียว

ตัวเลขข้างล่างคือการนับจำนวนการคัดลอกของสองวิธีนี้ ให้เห็นว่าช่องว่างถ่างขึ้นเร็วแค่ไหน

def naive_concat_cost(n):
    total_copied = 0
    length_so_far = 0
    for i in range(n):
        total_copied += length_so_far + 1   # คัดลอกของเดิมทั้งหมด + ตัวใหม่ 1 ตัว
        length_so_far += 1
    return total_copied

def join_cost(n):
    return n     # join รู้ความยาวรวมล่วงหน้า จึงคัดลอกแต่ละตัวอักษรแค่ครั้งเดียว

for n in [100, 1000, 10000]:
    nc, jc = naive_concat_cost(n), join_cost(n)
    print(f"n={n:<6} concat ทีละครั้งคัดลอกรวม {nc:<10} | join คัดลอกรวม {jc:<8} | ต่างกัน {nc//jc} เท่า")

n=100    concat ทีละครั้งคัดลอกรวม 5050       | join คัดลอกรวม 100      | ต่างกัน 50 เท่า
n=1000   concat ทีละครั้งคัดลอกรวม 500500     | join คัดลอกรวม 1000     | ต่างกัน 500 เท่า
n=10000  concat ทีละครั้งคัดลอกรวม 50005000   | join คัดลอกรวม 10000    | ต่างกัน 5000 เท่า

ที่ n เท่ากับ 10,000 ต่างกัน 5,000 เท่า และช่องว่างนี้ไม่มีเพดาน ยิ่งข้อมูลใหญ่ยิ่งถ่าง นี่คือเหตุผลที่กฎ ใช้ join เถอะ ถึงถูกบอกต่อกันมา

เจาะลึก (ข้ามได้) · ทำไมบางทีเขียน s += c แล้วดูไม่ช้า

ถ้าใครลองเอาโค้ด s += c ไปจับเวลาจริง จะพบเรื่องแปลก คือมันไม่ช้าอย่างที่ตารางข้างบนทำนาย ทำไมล่ะ

เพราะ CPython ซึ่งเป็นโปรแกรมที่รัน Python ที่เราใช้กันทั่วไป มีลูกเล่นพิเศษซ่อนอยู่ ถ้ามันตรวจว่าสตริงก้อนนั้น ไม่มีใครอื่นอ้างถึงอยู่เลยนอกจากตัวแปรเดียว มันจะแอบขยายป้ายเดิมในที่เดิมให้ แทนที่จะสลักป้ายใหม่

เราจับได้ว่ามันทำแบบนั้นจริง ด้วย id() ที่เราใช้ไปแล้วในส่วนที่ 1 ถ้า id ไม่เปลี่ยน แปลว่ายังเป็นป้ายเดิม ไม่ได้สลักใหม่

def count_new_objects(n, keep_extra_ref=False):
    s = ""
    prev_id = id(s)
    new_object_count = 0
    snapshots = []
    for i in range(n):
        s += "x"
        if keep_extra_ref:
            snapshots.append(s)      # เก็บ snapshot ทุกก้าว = มีคนอื่นถือ reference ของ s ด้วย
        if id(s) != prev_id:
            new_object_count += 1
        prev_id = id(s)
    return new_object_count

n = 20
print(f"n={n}")
print("ลูปธรรมดา (ไม่มีใครถือ reference เพิ่ม)   -> สร้างก้อนใหม่:", count_new_objects(n, False), "ครั้ง จาก", n, "รอบ")
print("มี snapshots ถือ reference ของ s ไว้ด้วย  -> สร้างก้อนใหม่:", count_new_objects(n, True), "ครั้ง จาก", n, "รอบ")

n=20
ลูปธรรมดา (ไม่มีใครถือ reference เพิ่ม)   -> สร้างก้อนใหม่: 3 ครั้ง จาก 20 รอบ
มี snapshots ถือ reference ของ s ไว้ด้วย  -> สร้างก้อนใหม่: 20 ครั้ง จาก 20 รอบ

ผลลัพธ์ฝั่งซ้ายบอกว่า วน 20 รอบ สร้างป้ายใหม่แค่ 3 ครั้ง แปลว่าลูกเล่นนี้ทำงานอยู่จริง

แต่ฝั่งขวาคือจุดสำคัญ เราแค่เพิ่มบรรทัดเดียวที่เก็บสตริงลง list ไว้ดูย้อนหลัง เท่ากับตอนนี้มีคนอื่นอ้างถึงสตริงนั้นด้วย ลูกเล่นก็หายไปทันที กลับไปสร้างป้ายใหม่ทุกรอบ 20 จาก 20

ส่วนที่ 5 · เครื่องมือติดตัวที่ต้องหยิบใช้ได้ทันที

สี่ส่วนแรกเป็นเรื่องกลไก ส่วนนี้เปลี่ยนเป็นเรื่องเครื่องมือ คือคำสั่งสำเร็จของ Python ที่ช่วยให้เราไม่ต้องเขียนลูปเองในเรื่องที่ภาษาเตรียมไว้ให้แล้ว

ทั้ง 9 ข้อในหมวดนี้ใช้อย่างน้อยหนึ่งตัวจากตารางนี้ ไม่ต้องท่องให้ครบตอนนี้ อ่านผ่านให้คุ้นตาก่อน แล้วจะเจอมันซ้ำอีกในทุกตัวอย่างหลังจากนี้

words = ["kiwi", "fig", "banana"]

print("sorted key=len         :", sorted(words, key=len))
print("sorted key=len reverse :", sorted(words, key=len, reverse=True))
print("reversed               :", list(reversed(words)))
print("any len>5              :", any(len(w) > 5 for w in words))
print("all len>2              :", all(len(w) > 2 for w in words))
print("max key=len            :", max(words, key=len), "| min key=len:", min(words, key=len))

s = "  Hello   World  "
print('s.split()      :', s.split(), " (แยกด้วย whitespace ใดก็ได้ ยุบช่องซ้ำ ตัดหัวท้ายให้)")
print('s.split(" ")   :', s.split(" "), " (แยกด้วยช่องว่างตรง ๆ เป๊ะ ไม่ยุบไม่ตัด)")
print(' " ".join(...) :', " ".join(["a", "b", "c"]))

print("ord('a')=", ord("a"), "ord('z')=", ord("z"), "chr(97)=", chr(97))
c = "d"
print(f"เลื่อน '{c}' ไปข้างหน้า 2 ตัว:", chr(ord(c) + 2))

sorted key=len         : ['fig', 'kiwi', 'banana']
sorted key=len reverse : ['banana', 'kiwi', 'fig']
reversed               : ['banana', 'fig', 'kiwi']
any len>5              : True
all len>2              : True
max key=len            : banana | min key=len: fig
s.split()      : ['Hello', 'World']  (แยกด้วย whitespace ใดก็ได้ ยุบช่องซ้ำ ตัดหัวท้ายให้)
s.split(" ")   : ['', '', 'Hello', '', '', 'World', '', '']  (แยกด้วยช่องว่างตรง ๆ เป๊ะ ไม่ยุบไม่ตัด)
 " ".join(...) : a b c
ord('a')= 97 ord('z')= 122 chr(97)= a
เลื่อน 'd' ไปข้างหน้า 2 ตัว: f

sorted() กับ .sort() ต่างกันยังไง

สองตัวนี้เรียงของได้เหมือนกัน แต่พฤติกรรมคนละเรื่อง และความต่างของมันคือเรื่องเดียวกับส่วนที่ 1 เป๊ะ ๆ

sorted(x) คือการ ทำสำเนาที่เรียงแล้วออกมาใหม่ ของเดิมไม่ถูกแตะ ใช้ได้กับทุกอย่างที่วนได้ รวมทั้ง string

ส่วน x.sort() คือการ จัดของในตู้แถวเดิมให้เรียง ของเดิมเปลี่ยนไปเลย จึงทำได้แค่กับ list เท่านั้น (string เป็นป้ายสลัก จัดเรียงในที่เดิมไม่ได้)

และมีกับดักหนึ่งที่ทำให้คนเสียเวลาหาบั๊กกันมาก: x.sort() ไม่คืนลิสต์กลับมา มันคืน None ลองดูว่าเกิดอะไรขึ้นถ้าเผลอเอาค่าที่มันคืนไปใช้ต่อ

nums = [3, 1, 2]

new = sorted(nums)          # คืนลิสต์ใหม่ ของเดิมไม่ถูกแตะ
print("sorted(nums) ->", new, "| nums เดิม:", nums)

ret = nums.sort()           # เรียงในที่เดิม และคืน None!
print("nums.sort() คืนค่า:", ret, "| nums หลังเรียง:", nums)

words = ["bb", "a", "ccc"]
result = words.sort()       # <- กับดักคลาสสิก
print("result = words.sort() ->", result, "<- ได้ None ไม่ใช่ลิสต์!")

s = "banana"                # str เรียงในที่เดิมไม่ได้ เพราะ immutable
print('sorted("banana") ->', sorted(s), "(ได้ list ไม่ใช่ str)")
print('"".join(sorted(s)) ->', "".join(sorted(s)))

sorted(nums) -> [1, 2, 3] | nums เดิม: [3, 1, 2]
nums.sort() คืนค่า: None | nums หลังเรียง: [1, 2, 3]
result = words.sort() -> None <- ได้ None ไม่ใช่ลิสต์!
sorted("banana") -> ['a', 'a', 'a', 'b', 'n', 'n'] (ได้ list ไม่ใช่ str)
"".join(sorted(s)) -> aaabnn

บรรทัด result = words.sort() ให้ None ไม่ใช่ลิสต์ ถ้าเผลอเอา result ไปใช้ต่อ โปรแกรมจะพังในบรรทัดถัดไปแบบที่ error ไม่ได้ชี้มาที่ต้นเหตุ วิธีจำง่าย ๆ คือ คำสั่งที่แก้ของเดิมมักไม่คืนอะไรกลับมา (append, sort, reverse เป็นแบบนี้ทั้งหมด)

อีกบรรทัดที่ควรจำคือ "".join(sorted(s)) เพราะ sorted() บน string คืน list ของตัวอักษร ไม่ได้คืน string ถ้าอยากได้ string กลับมาต้อง join ต่อท้ายเสมอ ท่านี้จะกลายเป็นหัวใจของการจัดกลุ่มคำที่สลับตัวอักษรกันได้ในหมวด Hash Map / Set

ส่วนที่ 6 · 6 วิธีคิดที่ใช้ครบทั้ง 9 ข้อ

ปัญหาที่คนเจอกันทุกคนคือ อ่านโจทย์จบแล้วไม่รู้จะเริ่มจากอะไร ไม่ใช่เพราะเขียนโค้ดไม่ได้ แต่เพราะยังไม่มีรายการวิธีคิดในหัวให้เลือกหยิบ

ส่วนนี้จะให้รายการนั้น มี 6 วิธี และครอบคลุมทั้ง 9 ข้อในหมวดนี้ พอเจอโจทย์ใหม่ เราจะเปลี่ยนคำถามในหัวจาก จะทำยังไงดี เป็น อันนี้มันแบบไหน ซึ่งตอบง่ายกว่ากันมาก

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

แบบที่ 1 · เดินรอบเดียว เห็นแล้วตัดสินใจเลย

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

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

ภาษาอังกฤษเรียกแนวคิดนี้ว่า greedy ซึ่งแปลว่าโลภ เพราะมันคว้าสิ่งที่ดีที่สุดตรงหน้าทันทีโดยไม่รอดูอนาคต

state = ค่าเริ่มต้น            # ตัวแปรไม่กี่ตัวที่จำสถานะล่าสุด
for x in data:
    if เงื่อนไขจาก x และ state:
        ตัดสินใจทันที           # ไม่มีการย้อนกลับมาคิดใหม่
        อัปเดต state

def can_place(bed, n):
    bed = bed[:]
    count = 0
    for i in range(len(bed)):
        left_empty = (i == 0) or (bed[i - 1] == 0)
        right_empty = (i == len(bed) - 1) or (bed[i + 1] == 0)
        if bed[i] == 0 and left_empty and right_empty:
            bed[i] = 1     # ตัดสินใจปลูกทันที ไม่ย้อนกลับมาคิดใหม่
            count += 1
    return count >= n

print("can_place([1,0,0,0,1], 1):", can_place([1, 0, 0, 0, 1], 1))
print("can_place([1,0,0,0,1], 2):", can_place([1, 0, 0, 0, 1], 2))
print("can_place([0], 1):", can_place([0], 1))

can_place([1,0,0,0,1], 1): True
can_place([1,0,0,0,1], 2): False
can_place([0], 1): True

ตรงนี้ต้องหยุดถามตัวเองก่อนว่า เห็นช่องว่างแล้วปลูกเลย จะพลาดไหม จะดีกว่าถ้าเว้นช่องนี้ไว้แล้วไปปลูกช่องถัดไปหรือเปล่า

คำตอบคือไม่พลาด และเหตุผลคือ: ตอนเราเดินมาถึงช่องนี้ ฝั่งซ้ายของมันถูกตัดสินไปเรียบร้อยแล้วและเปลี่ยนไม่ได้อีก ถ้าตอนนี้ปลูกได้แล้วเราไม่ปลูก ช่องนี้ก็เสียไปเปล่า ๆ เพราะเดินไปข้างหน้าแล้วไม่มีอะไรทำให้มันกลับมาปลูกได้อีก

การไม่ปลูกจึงไม่มีทางได้ดอกไม้มากกว่าการปลูก ในทางกลับกันการปลูกอาจปิดโอกาสของช่องขวาถัดไปหนึ่งช่อง แต่ช่องนั้นก็แลกมาด้วยดอกไม้หนึ่งดอกที่เราได้แล้ว จึงไม่ขาดทุน

การถามและตอบให้ได้แบบนี้คือขั้นตอนที่ห้ามข้าม ทุกครั้งที่จะใช้วิธีเดินรอบเดียว ต้องอธิบายให้ตัวเองฟังได้ว่าทำไมตัดสินใจตรงนี้แล้วไม่เสียหาย ถ้าอธิบายไม่ได้ แปลว่าโจทย์นั้นอาจต้องใช้วิธีอื่น

def increasing_triplet(nums):
    first = second = float("inf")
    for i, x in enumerate(nums):
        if x <= first:
            first = x
            note = "ตัวเล็กสุดใหม่"
        elif x <= second:
            second = x
            note = "ตัวรองเล็กสุดใหม่"
        else:
            print(f"  x={x} (i={i}) -> เจอตัวที่ 3 แล้ว! | first={first} second={second}")
            return True
        print(f"  x={x} (i={i}) -> {note} | first={first} second={second}")
    return False

print("increasing_triplet([2,1,5,0,4,6]):")
print(" ผลลัพธ์:", increasing_triplet([2, 1, 5, 0, 4, 6]))

increasing_triplet([2,1,5,0,4,6]):
  x=2 (i=0) -> ตัวเล็กสุดใหม่ | first=2 second=inf
  x=1 (i=1) -> ตัวเล็กสุดใหม่ | first=1 second=inf
  x=5 (i=2) -> ตัวรองเล็กสุดใหม่ | first=1 second=5
  x=0 (i=3) -> ตัวเล็กสุดใหม่ | first=0 second=5
  x=4 (i=4) -> ตัวรองเล็กสุดใหม่ | first=0 second=4
  x=6 (i=5) -> เจอตัวที่ 3 แล้ว! | first=0 second=4
 ผลลัพธ์: True

โค้ดนี้เก็บตัวแปรแค่สองตัวคือ first (ตัวเล็กสุดที่เคยเจอ) และ second (ตัวที่เล็กเป็นอันดับสอง โดยต้องอยู่หลัง first) ถ้าเจอตัวที่ใหญ่กว่าทั้งสองตัว ก็แปลว่าครบสามตัวเรียงเพิ่มขึ้นแล้ว

แต่มีจุดที่ดูเหมือนโค้ดพัง และเป็นจุดที่คนส่วนใหญ่สะดุด ลองดูบรรทัด i=3 ที่ค่า first ถูกเปลี่ยนจาก 1 เป็น 0 ทั้งที่ second เป็น 5 ซึ่งถูกตั้งไว้ตอน first ยังเป็น 1

ถ้าอ่านตามตัวอักษร ตอนนี้ first คือเลข 0 ที่อยู่ตำแหน่ง 3 ส่วน second คือเลข 5 ที่อยู่ตำแหน่ง 2 ซึ่ง second อยู่ ก่อน first ผิดกติกาที่เราตั้งไว้ตอนแรกเลย

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

พอไม่ต้องรายงานว่าใครคือใคร โค้ดจึงไม่จำเป็นต้องรักษาให้ first กับ second เป็นคู่ที่ถูกต้องตลอดเวลา ขอแค่ว่า ถ้ามีคำตอบอยู่จริง มันต้องตรวจจับได้ ซึ่งในตัวอย่างนี้ที่ i=5 ก็มีคำตอบให้เลือกถึงสองชุด คือ (1, 5, 6) และ (0, 4, 6)

แบบที่ 2 · กวาดสองรอบ ซ้ายทีขวาที แล้วเอามารวมกัน

ใช้ตอนที่คำตอบของแต่ละตำแหน่งต้องรู้ข้อมูลของ ทุกตัวยกเว้นตัวเอง ซึ่งฟังดูเหมือนต้องวนซ้อนสองชั้น (สำหรับแต่ละตำแหน่ง ก็วนดูตัวอื่นทั้งหมด) แต่จริง ๆ ไม่ต้อง

ให้นึกภาพว่าเรายืนอยู่ที่ตำแหน่งหนึ่งในแถว สิ่งที่เราต้องรู้มีแค่สองอย่าง คือ สรุปของทุกอย่างทางซ้ายมือ กับ สรุปของทุกอย่างทางขวามือ

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

สองรอบยังถือว่าเร็ว เพราะ 2 คูณ n ยังโตเป็นเส้นตรงตาม n เหมือนเดิม ต่างจากการวนซ้อนที่กลายเป็น n คูณ n

prefix = [ค่าตั้งต้น] * n
for i in range(1, n):
    prefix[i] = รวม(prefix[i-1], data[i-1])    # ทุกอย่างทางซ้ายของ i

suffix = [ค่าตั้งต้น] * n
for i in range(n-2, -1, -1):
    suffix[i] = รวม(suffix[i+1], data[i+1])    # ทุกอย่างทางขวาของ i

answer = [รวม(prefix[i], suffix[i]) for i in range(n)]

nums = [1, 2, 3, 4]
n = len(nums)

prefix = [1] * n     # prefix[i] = ผลคูณของทุกตัวก่อน i (ไม่รวม i)
for i in range(1, n):
    prefix[i] = prefix[i - 1] * nums[i - 1]
print("prefix (คูณจากซ้าย):", prefix)

suffix = [1] * n     # suffix[i] = ผลคูณของทุกตัวหลัง i (ไม่รวม i)
for i in range(n - 2, -1, -1):
    suffix[i] = suffix[i + 1] * nums[i + 1]
print("suffix (คูณจากขวา) :", suffix)

answer = [prefix[i] * suffix[i] for i in range(n)]
print("answer = prefix*suffix:", answer)

prefix (คูณจากซ้าย): [1, 1, 2, 6]
suffix (คูณจากขวา) : [24, 12, 4, 1]
answer = prefix*suffix: [24, 12, 8, 6]

ลองอ่านตัวเลขในผลลัพธ์ให้เห็นความหมาย ที่ตำแหน่ง 2 ค่า prefix เป็น 2 (มาจาก 1 คูณ 2 คือทุกตัวทางซ้าย) และค่า suffix เป็น 4 (คือเลข 4 ตัวเดียวที่อยู่ทางขวา) คูณกันได้ 8 ซึ่งคือผลคูณของทุกตัวยกเว้นเลข 3 พอดี

หลายคนพอเจอโจทย์นี้จะคิดวิธีที่สั้นกว่า คือคูณทุกตัวให้ได้ผลรวมก่อน แล้วเอาไปหารด้วย nums[i] ทีละตำแหน่ง

วิธีนั้นใช้ไม่ได้สองเหตุผล หนึ่งคือโจทย์ห้ามใช้การหารตรง ๆ สองคือถ้าในลิสต์มีเลข 0 อยู่ ผลคูณรวมจะเป็น 0 แล้วเอาไปหารต่อไม่ได้เลย ซึ่งเป็นเคสที่โจทย์เตรียมไว้ดักอยู่แล้ว

การกวาดสองรอบไม่มีปัญหานี้ เพราะมันไม่เคยหารอะไร และจัดการเลข 0 ได้เองโดยไม่ต้องเขียนเงื่อนไขพิเศษ

แบบนี้เจอในข้อ 7 · Product of Array Except Self และเป็น 'ท่ากวาดสะสมสองทิศ' ตัวแรกที่เจอในคอร์สนี้ จะเจอญาติของมันอีกครั้งในหมวด Prefix Sum ถัดไป ซึ่งใช้ผลรวมแทนผลคูณ แต่แนวคิดเหมือนกันทุกประการ

แบบที่ 3 · แก้ของในแถวเดิม ด้วยตัวชี้สองตัวเดินตามกัน

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

ทางออกคือใช้ตัวชี้สองตัวเดินไปด้วยกันบนแถวเดียว ให้นึกภาพคนคัดของที่ใช้สองมือ มือขวาหยิบของขึ้นมาดูทีละชิ้นเดินไปข้างหน้าเรื่อย ๆ เรียกว่า read ส่วนมือซ้ายคอยวางของที่คัดแล้วลงกล่องจากช่องแรก เรียกว่า write

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

write = 0
read = 0
while read < len(data):
    ประมวลผลกลุ่มที่เริ่มจาก data[read]   # อ่านเดินหน้าตามจังหวะของตัวเอง
    data[write] = ผลลัพธ์ที่ย่อแล้ว
    write += 1
# data[:write] คือผลลัพธ์

chars = ["a", "a", "b", "b", "c", "c", "c"]
write = 0
read = 0
n = len(chars)
while read < n:
    ch = chars[read]
    count = 0
    while read < n and chars[read] == ch:
        read += 1
        count += 1
    chars[write] = ch
    write += 1
    if count > 1:
        for digit in str(count):
            chars[write] = digit
            write += 1
    print(f"  หลังกลุ่ม '{ch}'x{count}: chars={chars[:write]} (write={write}, read={read})")

print("ความยาวใหม่:", write, "| chars[:write] =", chars[:write])

  หลังกลุ่ม 'a'x2: chars=['a', '2'] (write=2, read=2)
  หลังกลุ่ม 'b'x2: chars=['a', '2', 'b', '2'] (write=4, read=4)
  หลังกลุ่ม 'c'x3: chars=['a', '2', 'b', '2', 'c', '3'] (write=6, read=7)
ความยาวใหม่: 6 | chars[:write] = ['a', '2', 'b', '2', 'c', '3']

ดูตัวเลข write กับ read ในผลลัพธ์แต่ละบรรทัด จะเห็นว่า write ตามหลังหรือเท่ากับ read ทุกครั้ง ไม่มีบรรทัดไหนที่ write แซงไปข้างหน้าเลย

และนี่ไม่ใช่ความโชคดีของข้อมูลชุดนี้ แต่รับประกันได้ทุกกรณี เหตุผลมีสองข้อ

ข้อแรก เราเขียนผลลัพธ์ของกลุ่มลงไป หลัง จากที่ read เดินผ่านกลุ่มนั้นจนหมดแล้ว ไม่ได้เขียนล่วงหน้า

ข้อสอง ผลลัพธ์ที่เขียนลงไปไม่เคยยาวกว่ากลุ่มต้นฉบับ ลองไล่ดู: กลุ่มยาว 1 ตัวเขียนแค่ตัวอักษร ใช้ 1 ช่องเท่าเดิม · กลุ่มยาว 2 ตัวเขียน a2 ใช้ 2 ช่องเท่าเดิม · กลุ่มยาว 3 ขึ้นไปเขียนสั้นลงกว่าเดิม

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

แบบที่ 4 · เดินสองแถวไปพร้อมกัน

แบบที่ 3 มีตัวชี้สองตัวบนแถวเดียว แบบนี้ต่างออกไป คือมีสองแถวแยกกันคนละก้อน และมีตัวชี้ประจำแถวละตัว

ให้นึกภาพคนสองแถวยืนรอเข้าประตูเดียวกัน ประตูปล่อยทีละคนสลับแถวไปเรื่อย ๆ ซ้าย ขวา ซ้าย ขวา ตัวชี้แต่ละตัวก็คือคนหัวแถวของแต่ละฝั่ง

จุดที่เป็นกับดักของแบบนี้อยู่ที่ตอนจบ เพราะสองแถวมักยาวไม่เท่ากัน พอแถวสั้นหมดคนแล้ว การสลับก็ทำต่อไม่ได้ ต้องปล่อยคนที่เหลือของอีกแถวออกไปรวดเดียว

ในโค้ดจึงต้องมีสองส่วนเสมอ คือลูปที่ทำงานตอนทั้งสองฝั่งยังมีของ และการเก็บเศษที่เหลือหลังลูปจบ ถ้าลืมส่วนที่สอง คำตอบจะขาดท้ายไปเงียบ ๆ โดยไม่มี error

i = j = 0
result = []
while i < len(a) and j < len(b):     # ต้องเช็คขอบเขตทั้งสองฝั่งก่อนอ่านเสมอ
    result.append(a[i]); i += 1
    result.append(b[j]); j += 1
tail = a[i:] + b[j:]                 # ฝั่งที่เหลือ ต่อท้ายรวดเดียว ไม่ต้องสลับอีก

def merge_alternately(word1, word2):
    i = j = 0
    result = []
    while i < len(word1) and j < len(word2):
        result.append(word1[i]); i += 1
        result.append(word2[j]); j += 1
        print(f"  หยิบ {word1[i-1]!r} กับ {word2[j-1]!r} -> result={''.join(result)} (i={i}, j={j})")
    tail = word1[i:] + word2[j:]
    print(f"  ฝั่งหนึ่งหมดแล้ว เหลือ {tail!r} ต่อท้ายรวดเดียว")
    return "".join(result) + tail

print("merge_alternately('abcd', 'pq') =", merge_alternately("abcd", "pq"))

  หยิบ 'a' กับ 'p' -> result=ap (i=1, j=1)
  หยิบ 'b' กับ 'q' -> result=apbq (i=2, j=2)
  ฝั่งหนึ่งหมดแล้ว เหลือ 'cd' ต่อท้ายรวดเดียว
merge_alternately('abcd', 'pq') = apbqcd

แบบนี้เจอในข้อ 1 · Merge Strings Alternately กับดักเดียวคือลืมจัดการ 'ส่วนที่เหลือ' หลัง while จบ เพราะเงื่อนไข while ใช้ and ทำให้ลูปหยุดทันทีที่ฝั่งใดฝั่งหนึ่งหมด แม้อีกฝั่งจะเหลืออยู่เต็มก็ตาม จะเจอท่านี้เวอร์ชันเข้มข้นกว่านี้ในหมวด Two Pointers (แบบที่ 3 · same direction บนข้อมูลสองชุด)

แบบที่ 5 · มองหาข้อสังเกตที่ทำให้ไม่ต้องไล่ลองทีละแบบ

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

โจทย์ที่ยกมาเป็นตัวอย่างคือข้อ 2 ซึ่งถามหาบล็อกตัวอักษรที่ยาวที่สุด ที่เอามาต่อกันซ้ำ ๆ แล้วได้ทั้ง str1 และ str2 พอดี

วิธีตรงไปตรงมาคือไล่ลองบล็อกทุกความยาวที่เป็นไปได้ แต่มีข้อสังเกตสองข้อที่ตัดงานนั้นออกได้ทั้งหมด

ข้อสังเกตแรก ถ้าสองสตริงสร้างจากบล็อกเดียวกันจริง เอามาต่อกันสลับข้างจะได้ผลเหมือนกัน คือ str1 + str2 ต้องเท่ากับ str2 + str1 เหตุผลง่าย ๆ คือทั้งสองฝั่งก็แค่บล็อกเดิมมาเรียงต่อกัน จำนวนบล็อกรวมเท่ากัน ลำดับจึงเหมือนกันไม่ว่าจะต่อข้างไหนก่อน

และในทางกลับกันก็เป็นจริงด้วย คือถ้า str1 + str2 เท่ากับ str2 + str1 แล้วรับประกันได้ว่ามีบล็อกร่วมอยู่จริง ข้อนี้เป็นทฤษฎีบทที่พิสูจน์แล้วในทฤษฎีสตริง หน้านี้ขอไม่พิสูจน์ แต่จะเห็นว่ามันตรงกับทุกเคสในตัวอย่างข้างล่าง

ข้อสังเกตที่สอง ความยาวของบล็อกต้องหารความยาวของทั้งสองสตริงลงตัว ดังนั้นบล็อกที่ยาวที่สุดจึงยาวเท่ากับ ห.ร.ม. ของสองความยาวนั้นพอดี ซึ่ง Python มี math.gcd ให้ใช้อยู่แล้ว

สองข้อสังเกตนี้รวมกันทำให้คำตอบเหลือแค่: เช็คว่าต่อสลับข้างได้เท่ากันไหม ถ้าไม่เท่าก็ตอบสตริงว่าง ถ้าเท่าก็ตัดหัวสตริงมาตามความยาว ห.ร.ม.

import math

def gcd_string(str1, str2):
    if str1 + str2 != str2 + str1:
        return ""
    g = math.gcd(len(str1), len(str2))
    return str1[:g]

tests = [("ABCABC", "ABC"), ("ABABAB", "ABAB"), ("LEET", "CODE"), ("ABABABAB", "ABAB")]
for a, b in tests:
    print(f"str1={a!r} str2={b!r} -> a+b==b+a: {a+b == b+a} -> คำตอบ = {gcd_string(a,b)!r}")

str1='ABCABC' str2='ABC' -> a+b==b+a: True -> คำตอบ = 'ABC'
str1='ABABAB' str2='ABAB' -> a+b==b+a: True -> คำตอบ = 'AB'
str1='LEET' str2='CODE' -> a+b==b+a: False -> คำตอบ = ''
str1='ABABABAB' str2='ABAB' -> a+b==b+a: True -> คำตอบ = 'ABAB'

โค้ดทั้งข้อเหลือ 4 บรรทัด ทั้งที่โจทย์อ่านแล้วดูยาก เพราะงานหนักถูกย้ายจากการไล่ลอง ไปเป็นการสังเกตกฎ

บทเรียนที่เอาไปใช้ต่อได้คือ: ถ้าเจอโจทย์ที่ทางแรกที่คิดออกคือ ไล่ลองทุกแบบ ให้หยุดถามก่อนหนึ่งรอบว่ามันมีความสมมาตร มีคาบซ้ำ หรือมีการหารลงตัวซ่อนอยู่ไหม ถ้ามี โจทย์มักสั้นลงมาก

แบบนี้เจอในข้อ 2 · Greatest Common Divisor of Strings และต่างจาก 4 แบบก่อนหน้าตรงที่มันไม่ใช่สูตรตายตัวที่ทำซ้ำได้ แต่เป็นทักษะ 'มองหาคุณสมบัติทางคณิตศาสตร์' ที่จะได้ใช้ซ้ำในโจทย์ยาก ๆ ตลอดเส้นทางสายนี้

แบบที่ 6 · ใช้เครื่องมือของ string ให้เต็มที่

แบบสุดท้ายไม่ใช่อัลกอริทึม แต่เป็นการรู้ว่า Python เตรียมอะไรมาให้แล้ว เพื่อไม่ให้เราไปนั่งเขียนลูปนับช่องว่างเองทั้งที่มีคำสั่งสำเร็จอยู่

อย่างแรกคือการตัดประโยคเป็นคำ ถ้าใช้ s.split() เฉย ๆ โดยไม่ใส่อะไรในวงเล็บ มันจะยุบช่องว่างที่ติดกันหลายช่องให้เหลือรอยต่อเดียว และตัดช่องว่างหัวท้ายทิ้งให้เองด้วย ซึ่งพอดีกับที่ข้อ 6 ต้องการเป๊ะ

อย่างที่สองคือการเช็คว่าตัวอักษรตัวหนึ่งอยู่ในกลุ่มที่เราสนใจไหม เช่นเป็นสระหรือเปล่า วิธีที่สะอาดที่สุดคือเตรียมกลุ่มไว้เป็น set แล้วถามด้วยคำว่า in ซึ่งเร็วมากและอ่านง่าย

และให้ใส่ทั้งตัวพิมพ์เล็กและพิมพ์ใหญ่ลงไปในกลุ่มด้วย เพราะโจทย์ข้อ 5 นับ A E I O U เป็นสระเหมือนกัน ซึ่งเป็นจุดที่คนตกข้อนั้นกันมากที่สุด

s = "  a good   example  "
words = s.split()
print("s.split()       :", words)
print("กลับลำดับ + join:", " ".join(reversed(words)))

s.split()       : ['a', 'good', 'example']
กลับลำดับ + join: example good a

VOWELS = set("aeiouAEIOU")

def reverse_vowels(s):
    chars = list(s)
    i, j = 0, len(chars) - 1
    while i < j:
        if chars[i] not in VOWELS:
            i += 1
        elif chars[j] not in VOWELS:
            j -= 1
        else:
            chars[i], chars[j] = chars[j], chars[i]
            i += 1; j -= 1
    return "".join(chars)

print("reverse_vowels('IceCreAm') =", reverse_vowels("IceCreAm"))
print("reverse_vowels('leetcode') =", reverse_vowels("leetcode"))

reverse_vowels('IceCreAm') = AceCreIm
reverse_vowels('leetcode') = leotcede

สองท่านี้ครอบคลุมข้อ 6 (ใช้ split แล้วกลับลำดับคำ) และข้อ 5 (ใช้ set ของสระ)

และถ้าดูโค้ดข้อ 5 ข้างบนให้ดี จะเห็นว่ามันมีตัวชี้ i กับ j วิ่งเข้าหากันจากหัวและท้ายด้วย นั่นคือตัวอย่างจริงของการที่โจทย์หนึ่งข้อผสมสองวิธีเข้าด้วยกัน ตามที่เตือนไว้ตอนต้นส่วนนี้

ตารางสรุป · 6 แบบ กับ 9 ข้อ

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

ส่วนที่ 7 · สัญญาณว่าควรเลิกใช้ list แล้วเปลี่ยนเครื่องมือ

list กับ string ใช้ได้กว้างมาก แต่มีสี่สถานการณ์ที่ถ้าฝืนใช้ต่อจะช้าโดยไม่จำเป็น ส่วนนี้ไม่ได้ให้ไปเรียนเครื่องมือใหม่ตอนนี้ แค่ให้จำสัญญาณไว้ เพื่อว่าพอเจอของจริงจะรู้ว่าต้องไปหาอะไร

def pop_front_list_shifts(n):
    lst = list(range(n))
    shifts = 0
    while lst:
        shifts += len(lst) - 1     # pop(0) ต้องขยับทุกตัวที่เหลือ (ยกเว้นตัวที่ถูกดึงออก) มาข้างหน้า 1 ช่อง
        lst.pop(0)
    return shifts

for n in [100, 1000, 10000]:
    print(f"n={n:<6} list.pop(0) รวมการขยับ: {pop_front_list_shifts(n):<10} | deque.popleft(): 0 ครั้ง (ไม่ต้องขยับอะไรเลย)")

n=100    list.pop(0) รวมการขยับ: 4950       | deque.popleft(): 0 ครั้ง (ไม่ต้องขยับอะไรเลย)
n=1000   list.pop(0) รวมการขยับ: 499500     | deque.popleft(): 0 ครั้ง (ไม่ต้องขยับอะไรเลย)
n=10000  list.pop(0) รวมการขยับ: 49995000   | deque.popleft(): 0 ครั้ง (ไม่ต้องขยับอะไรเลย)

ส่วนที่ 8 · กับดักที่ทำให้เสียเวลาหาบั๊กนานที่สุด

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

ไม่ต้องจำทั้งหมดตอนนี้ แต่ถ้าวันหนึ่งเจออาการว่า โค้ดดูถูกแล้วแต่คำตอบเพี้ยน ให้กลับมาไล่ดูรายการนี้ทีละข้อ

• ตั้งค่าเริ่มต้นของ parameter เป็นลิสต์ว่าง เช่น def f(x, bucket=[]) ลิสต์นั้นถูกสร้างครั้งเดียวตอนประกาศฟังก์ชัน แล้วถูกใช้ร่วมกันทุกครั้งที่เรียก ทำให้ค่าจากการเรียกครั้งก่อนค้างอยู่ ทางแก้คือใช้ bucket=None แล้วสร้างลิสต์ใหม่ข้างในฟังก์ชัน
• สร้างตาราง 2 มิติด้วย [[0]*m]*n จะได้แถวเดียวกันซ้ำ n ที่ ไม่ใช่ n แถวจริง แก้ช่องหนึ่งแล้วทุกแถวเปลี่ยนตาม (เป็นเรื่อง aliasing จากส่วนที่ 1 ตรง ๆ) ทางแก้คือ [[0]*m for _ in range(n)]
• คิดว่า nums[:] คัดลอกได้ทุกชั้น จริง ๆ มันคัดลอกแค่ชั้นบนสุด ถ้าเป็นลิสต์ซ้อนลิสต์ การแก้ลิสต์ชั้นในยังกระทบต้นฉบับ ถ้าต้องแยกขาดจริงต้องใช้ copy.deepcopy
• ลบสมาชิกออกจากลิสต์ระหว่างที่กำลังวน for อยู่บนลิสต์นั้น ตำแหน่งจะเลื่อนกลางทางทำให้บางตัวถูกข้าม ทางแก้คือวนบนสำเนา for x in nums[:] หรือสร้างลิสต์ใหม่แทนการลบ
• ลืมว่า string แก้ผ่านตำแหน่งไม่ได้ ถ้าต้องแก้ทีละตัวอักษรหลายครั้ง ให้แปลงเป็น list(s) ทำงานให้เสร็จ แล้วค่อย "".join(...) กลับตอนท้าย
• เดินสองแถวพร้อมกันแล้วลืมเก็บส่วนที่เหลือหลังลูปจบ คำตอบจะขาดท้ายไปโดยไม่มีอะไรเตือน (กับดักของแบบที่ 4)
• ใช้ s.split(" ") ทั้งที่ต้องการยุบช่องว่างซ้ำ จะได้สตริงว่างแทรกอยู่ในผลลัพธ์ ถ้าไม่สนว่าคั่นด้วยช่องว่างกี่ตัว ให้ใช้ s.split() เฉย ๆ

ทบทวนก่อนไปทำโจทย์

ถ้าตอบสี่ข้อนี้ได้ด้วยคำพูดของตัวเอง แปลว่าพร้อมแล้ว ถ้าข้อไหนตอบไม่ได้ ให้กลับไปอ่านส่วนที่วงเล็บไว้

1. ทำไม b = a แล้วแก้ b ถึงทำให้ a เปลี่ยนไปด้วย แต่กับ string ไม่เป็นแบบนั้น (ส่วนที่ 1)
2. ทำไม nums.append(x) ถูก แต่ nums.insert(0, x) แพง (ส่วนที่ 3)
3. ทำไมประกอบ string ในลูปควรใช้ list แล้ว join ปิดท้าย (ส่วนที่ 4)
4. โจทย์ที่ให้หาคำตอบของทุกตำแหน่งโดยใช้ข้อมูลทุกตัวยกเว้นตัวเอง ควรเริ่มจากวิธีไหน (แบบที่ 2)