👾Algorithm Big-O

ลองดูดิ๊การบวกเลขมันง่ายจิงป่ะ ? 🤪

จากบทความก่อนหน้าหลายคนน่าจะเริ่มเห็นความสำคัญของ Algorithm กันเพิ่มขึ้นละ ดังนั้นในบทความนี้ ดช.แมวน้ำ จะยกตัวอย่าง การบวกเลข ให้เห็นว่ามันแตกประเด็นไปถึงเรื่องการทำ Security ได้ยังงุยกัน (ขอแบ่งเป็น 2 บทนะ)

แนะนำให้อ่าน บทความนี้เป็นส่วนหนึ่งของบทความ 👶 Data Structure & Algorithm หากเพื่อนๆสนใจอยากรู้ว่าเจ้า Algorithm มันคืออะไร คุ้มค่าเวลาชีวิตที่เราจะอ่านไหม ก็สามารถศึกษาได้จากบทความหลักได้เลยโดยการคลิกที่ชื่อบทความสีฟ้าๆนั่นแหละ

🥱 บวกเลข ป.3

สมมุติว่าแมวน้ำเขียนโค้ดตามด้านล่าง

a = 0.2
b = 0.1
c = a + b

คำถามคือ ตัวแปร c มีค่าเป็นเท่าหร่ายยยยจ๊ะ ?

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

ผลลัพท์ 0.30000000000000004 😳 เฮ้ยมันเกิดบร้าไรขึ้นทำไมมันถึงมีติ่งแปลกๆงอกขึ้นมาดั๊ยยยยย!! ลองไปเขียนดูนะ C#, Java, Javascript, Python บลาๆ 🤪

สาเหตุที่คอมมันได้ผลลัพท์แบบนั้นออกมาก็เพราะว่า Data Structure & Algorithm ของตัวเลขมันเป็นแบบนั้นยังไงล่ะ ซึ่งเราจะเห็นว่า แค่เรื่องพื้นฐานแบบสุดๆ ก็ยังมีเรื่อง Data Structure & Algorithm รวมอยู่ด้วยเสมอ ดังนั้นไม่ว่าเราจะเขียนโค้ดด๋อยอะไรก็ตามของพวกนี้ก็จะตามเราไปทุกที่ ซึ่งถ้าเราไม่เข้าใจมัน การออกแบบ การทำ performance tuning หรืออะไรก็ตามก็จะมีปัญหาโดยที่เราไม่รู้ตัวนั่นเอง

ข้อควรระวัง หลายคนพอเห็นว่ามันได้ตัวเลขเพี้ยนๆ ก็จะเบ้ปากแล้วบอกว่างั้นก็ใช้ decimal ไปเลยเด๊ปัญหาก็จบแล้ว ซึ่งแมวน้ำก็จะบอกว่า ใช่ครับมันแก้เรื่องตัวเลขเพี้ยนได้ แต่มันจำเป็นไหม? หรือมันเป็นแค่การซ่อนปัญหา?

เกร็ดความรู้ (ทศนิยม) สาเหตุที่มันได้คำตอบเป็น 0.30000000000000004 ก็เพราะว่า Data Structure ของตัวเลขที่คอมมันเก็บนั้น มันอยู่ในรูปแบบของ binary (0/1) นั่นเอง และคอมมันทำงานกับตัวเลขที่เป็นทศนิยมไม่เก่ง เพราะมันจะเก็บค่าที่แท้จริงของทศนิยมไม่ได้ ดังนั้นมันจะเก็บเป็นค่าที่ใกล้เคียงที่สุด ดังนั้นเวลามันนำไปแสดงผลในบางทีมันจะมีปัญหาเรื่องการปัดเศษ ซึ่งเราเรียกปัญหาแบบนี้ว่า Round-off error นั่นเองขอรับ

เกร็ดความรู้ (Bitcoin) อย่างที่เกร็ดความรู้แรกบอกไปว่า คอมทำงานกับทศนิยมไม่เก่ง ยิ่งทำงานกับเลขทศนิยมมันจะยิ่งช้า ดังนั้นพวก Bitcoin เลยไม่ทำงานกับทศนิยมตรงๆ แต่จะเก็บเป็นตัวเลขจำนวนเต็มแทน (ตัวอย่างให้เห็นภาพสมมุตเขาจะเก็บ 1 บาท 25 สตางค์ ก็จะเก็บเป็น 12500) แล้วเมื่อไหร่ที่จะเอาไปแสดงผลก็ค่อยปัดตำแหน่งที่เป็นทศนิยมไปแสดงผลนั่นเอง (ตามตัวอย่างคือ 4 digits สุดท้าย 12500 ก็จะเป็น 1.25 บาท)

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

