วนลูป แล้วลบ “ของ” ออกจาก list

คุณเคยต้องเขียนโปรแกรมที่วนลูปบน list แล้วลบ “ของ (object)” ออกจาก list นั้นหรือไม่? ลองยกตัวอย่างโปรแกรมง่ายๆ สมมติให้ list A เก็บเลขจำนวนเต็ม แล้วคุณต้องการลบเลขที่หารสามลงตัว ออกจาก list A โค้ดของคุณก็อาจจะเป็น

A = [1, 2, 3, 6, 7, 9, 12]
for x in A:
    if x % 3 == 0:
        A.remove(x)

List<int> A = new List<int>(new int[]{1, 2, 3, 6, 7, 9, 12});
foreach(int x in A)
{
    if(x % 3 == 0)
        A.Remove(x);
}

ในบล็อกนี้ขออนุญาตยกตัวอย่างแค่ 2 ภาษา คือ Python และ C# นะครับ สำหรับฝั่ง C# จะเจอกับ “Unhandled Exception: System.InvalidOperationException: Collection was modified;” (เขาบอกว่า เกิดการกระทำที่ไม่ถูกต้อง เนื่องจาก list ถูกแก้ไขระหว่างวนลูป) ส่วนคนใช้ Python จะไม่เจอปัญหาอะไรเวลารันครับ แต่พอลองพิมพ์ A ออกมาดูจะพบว่า

A = [1, 2, 6, 7, 12]

แงว… ทำไม 6 กับ 12 ยังโผล่ออกมา? ในเมื่อมันน่าจะ mod 3 ลงตัว… ในบล็อกนี้เราจะมาดูวิธีแก้ปัญหาที่มักจะเจอบ่อยๆ ปัญหานี้กันครับ

ปัญหาที่เจอใน Python คือ เลขจำนวนเต็มที่หารสามลงตัว ไม่โดนลบออกไปทุกตัว สาเหตุคือ ในการวนลูปบน list python จะมีตัวชี้ index ของ list สร้างขึ้นมา และในการวนลูปแต่ละรอบ index จะต้องโดนขยับไป 1 เสมอ ดังนั้นเมื่อตัวเลขโดนลบไป ตัวเลขอื่นๆ ที่อยู่ต่อท้ายจะเลื่อนมาแทนที่ตัวที่หายไป แล้วตัวที่เลื่อนมาแทนที่เนี่ยแหละครับ จะโดนข้ามไป (ไม่โดนตรวจสอบ)…. ถ้างง ลองดูตัวอย่างต่อไปนี้ครับ

A = 1 2 3 6 7 9 12

A = 1 2 3 6 7 9 12

A = 1 2 3 6 7 9 12

A = 1 2 6 7 9 12

จะเห็นว่ามีกรณีแบบนี้เกิดขึ้นได้ใน python และคนเขียนโปรแกรมก็ไม่รู้ว่าเกิดปัญหาขึ้นเลย (นอกจากมาดูผลลัพธ์) ดังนั้นใน C# เขาจึงห้ามวนลูปแบบ foreach แล้วแก้ไขข้อมูลใน list (เกิด InvalidOperationException นั่นเอง) ในเมื่อ foreach ใช้ไม่ได้ ขอลักไก่ใช้ for ธรรมดาแทนได้มั้ย? คำตอบคือ ไม่ได้ครับ ถ้าลองเขียนแล้วจะเจอปัญหาเหมือนกับที่เจอใน Python ครับ

แล้วเราจะแก้ปัญหานี้ยังไงดีหละ?

แบ่งได้เป็น 3 วิธีที่เจอบ่อยๆ ครับ

1. สร้าง List อีกอันมาเก็บเฉพาะผลลัพธ์ที่ต้องการ

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

B = []
for x in A:
    if x % 3 <> 0:
        B.append(x)

List B = new List<int>();
foreach(int x in A)
{
    if (x % 3 != 0)
	B.Add(x);
}

