“การเปลี่ยนมุมมอง” กับอัลกอริทึม Sieve of Eratosthenes

หลาย ๆ ครั้งเราน่าจะเคยได้ยินหลายเรื่องราวเกี่ยวกับการแก้ปัญหาและการเปลี่ยนมุมมอง ที่การปรับมุมมองใหม่ ๆ การที่มองปัญหาในอีกด้าน อาจนำไปสู่วิธีแก้ปัญหาที่ดีกว่าเดิม ยกตัวอย่างเช่น quote ของ Henry Ford ที่หลายคนคุ้นเคย

“If I had asked people what they wanted, they would have said faster horses.” — Henry Ford

การพยายาม optimize solution เดิมให้ดีขึ้น (faster horses) ไม่ได้หมายความว่ามันจะนำมาสู่ solution ที่ดีที่สุด (car) เสมอไป ซึ่งเรามักจะได้เห็นเรื่องราวการแก้ปัญหาแบบพลิกมุมมองแบบนี้เกิดขึ้นอยู่บ่อย ๆ โดยเฉพาะในวงการของการทำธุรกิจ

Peter Thiel หนึ่งใน PayPal Mafia เคยบอกว่าธุรกิจที่แก้ปัญหาบนมุมมองใหม่อย่างสิ้นเชิงแบบนี้ คือธุรกิจที่เรียกว่า “Zero To One” (ซึ่งหลายครั้งนำมาสู่ technology ที่หน้าตาแทบไม่เหมือน solution เดิมเลย) ในขณะที่ธุรกิจที่พยายามทำของเดิมให้ดีขึ้นหรือเอาอะไรที่มัน work อยู่แล้วมาทำต่อ คือธุรกิจที่เรียกว่า “One To N”

แน่นอนว่าการเปลี่ยนมุมมองของปัญหาแบบนี้ มันไม่ได้ใช้ได้กับแค่การทำธุรกิจ แต่มันคือ problem solving in general เลย ทั้งในวงการ math, computer science หรือ field อื่น ๆ ไม่ว่าอะไรก็ตาม ส่วนตัวเลยรู้สึกว่าเรื่องนี้เป็นเรื่องสำคัญที่เราควรหยิบมาพูดคุยกัน

แต่ว่าคำถามคือ การจะเปลี่ยนมุมมองมันต้องทำยังไง? กระบวนการของมันคืออะไร? แล้วการเปลี่ยนมุมมองจริง ๆ แล้วมันคืออะไรกันแน่ บทความนี้เลยอยากมาชวนหาคำตอบกัน

จำนวนเฉพาะตั้งแต่ 1 ถึง n

เพื่อให้เห็นภาพมากขึ้น ในบทความนี้เราจะลองยกตัวอย่างปัญหาง่าย ๆ มาแก้กันครับ

“กำหนดให้ n เป็นจำนวนเต็มบวกที่มีค่ามากกว่า 1 ขึ้นไป จงหาจำนวนเฉพาะ (prime number) ทั้งหมดตั้งแต่ 2 ถึง n”

ถึงตรงนี้เราอยากให้ทุกคนลองใช้เวลา 2 - 3 นาทีคิด solution ในการแก้ปัญหาดู แน่นอนว่าไม่จำเป็นต้องเป็น algorithm ที่มีประสิทธิภาพสูงที่สุดก็ได้ อาจจะลองคิดเล่น ๆ ว่าถ้าเราจะหา prime number ทั้งหมดตั้งแต่ 1 ถึงสักตัวเลข (เช่น 50) เราจะใช้วิธีไหนหาคำตอบออกมา

Naive Solution

ถ้าเราคิดอะไรไม่ออกวิธีการนึงที่เราสามารถทำได้ก็คือ การเริ่มคิดจากวิธีการที่ง่าย ตรงไปตรงมา และ obvious ที่สุดก่อน เรามักจะเรียก solution แบบนี้ว่า “Naive solution”

