Wall of Text #5: Internet Scale List Comprehension

ในทีมผมมีคนแนะนำ Codewars มา ผมก็เลยเอาไปปล่อยต่อให้น้องเค้าเล่น ซึ่งมันสนุกมาก

เวลาทำโจทย์ใน Codewars ผ่าน มันจะให้ดูว่าคนอื่นแก้โจทย์นี้อย่างไร ซึ่งถ้าเป็น Python เรามักจะเห็นเฉลยระดับบรรทัดเดียวออก เช่น

def find_it(seq):
    return [i for i in seq if seq.count(i) % 2 != 0]

โค้ดนี้เรียกว่า List Comprehension ซึ่งสำหรับมือใหม่อาจจะดูซับซ้อน ผมเองก็เขียน Python มาประมาณ 3-4 ปีก่อนที่จะเริ่มใช้เป็น

List Comprehension ประกอบด้วยคอนเซปต์จาก Functional Programming 2 ตัว คือ Map และ Filter

Map

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

ยกตัวอย่างเช่น ถ้ากำหนดฟังค์ชั่นคือ ยกกำลังสอง แล้ว Map function นี้ลงบน [1, 2, 3, 4] ผลลัพท์ที่ได้คือ [1, 4, 9, 16]

Filter

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

ยกตัวอย่างเช่น ถ้ากำหนดฟังค์ชั่นคือ ทดสอบว่าเป็นเลขคู่ แล้ว Map ลงบน [1, 2, 3, 4, 5] ผลลัพท์ที่เหลืออยู่คือ [2, 4]

ในหลายๆ ภาษา กระบวนการ Map กับ Filter นี้จะแยกกันเป็นสองคำสั่ง เช่นในภาษา JavaScript [1,2,3].map((x) => x*2).filter((x) => x<5) แต่ใน Python เราสามารถรวบเป็น List Comprehension ครั้งเดียวได้เพื่อความสะดวก

Reduce

โดยปกติแล้วฟังค์ชั่นตระกูลนี้นอกจาก Map – Filter แล้วยังมักจะมี Reduce ด้วย (ซึ่ง List Comprehension ทำไม่ได้)

Reduce คือการนำสมาชิก 2 ตัวเข้ามารวมกันเหลือค่าเดียว เช่น ถ้าหากต้องการหาผลรวมของ [1, 2, 5] เราสามารถใช้ reduce function คือ x+y แล้วระบบจะรันฟังค์ชั่นนี้จนครบทุกสมาชิกให้เอง คือ

x=1, y = 2; 1+2 = 3
x=3, y = 5; 3+5 = 8
คำตอบสุดท้ายคือ 8

คำสั่ง Reduce ใน Python 2 คือ reduce() และ Python 3 ถูกย้ายไปไว้ใน functools.reduce() ด้วยเหตุผลว่าเราสามารถใช้ For loop แทนกันได้และอ่านเข้าใจง่ายกว่า

MapReduce

กระบวนการ Map – Reduce – Filter นี้ทรงพลังมาก ขนาด Google ที่มีข้อมูลมหาศาลก็ยังใช้กระบวนการนี้ประมวลผลข้อมูลบางอย่างอยู่

สาเหตุที่มันทรงพลังมาก ก็เพราะมันทำให้ปัญหานี้สามารถกระจายงานไปหลายๆ เครื่องพร้อมกันได้

ยกตัวอย่างเช่น ถ้าหากเราต้องการทำโปรแกรมนับคะแนนจากภาพบัตรเลือกตั้ง วิธีก็คือ

Map – แปลงภาพบัตรเลือกตั้งเป็นพรรคที่เลือก
Filter – กรองบัตรเสียออก
Reduce – รวมคะแนนเลือกตั้งจาก Map

วิธีนี้จะสังเกตว่าในขั้นตอน Map-Filter ไม่มีใครต้องรอใคร ทำให้เรากระจายงานได้ง่ายมาก

ทั้งนี้ MapReduce ที่ใช้ในงาน BigData จะแตกต่างกับ Map-Filter-Reduce อยู่เล็กน้อยเพราะ Map จะมีหน้าที่ของ Filter ไปด้วย โดยในแต่ละ Input Map อาจจะคืนค่ามากกว่า 1 ก็ได้ หรือไม่คืนค่าเลยก็ได้ (แปลว่า filter ทิ้ง) มันจึงจะหน้าตาประมาณนี้

def map_ballot(ballot_img):
    result = ocr(ballot_img)
    if result is not None:
        emit({result: 1})

จากโค้ดด้านบน เราสามารถเรียก emit หลายๆ ครั้งได้ถ้าหากต้องการ output หลายๆ ค่า หรือถ้า result เป็น None จะไม่มีการเรียก emit ก็คือ input นี้จะถูก filter ทิ้งนั่นเอง