เช่น เราจะทำงานกับ collection แล้วเราจะเลือก Data Structure ตัวไหนล่ะ Array ดีไหม หรือ List ดีหว่า Stack ก็น่าสนใจนะ บลาๆ ซึ่งแน่นอนว่า Data Structure แต่ละตัวมีจุดเด่นที่ต่างกัน ซึ่งเราจะเลือกใช้ตัวไหนให้ดูง่ายๆจาก 2 อย่างคือ

1.รูปแบบของปัญหา - เช่น ถ้าต้องประมวลผลข้อมูลแบบ FIFO (ทำตามลำดับ) หรือมาแบบ LIFO (มาหลังทำก่อน) การเลือก Data Type ผิดก็ทำให้เราเขียนโค้ดยากขึ้นเยอะ แถมยังช้าอีก

2.รูปแบบของข้อมูล - เช่น ถ้าข้อมูลถูกเรียงลำดับมา หรือ ข้อมูลไม่มีลำดับเลย ก็จะมีผลเช่นกัน

😒 แล้วเราจะรู้ได้ยังไงว่าเมื่อไหร่ควระเลือก Algorithm ตัวไหน? หรือใช้ Data Structure อันไหนดีกว่ากัน? . . . ไม่ต้องเสียเวลาคิดให้มากความ ไปรู้จักกับ Algorithm Complexity ในหัวข้อถัดไปกันเบย

🤔 Algorithm ช้า/เร็ว ดูไง ?

🔥 Algorithms Complexity

สำหรับเพื่อนๆที่เข้าใจ Big-O อยู่แล้วก็ให้อ่านข้ามไปอ่านบทความถัดไปได้เลยที่บทความนี้ 👽 Algorithm P & NP ส่วนใครที่อยากทบทวนก็อ่านต่อตรงนี้ละกัน โดยแมวน้ำขออธิบายโดยใช้คำถามง่ายๆด้านล่าง

ถ้าเราจะคูณเลข 2 ตัว เรามีวิธีคิดแบบไหนได้บ้าง ? ตัวอย่าง 12 x 12 เราคิดยังไงให้ได้ผลลัพท์เป็น 144

จากโจทย์ด้านบน เราก็อาจจะคิดง่ายๆได้ 2 วิธีตามด้านล่าง (จะหลายวิธีก็ได้แต่ขอตัดมาแค่นี้พอ)

1.บวกซ้ำ - โดยเราก็จะนำ 12 มาบวกกัน 12 รอบ (12+12+12+....) ซึ่งก็จะได้ผลลัพท์เป็น 144 นั่นเอง 2.คูณทีละตำแหน่ง - โดยเราก็จะนำ 12 x 2 ก่อน แล้วค่อยเอาไปบวกกับ 12 x 10 ซึ่งก็ได้ผลลัพท์เป็น 144 เช่นกัน

จากทั้ง 2 วิธี (Algorithm) ที่ว่ามา ถ้าเราลองทำตามดูเราจะพบว่า จำนวนครั้งที่ทำในแต่ละวิธีมันไม่เท่ากัน

วิธี (Algorithm)	จำนวนครั้งที่ทำ	ตัวอย่าง
บวกซ้ำ	ขึ้นอยู่กับตัวคูณ	15 x 5,000 ต้องทำซ้ำ 5,000 ครั้ง
คูณทีละตำแหน่ง	(หลักของตัวคูณ x 2) -1	15 x 5,000 ต้องทำซ้ำ (4x2)-1 = 7 ครั้ง