อ่าวๆๆแบบนี้ โปรแกรมก็ต้อง copy ตัวเลขทุกตัว ไปใส่ list B แทน ซึ่งมันต้องทำงานช้าแน่ๆ เลย สมมติว่าเราต้องการลบเลขแค่ตัวเดียวใน list A แต่ดันต้อง copy ตัวที่ต้องการเก็บไว้ไปใส่ใน list B ซึ่งเสียเวลาทำงานตั้งนาน (แต่! จะเร็วกว่าวิธีอื่นๆ ถ้ามีตัวเลขที่ต้องโดนลบเยอะๆ ครับ)

งั้นไปดูวิธีที่สองดีกว่า

2. วนลูปในตัวก๊อบปี้ของ List

วิธีนี้คือ สร้างตัวก๊อบปี้ของ List (เอาตัวเลขทุกตัว) มาเลยครับ เอามาใช้วนลูป แล้วเวลาลบข้อมูลก็ลบใน list ของจริง ผลลัพธ์ก็จะเก็บอยู่ใน list A ตามปกติ

for x in A[:]:
    if x % 3 == 0:
        A.remove(x)

foreach(int x in new List<int>(A))
{
    if (x % 3 == 0)
	A.Remove(x);
}

หลายๆ คนคงจะเห็นว่า มันก็คล้ายๆ กับวิธีที่ 1 แหละน๊า… แค่สร้างตัวก๊อบปี้ไว้วนลูป ต้องเสียเวลาสร้างตัวก๊อบปี้เหมือนกันไม่ใช่เรอะ?… ฮึ่ม! งั้นลองไปดูวิธีที่ 3 กันครับ

3. วนลูปถอยหลัง

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

for i in reversed(range(len(A)))
    if x % 3 == 0:
        del A[i]

for(int i = A.Count - 1; i >= 0; i--)
{
    if (A[i] % 3 == 0)
	A.RemoveAt(i);
}

จากตัวอย่างโค้ดจะเห็นว่าเราใช้ del A[i] และ A.RemoveAt(i) เพื่อลบตัวเลข ที่ตำแหน่งใดๆ แทนที่จะใช้ Remove ที่ใช้ลบค่าใดๆ จะเห็นว่าวิธีที่สามนั้นน่าจะทำงานได้เร็วกว่าวิธีที่ 1 และ 2 เพราะไม่ต้องสร้างตัวก๊อบปี้ของ list นั่นเอง

สรุป

จากบล็อกนี้เราได้เรียนรู้วิธีแก้ปัญหาที่เกิดขึ้นจากการวนลูป แล้วลบ “ของ” ออกจาก list โดยแบ่งออกเป็น 3 วิธีที่เจอบ่อยๆ ซึ่งแต่ละวิธีก็มีประสิทธิภาพแตกต่างกันไปขึ้นกับการนำไปใช้ และความแตกต่างของแต่ละภาษา ใครชอบใครถนัดวิธีไหนก็เลือกไปใช้ตามสะดวก

ส่วนตั๊วส่วนตัวจากคนเขียน

ปล. สาเหตุที่มานั่งเขียน blog นี้เพราะผมเขียนโปรแกรมไปแล้วก็เจอ bug… คือ “ของ” ใน list มันโดนลบออกไปไม่หมด (แต่ python ไม่ยอมเตือนเหมือน C# หง่ะ!!) ก็เลยนั่งหา bug จนมาเจอ… เอาเป็นว่า เพื่อนๆ คนอื่นที่อ่านมาเจอบล็อกนี้แล้ว คงไม่พลาดแบบผมละกันครับ

ปล2. เพิ่งรู้ว่าใช้ reversed() แล้วโค้ดสวยกว่าเดิมเยอะเลย ปกติเวลาต้องการวนลูปจากมากไปน้อย (9 ถึง 0) ก็เขียนโค้ดน่าเกลียดๆ แบบนี้

for i in range(9, -1, -1):
    print i

พอเขียนบล็อกนี้แล้วเพิ่งรู้ว่าเขียนเป็น

for i in reversed(range(0, 9)):
    print i

สวยกว่าเยอะเลย

ปล3. ใครอยากให้เขียนบล็อก แล้วยกตัวอย่างภาษาอื่นๆ นอกจาก Python และ C# ช่วยทิ้งคอมเม็นท์ไว้ด้วยครับ