เช่นเราอาจจะเริ่มจากการไล่เช็คไปทีละเลขตั้งแต่ 2 ถึง \(n\) ว่าเลขนั้นเป็น prime number หรือไม่; เพื่อความง่าย เราจะตั้งชื่อให้เลขที่เราไล่เช็คว่า \(x\) โดยที่ \(2 \le x \le n\)

ถ้า \(x\) เป็น prime number ก็จดเก็บเอาไว้เป็นคำตอบ และเมื่อเราเช็ค \(x\) ครบทุกตัวแล้ว prime number ทั้งหมดก็คือที่เราจดเอาไว้

“For each x in the range 2 to n, check if x is prime.”

ส่วนวิธีการเช็คว่า \(x\) เป็น prime หรือไม่นั้น เราก็อาจจะมาไล่ดูว่าตั้งแต่เลข 1 จนถึง \(x\) มีเลขไหนที่หาร \(x\) ลงตัวไหม (ที่ไม่ใช่ 1 และ \(x\)) ถ้ามีเราก็สรุปได้เลยว่า \(x\) ไม่ใช่ prime number

16 มีตัวที่หารลงตัวคือ 1, 2, 4, 8, 16; ดังนั้น 16 ไม่ใช่ prime number

7 มีตัวที่หารลงตัวคือ 1, 7; สรุปได้ว่า 7 คือ prime number

ถ้าเราลองทำ analysis เพื่อเช็ค cost (หรือจำนวน operation) ในการรัน algorithm นี้คร่าว ๆ เราจะพบว่า การเช็คว่า \(x\) เป็น prime number หรือไม่นั้น ในกรณีที่แย่ที่สุดคือ \(x\) เป็น prime number เราต้องลองไล่หารจำนวนทั้งหมดตั้งแต่ 1 ถึง \(x\) ดังนั้นเราสรุปคร่าว ๆ ได้ว่า

และในเมื่อเราต้องเช็ค prime number ทั้งหมดตั้งแต่ 2 ถึง \(n\) (ประมาณ​ \(n\) ครั้ง); ดังนั้น Cost ทั้งหมดโดยประมาณก็คือ

ทั้งนี้เราไม่จำเป็นต้องคำนวณ operation cost ออกมาเป็ะ ๆ ก็ได้ เพราะจุดประสงค์ของการทำ analysis คือเราต้องการดูว่า algorithm ที่คิดมามันตอบโจทย์กับปัญหาไหม รวมถึงการนำไปเปรียบเทียบกับ algorithm อื่น ๆ ด้วย

ดังนั้นสิ่งที่สำคัญกว่าจำนวน cost เป็ะ ๆ คือการเติบโตของ cost “โดยประมาณ” โดยเฉพาะเมื่อ input (หรือในที่นี้คือค่า \(n\)) มีค่ามาก ๆ

ซึ่งเราสามารถใช้ mathematical notation ตัวหนึ่งที่ชื่อว่า “Big O Notation” ในการ express สิ่งที่ว่ามานี้ออกมาได้ ว่าในการรัน algorithm นี้มี Cost (หรือที่เรียกว่า Time Complexity) เป็น \(O(n^2)\) (เนื่องจากเราสนแค่การเติบโตเมื่อ input มีค่ามาก ๆ ดังนั้นพจน์ที่ไม่ significant เลยตัดออกไปได้)

มีวิธีการที่ดีกว่านี้ไหม ?

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

สำหรับการเช็คว่า \(x\) เป็น prime number หรือไม่นั้น เราอาจจะสังเกตว่าในกรณีที่ \(x\) ไม่ได้เป็น prime number เราเช็คไปแค่ไม่กี่ค่าก็เจอค่าที่หารลงตัวตัวแรกแล้ว เช่น 16 เราเจอ 2 ก็รู้แล้วว่า \(x\) ไม่ใช่ prime หรือ 49 เราเจอ 7 ก็ไม่ต้องไล่หารต่อแล้ว

