"อยากเขียนโค้ดเดอะซีรีย์" ep 2
โอเคครับ ต้องขอย้อนกลับไปเมื่อ ep ที่แล้วสักครู่หนึ่ง บางทีอาจจะสงสัยว่า การวัดประสิทธิภาพ เหล่า Competitive Programming ดูแค่ตรงนั้นจริง ๆ หรือ ?
และแน่นอน คำตอบคือ "ไม่ใช่"
ซีรี่ย์นี้ทำขึ้นมาเพื่อเป็น Output อย่างหนึ่งในตัวเราเอง หลังจากศึกษาการทำโค้ด หรือการเขียนโปรแกรม (ตอนนี้กำลังอยากจะศึกษามากขึ้นของมากขึ้น)
และก็โอ๊ะโอ เราไม่ได้สอนเขียนโค้ดนะครับ เพียงแต่อาจจะสามารถศึกษาได้ในเบื้องต้นจริง ๆ เพราะเราก็อธิบายให้ง่าย ๆ เพื่อให้บางทีเรามาอ่านทวนได้ ^^
โอเค หลังจากที่เราพูดถึงการวัดประสิทธิภาพกันไปแล้ว แต่เราพูดไปเป็นส่วนน้อยมาก ทำให้คนที่อาจจะอยากศึกษาเหมือนกับเรายังไม่รู้ Overview เหมือนหนังสือไม่มีสารบัญนั่นเอง (และมันยากลำบากมากเลย ฮือ)
ออกตัวก่อนว่า เราก็เพิ่งเรียน / ศึกษา หากผิดพลาดประการใด สามารถติเพื่อก่อได้ และขออภัยมา ณ ที่นี้ด้วยครับ
Algorithm คือ อะไร ?
ขออนุญาตพูดง่าย ๆ ว่า สิ่งนี้คือ ลำดับวิธีการทำงานเพื่อให้ได้ผลลัพธ์ตามต้องการ
เช่น การจะทำไข่เจียว เราต้องเริ่มจากการเตรียมวัตถุดิบ เครื่องครัว ก่อนที่จะเริ่มตอกไข่ ปลุงเล็กน้อย ตีไข่ ใส่น้ำมัน (ถ้าใช้กระทะหินอ่อนก็คงไม่จำเป็น >///<) เปิดแก๊ส (หรือไม่เปิดแล้วแต่สูตร) เอาไข่เทลงกระทะ รอด้านหนึ่งสุก พลิก รอ ปิดแก๊ส ตักใส่จาน เป็นอันเสร็จ
ทำนองนี้ครับ แต่ทว่าในเรื่องของ Competitive Programming เหมือนจะไม่ได้มองเป็นอย่างนั้นโดยตรง เพราะในหนึ่งปัญหา ๆ เราแก้ได้หลายวิธี และวิธีไหนกันที่ดีที่สุดกันนะ ?
วันนี้เราได้เรียนเรื่องนี้ และอาจารย์ผู้สอนก็ได้พูดถึง 4 หลักการของอัลกอริทึมที่ดีได้ 4 ข้อ ดังนี้
1. Correctness
2. Time Complexity
3. Space Complexity
4. Error (Approximate)
จาก 4 ข้อที่ผ่านมา จะสังเกตว่า Time complexity จริง ๆ ก็คือ ส่วนที่พูดถึงไปบ้างแล้วในครั้งที่แล้วนั่นเอง อย่างหาเงิน 10 บาทจากหีบ 10 ใบ ที่มีแค่หีบเดียวที่มีเงินอยู่เพื่อไปซื้อขนม
และแน่นอน ความน่าสนใจและท้าทายของมันก็มีมากจนเกิดการแข่งขันขึ้น และรายการใหญ่ ๆ ที่เด็กค่ายโอลิมปิกวิชาการ สอวน. รู้จักกันดีก็หนีไม่พ้น Thailand Olympiad in Informatics (TOI)
แล้ว เราจะวัดผลประสิทธิภาพอัลกอริทึมยังไงนะ ?
เราขอเริ่มเป็นข้อ ๆ ละกัน
ข้อแรก Correctness :
ข้อนี้คือความถูกต้อง ประมาณว่า ให้เราแก้ปัญหา 1 + 2 + 3 + 4 + 5 + ... + 97 + 98 + 99 + 100 = ____
แล้วถ้าคำตอบของอัลกอริทึมไม่ใช่ 5,050 ก็แสดงว่าอัลกอริทึมนี้ไม่ถูกต้องนั่นเอง
โอเค ข้อสองค่อนข้างเยอะ ขอข้ามไปข้อสามสักครู่
ข้อที่สาม Space Complexity :
เป็นการวิเคราะห์หน่วยความจำทั้งหมดที่ใช้เพื่อประมวลผลโปรแกรม เพื่อรับค่าแล้วไม่เกิดข้อผิดพลาด หรือทำงานได้ถูกต้อง
ส่วนประกอบทั่วไปของเรื่องนี้ เช่น ขนาดความจำของ Compiler, Data space (มี 2 ประเภท คือ Static memory และ Dynamic memory) และ Environment stack space
และนี่คือตัวอย่างของคนอ่านโจทย์ไม่ดีที่เลือกใช้ Data space ไม่เพียงพอ...
ภาพการส่งโค้ดเข้าเกรดเดอร์ แต่ภาพนี้เราเลือก Data Space ผิด
ซึ่งแน่นอน ผมแทบจะรื้อโค้ดใหม่ทั้งแผงอยู่แล้วจนกระทั่งเราลองเปลี่ยนตัวแปร Environment stack data ที่เอาไว้เก็บคำตอบจาก int ไปเป็น double
แล้วผลที่ได้ก็คือ...
จะสังเกตว่า Memory มีขนาดใหญ่ขึ้น
นั่นทำให้เราเริ่มรู้ความจริงว่า เรามีสิทธิที่จะจอง space ไม่พอ
ทีนี้เราก็เลยเอา long long มาใช้เลย และนี่คือผลลัพธ์ของมัน...
เย้ ได้เต็มกับเขาเสียที
โอเค สิ่งที่เราเห็นอีก ก็คือ Memory ใช้มากขึ้น
แต่ในนี้เรายังเห็นสิ่งที่เรียกว่า Time อีกด้วย และถ้าเวลาไม่ทันที่เขากำหนด (ในโจทย์ข้อนี้ คือ 2 second) และเราก็มาต่อกันที่เรื่องที่ 3
ข้อที่สอง Time Complexity :
จริง ๆ ส่วนนี้เราดูได้จาก Algorithm Growth Rates ที่มี Big-O, Big-Omega, Big-Tera, Little-o, Little-omega
อธิบายง่าย ๆ ด้วยคำว่า Big-O คือ กรณีที่ใช้เวลาในการประมวลผลที่นานที่สุดนั่นเอง (หรือที่เราเรียกว่า Worst-Case จาก ep ที่แล้ว)
ส่วน Big-Omega ก็ตรงข้ามกัน คือ เวลาที่ใช้ในการประมวลผลดีที่สุด
Big-Tera เป็นเวลาที่อยู่ระหว่าง Lower bound กับ Upper bound นั่นแหละ
ส่วน Little ทั้งคู่ก็เหมือนกับ เหล่า Big ที่ลงท้ายเหมือนกนนั่นแหละ เพียงแต่ไม่ถึงขอบเท่านั้นเอง
ส่วนเรื่องที่ 4 เรายังไมได้เรียน และคิดว่า คงยังไม่เรียนในเร็ว ๆ นี้แน่นอน แต่เราอาจจะไปหาอ่านมาลง (ย้ำว่าอาจจะ)
ปัญหาที่น่าสนใจที่อาจารย์ให้ทำในครั้งนี้ คือ ปัญหาการโยนไข่จากตึก เราจะรู้ได้ยังไงว่า ไข่จะไม่แตกในชั้นไหนของตึก n ชั้น โดยมีไข่อยู่จำนวนจำกัด
เช่น มีไข่ 1 ฟอง ตึก 10 ชั้น จะรู้ได้ยังไงว่าไข่จะไม่แตกเมื่อโยนลงมาจากชั้นไหน ?
คำตอบก็คือ เราก็ต้องโยนตั้งแต่ชั้น 1 ขึ้นไปชั้น 2 3 4 5 6 7 8 9 10 แล้วดูว่าแตกชั้นไหน เราก็จะตอบชั้นด้านล่างนั้นนั่นเอง
และเมื่อเรามองเป็น Big-O เราจะพบว่ากรณีที่แย่ที่สุด คือ ไข่ไม่แตกทั้ง 10 ชั้น หรือ ไข่แตกในชั้นที่ 10 ซึ่งก็ทำให้เรารู้ว่าประสิทธิภาพของ Solution นี้เป็น O(n) นั่นเอง
แต่ถ้าเรามีไข่ 2 ฟองละ ?
ในตอนนั้น ผมคิดแบบมักง่าย คือ โยนที่ชั้น n/2 แล้วก็ค่อยโยนไปเป็น n/2 +1 +2 +3 + ... จนถึง n ถ้าไม่แตกที่ชั้น n/2
แต่เอ๊ะ เมื่อเราลดจำนวนชั้นลงมา เราจะเห็นว่า มีโอกาสที่จะหาจำนวนชั้นได้ดีขึ้น เช่น ถ้าเราโยนไข่ใบที่ 1 ที่ชั้นที่เป็นเลขคู่ล่ะ ? เช่น 2 4 6 8 10 12 14 ... ถ้าแตกชั้นไหน เราก็แตโยนในชั้นเลขคี่ที่ถัดลงมา 1 ชั้นเท่านี้ก็ได้คำตอบแล้ว
แต่เมื่อประสิทธิภาพต่ำมาก ๆ
เราก็เลยมั่วขึ้น ใช่ครับ ฟังไม่ผิดครับ "มั่ว"
เราก็ไล่แบ่งชั้นเลยครับ เป็นแพทเทิร์น ไข่ใบแรกที่ ชั้น 2 4 6 8 10 ... พอไม่เวิร์คก็ที่ 3 6 9 12 15 ... วนแบบนี้วนไปวนมา เราก็ไปสะดุดที่ case 25 ชั้น กับการเพิ่มทีละ 5 ของไข่ใบแรก
สมมติ ไข่ใบแรกแตกที่ชั้น 25 พอดี ไข่ใบที่ 2 ก็ต้องเริ่มโยนจากชั้นที่ 21 ไล่มาที่ 22 23 และ 24 ซึ่งเราก็เลยมั่วต่อไปอีก ว่าถ้า 100 ชั้นเพิ่มทีละ 10 ละ
และนั่นทำให้เรามั่วจนถูก เพราะเราประมาณขึ้นมาว่า น่าจะเป็น O(sqrt(n)) แน่นอน เพราะถ้าอยากให้โยนไข่น้อยที่สุด ไข่ทั้งสองฟองต้องโยนในจำนวนครั้งที่ใกล้เคียงกัน และกรณีที่เราสุ่มมั่วจนจับสังเกตได้ก็นำไปสู่คำตอบของครั้งนี้นั่นเอง !
// อาจารย์จะเข้ามาอ่านไหมนะ >,w,<
โอเค ส่วนอีกคำถามก็คือ ถ้ามีไข่ k ใบ จะคิดยังไง
อันนี้คิดไม่ออก แต่ตอนนั้นเดาในใจไปว่า คงคล้ายเดิมแหละ น่าจะ O(รากที่ n ของ n) เพราะไข่ 2 ใบเป็นรากที่ 2 ของ n
แต่คำตอบที่ถูกต้อง ตามที่อาจารย์เฉลยก็คือ O(n * (รากที่ n ของ n))
ลองคิดกันดูนะครับ อิอิ
ep นี้จบแล้วดีกว่า ใครชอบหรือสนใน "อยากเขียนโค้ด" ก็คุยกันได้นะครับ
ส่วนพาดหัวครั้งที่แล้ว ที่บอกว่า บางทีเราก็ตั้งคำถามว่าเราเปปป็นผู้ใหญ่รึยังนะ ? เป็นการสปอยด์เนื้อหาที่เราคิดไว้ว่าจะทำแนวปรัชญา การ Rethinking หรือแม้แต่ Scientific thinking ก็เลยทำทิ้งไว้
สำหรับ ep นี้ขอตัวลาไปก่อน สวัสดีครับ ^^
- 2
โฆษณา
- ดาวน์โหลดแอปพลิเคชัน
- © 2025 Blockdit