จากตารางด้านบนจะเห็นว่า วิธีบวกซ้ำ มันมีจำนวนครั้งที่ใช้เยอะกว่า วิธีคูณทีละตำแหน่ง ยิ่งตัวคูณเยอะเท่าไหร่ จำนวนครั้งที่ทำก็จะยิ่งเยอะตาม โดยในทางคอมพิวเตอร์ยิ่งจำนวณครั้งที่ทำสูงเท่าไหร่มันยิ่งช้า ดังนั้นเวลาที่เราจะเลือก Algorithm ให้เลือกจากจำนวนครั้งที่มันใช้ ซึ่งเราเรียกเจ้าตัวนี้ว่า Algorithms Complexity ซึ่งโดยปรกติเราจะเขียนมันด้วยสูตรที่เราเรียกมันว่า Big-O เพื่อเอาไว้บอกว่า Algorithm นั้นๆเร็วหรือช้ายังไง จากรูปด้านล่างจะเป็น Big-O ของแต่ละ Data Structure ของพวก Collection เพื่อช่วยในการตัดสินใจ เช่นจะใช้ Array หรือจะใช้ Stack ดี เราก็สามารถดูตารางด้านล่างเปรียบเทียบได้

https://www.bigocheatsheet.com

https://www.bigocheatsheet.com

จากที่แมวน้ำมโนมาทั้งหมด สรุปได้ง่ายๆคือ Algorithm เร็วหรือช้า ไม่ได้ขึ้นอยู่กับ มันซับซ้อนหรือเปล่า เพราะต่อให้เราพยายามศึกษาแล้วก็ยังไม่เข้าใจมันเลย แต่ถ้าค่า Big-O ของมันน้อย มันจะทำงานได้เร็วกว่า Algorithm ประเภทเดียวกันที่มี Big-O เยอะๆนั่นเอง

🍖 ตัวอย่างเพิ่มเติม

ยังจำเรื่องการหา ห.ร.ม. (หารร่วมมาก) สมัยประถมกันได้ไหมเอ่ย? ซึ่งโดยปรกติที่เรียนมาเขาก็จะให้จับหารไปเรื่อยๆจนมันหารไม่ได้ แล้วเอาตัวที่หารไม่ได้ที่เหมือนกันไปคูณกันเพื่อได้ให้ผลลัพท์มาชิมิ ซึ่งนั่นก็เป็น 1 ใน Algorithm ที่สามารถทำได้ แต่ถ้าเราลองไปดู Euclid's algorithm เราก็จะพบวิธีการหาเจ้า ห.ร.ม ในอีกรูปแบบที่ลดขั้นตอนลงไปได้เยอะเลยนั่นเอง ลองดูจากรูปด้านล่างก็ได้

public int GCD(int a, int b)
{
    var x = Math.Max(a, b);
    var y = Math.Min(a, b);
    
    while(y != 0)
    {
        var remain = x % y;
        x = y;
        y = remain;
    }
    
    return x;
}

🎯 บทสรุป (part 1)

ถึงตรงนี้ ดช.แมวน้ำ เชื่อว่าหลายคนน่าจะเข้าใจตรงกันละว่า Algorithm ช้าหรือเร็วขึ้นอยู่กับ Big-O หรือพูดอีกแบบคือ ยิ่ง execute statements เยอะยิ่งช้า และ แต่ละ Data Structure มันเก่งคนละด้าน ดังนั้นอย่าตะบี้ตะบันเอา Solution ที่เจอในเน็ทไปใช้กับงานที่ใช้จริง เพราะมันอาจจะไม่เข้ากับหน้างานเราก็ได้

ข้อความระวัง แมวน้ำเห็นหลายครั้งที่บรรดาโปรแกรมเมอร์จะชอบเข้าใจผิดว่า ยิ่งโค้ดสั้นแสดงว่ามันยิ่งเร็ว ซึ่งถ้าได้อ่านบทความนี้แล้วก็ขอให้หยุดความคิดนั้นไปได้เลย เพราะ ความเร็วไม่ได้ขึ้นกับจำนวนบรรทัดของโค้ด มันขึ้นอยู่กับค่า Big-O เท่านั้น และต่อให้โค้ดคุณจะยาวแค่ 1 บรรทัด แต่ถ้า Big-O ของมันโคตรเยอะแบบ O(n!) มันก็จะช้ากว่าโค้ดที่เขียน 1,000 บรรทัดแต่มี Big-O น้อยๆเช่น O(n)

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

เดี๋ยวเราลองไปดูบทความถัดไปของ Algorithm ว่ามันไปเกี่ยวข้องกับพวกที่ทำ Security ยังไงกันบ้างดีกั่วกับบทความนี้ 👽 Algorithm P & NP