👾Algorithm Big-O

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

🥱 บวกเลข ป.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 หรืออะไรก็ตามก็จะมีปัญหาโดยที่เราไม่รู้ตัวนั่นเอง

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

จากที่แมวน้ำมโนมาทั้งหมด สรุปได้ง่ายๆคือ 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 ที่เจอในเน็ทไปใช้กับงานที่ใช้จริง เพราะมันอาจจะไม่เข้ากับหน้างานเราก็ได้

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