Skip to content

Latest commit

 

History

History
128 lines (85 loc) · 17.2 KB

File metadata and controls

128 lines (85 loc) · 17.2 KB
description
ลองดูดิ๊การบวกเลขมันง่ายจิงป่ะ ? 🤪

👾 Algorithm Big-O

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

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

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

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

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

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

จากที่เกริ่นมา 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 ที่เจอในเน็ทไปใช้กับงานที่ใช้จริง เพราะมันอาจจะไม่เข้ากับหน้างานเราก็ได้

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

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

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