คำถามคือเพื่อที่จะเจอค่าที่หารลงตัวแรก เราจำเป็นต้องไล่เช็คไปเรื่อย ๆ จนถึง \(x\) ไหม ? หรือถ้าตั้งคำถามในทางกลับกัน

“เราต้องไล่ไปถึงเท่าไหร่ถึงจะเจอตัวที่หารลงตัวตัวแรก และถ้าหากว่าเราไม่เจอค่านั้น เราการันตีได้เลยไหมว่าจะไม่มีค่าที่หาร \(x\) ลงตัวอีกแล้ว (หรือสรุปได้ว่า \(x\) เป็น prime number)”

ถ้าหากว่าเราลองไล่หาตัวที่หาร \(x\) ลงตัวออกมาดูทั้งหมดเราจะพบว่า ถ้าเราหาค่าที่หารลงตัวได้ค่าหนึ่ง เราจะหาอีกคู่ที่หารลงตัวได้ด้วย เช่น

16 มีตัวที่หารลงตัวคือ 1, 2, 4, 8, 16; ถ้าเราลองไล่หารเราจะพบว่าเมื่อเจอ 1 เราจะรู้ว่า 16 ก็หารลงตัวด้วย เมื่อเจอ 2 จะเจอ 8 และเมื่อเจอ 4 อีกคู่นึงก็คือ 4

จากการจับคู่ด้านบนเราจะเห็นว่า pattern ว่า \(x\) จะเกิดจากค่า \(a\) และ \(b\) คูณกันเสมอ

เมื่อเราเขียนออกมาแบบนี้ เราอาจจะสังเกตต่อว่า ถ้าหากว่าเราเพิ่มค่า \(a\); ค่า \(b\) จะลดลง และในทางกลับกัน ถ้าเพิ่ม \(b\); ค่า \(a\) ก็จะลด

ดังนั้นถ้าเราให้ค่า \(a\) เป็นค่าฝั่งน้อย และค่า \(b\) เป็นค่าฝั่งที่มาก ค่า \(a\) ที่มากที่สุดที่เป็นไปได้ก็คือกรณีที่ \(a = b\) (เพราะถ้า a มีค่ามากกว่านี้ค่า a ก็จะกลายเป็นฝั่งมาก และค่า b กลายเป็นฝั่งที่น้อยแทน)

สรุปในกรณีที่ \(a = b\) ก็คือ \(x = a \times b = a \times a = a^2\) ดังนั้นเราเลยสรุปได้ว่า \(a = \sqrt{x}\)

สรุปก็คือเราไล่หารถึง \(\sqrt{x}\) ก็พอแล้ว (ไม่จำเป็นต้องไล่ไปถึง \(x\)) ถ้าหากว่าไม่เจอค่าที่หารลงตัวในช่วงนี้ เราก็สรุปได้ทันทีว่า \(x\) เป็น prime number

Time Complexity ของ algorithm โดยรวมคือ \(O(n \sqrt{n})\)

Sieve of Eratosthenes

อีก algorithm ที่เราอยากเอามานำเสนอคือ Sieve of Eratosthenes เป็น algorithm ที่ถูกคิดมา 2000 กว่าปีแล้วโดยชาวกรีกคนหนึ่งที่ชื่อว่า Eratosthenes

ก่อนอื่นเราอาจจะต้องโยน solution เก่าที่เราเคยมีทิ้งไปก่อน แล้วย้อนกลับมามอง มาตั้งคำถามที่ปัญหาของเราอีกครั้ง

“กำหนดให้ n เป็นจำนวนเต็มบวกที่มีค่ามากกว่า 1 ขึ้นไป จงหาจำนวนเฉพาะ (prime number) ทั้งหมดตั้งแต่ 2 ถึง n”

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

ทั้งหมดนี้ก็เพื่อทำให้ปัญหามันชัดมากขึ้น เพื่อที่เราจะสังเกตและ reasoning ต่อไปได้ง่ายขึ้น

“A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers.”

เราอาจจะสังเกตว่า prime number มันคือจำนวนที่เป็นรากฐานของจำนวนอื่น ๆ (prime มาจากคำว่า primus ที่แปลว่า “first”) เราสามารถใช้ prime number (กำหนดให้เป็น \(p\)) สร้างจำนวนอื่น ๆ ที่ไม่ใช่ prime number ได้เช่น \(2p, 3p, 4p, …\)

จาก observation นี้เราสามารถคิดต่อได้ว่า จะเกิดอะไรขึ้นถ้าหากว่าเราตัดค่าที่ไม่ใช่ prime number ออกให้หมดจนถึง n โดยการนำ \(p\) มาคูณเลขไปเรื่อย ๆ

เราอาจจะลองสร้าง algorithm ขึ้นมา โดยการที่เราจะเริ่มจาก prime number ตัวแรก (ก็คือ 2) จากนั้นตัดค่า \(2p, 3p, 4p, …\) ออกให้หมดจนถึง \(n\) จากนั้นตัวถัดไปที่ยังไม่ถูกตัดก็คือ prime number ตัวถัดไป จากนั้นก็ตัดค่าที่ไม่ใช่ออกเหมือนเดิม ทำแบบนี้ไปเรื่อย ๆ จนกระทั้งไม่เหลือ prime number ที่น้อยกว่า \(n\) แล้ว

Time Complexity: \(O(n\log\log{n})\)

การเปลี่ยนมุมมองคืออะไร ?

เราจะไม่สามารถคิด algorithm แบบ Sieve of Eratosthenes ออกได้เลยถ้าหากว่าเราไม่โยน naive solution ที่เราเคยมีทิ้งไป แล้วกลับมาทำความเข้าใจกับปัญหาอีกครั้ง

“สิ่งที่เราเรียกมันว่า naive solution มันก็คือความคุ้นเคย สิ่งที่เราเคยเห็นมันมาก่อน ไอเดียหรือความเชื่อที่เราเคยมีอยู่มาก่อน”

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

เราเลยรู้สึกไม่ได้แปลกใจที่ในบางครั้ง คนที่เป็น beginners อาจจะสามารถหา solution ที่ดี หรือมองเห็นมุมมองใหม่ ๆ ได้มากกว่าคนที่มีประสบการณ์เยอะกว่า (ซึ่งนี่ก็เป็นอีกเหตุผลด้วยที่ทำไมการที่เราทำงานกับคนที่มี background หรือประสบการณ์ที่หลากหลาย อาจจะทำให้เราเห็นความเป็นไปได้ที่มากกว่า)

“In the beginner’s mind there are many possibilities, but in the expert’s there are few” - Shunryu Suzuki, Zen Mind, Beginner’s Mind

สำหรับเราแล้วการเปลี่ยนมุมมองมันคือ “การโยนสิ่งที่เราเคยมีทิ้งไป แล้วกลับมาทำความเข้าใจในปัญหา หรือแก่นของสิ่ง ๆ นั้นอีกครั้ง”

การตั้งคำถามจะทำให้เราเข้าใจปัญหาชัดขึ้นและกว้างขึ้น; การสังเกตจะทำให้เราเห็น pattern (หรือ insights) ที่ทำให้เราสามารถคิดวิธีแก้ปัญหาที่ดีขึ้น; และการให้เหตุผลจะทำให้เรามองเห็นปัญหาและ insight ที่ลึกมากขึ้น ที่หลายครั้งเราอาจจะมองไม่เห็นเลยถ้าเราดูแบบผิวเผิน

เรารู้สึกว่า 3 อย่างนี้เป็นเครื่องมือที่สำคัญมาก ๆ ที่จะนำพาเราไปสู่มุมมองใหม่ ๆ