Topic 39: Algorithm Speed

Topic 39	ความเร็วของอัลกอริทึม

ใน Topic 15, ​ Estimating ​ เราเคยพูดถึงการประมาณสิ่งต่างๆ เช่น การเดินข้ามเมืองต้องใช้เวลานานแค่ไหน หรือโปรเจกต์หนึ่งจะเสร็จเมื่อไหร่ แต่ยังมีการประมาณอีกแบบที่ Pragmatic Programmer ใช้กันแทบทุกวัน นั่นคือการประมาณทรัพยากรที่อัลกอริทึมใช้ไป ไม่ว่าจะเป็นเวลา, ตัวประมวลผล, หน่วยความจำ และอื่นๆ

การประมาณแบบนี้มักจะสำคัญมาก เวลาต้องเลือกระหว่างสองวิธีในการทำอะไรสักอย่าง คุณจะเลือกแบบไหน? คุณรู้ว่าโปรแกรมของคุณรันกับข้อมูล 1,000 records ใช้เวลาเท่าไหร่ แต่ถ้าต้องขยายไปถึง 1,000,000 records ล่ะ? ส่วนไหนของโค้ดที่ต้อง optimize บ้าง?

ปรากฏว่าคำถามพวกนี้มักตอบได้ด้วยสามัญสำนึก การวิเคราะห์เล็กน้อย และวิธีเขียนค่าประมาณที่เรียกว่า Big-O notation ครับ

What Do We Mean by Estimating Algorithms? (เราหมายถึงอะไรเมื่อพูดถึงการประมาณอัลกอริทึม)

อัลกอริทึมที่ไม่ธรรมดาส่วนใหญ่ต้องจัดการกับ input ที่มีขนาดแปรผันได้ ไม่ว่าจะเป็นการ sort สตริงจำนวน ตัว, การ invert เมทริกซ์ขนาด หรือการถอดรหัสข้อความด้วยคีย์ขนาด บิต โดยปกติขนาดของ input นี้จะส่งผลต่ออัลกอริทึมเสมอ ยิ่ง input ใหญ่ ก็ยิ่งใช้เวลารันนานขึ้นหรือใช้หน่วยความจำมากขึ้น

ถ้าความสัมพันธ์นี้เป็นเชิงเส้น (linear) เสมอ กล่าวคือเวลาเพิ่มขึ้นตามสัดส่วนของค่า โดยตรง หัวข้อนี้ก็คงไม่สำคัญขนาดนี้ แต่อัลกอริทึมสำคัญๆ ส่วนใหญ่ไม่ได้เป็นเชิงเส้น ข่าวดีคือหลายตัวมี sublinear ด้วยซ้ำ เช่น binary search ที่ไม่จำเป็นต้องดูทุกตัวเลือกเพื่อหาค่าที่ตรงกัน ส่วนข่าวร้ายคืออัลกอริทึมบางตัวแย่กว่าเชิงเส้นมาก เวลาที่ใช้รันหรือหน่วยความจำที่ต้องใช้เพิ่มขึ้นเร็วกว่า มากๆ อัลกอริทึมที่ใช้เวลาหนึ่งนาทีในการประมวลผล 10 รายการ อาจต้องใช้เวลาทั้งชีวิตในการประมวลผล 100 รายการเลยก็ได้

เราพบว่าทุกครั้งที่เขียนอะไรก็ตามที่มี loop หรือ recursive call เราจะเช็ก runtime กับหน่วยความจำที่ต้องใช้แบบไม่รู้ตัวอยู่เสมอ ซึ่งแทบไม่ใช่กระบวนการที่เป็นทางการอะไร แค่เป็นการเช็กเร็วๆ ว่าสิ่งที่เรากำลังทำมันสมเหตุสมผลในสถานการณ์นั้นๆ แต่บางครั้งเราก็ ทำ การวิเคราะห์แบบละเอียดขึ้นจริงๆ และนั่นแหละคือจังหวะที่ Big-O notation จะมีประโยชน์ครับ

Big-O Notation (สัญกรณ์ Big-O)

สัญกรณ์ Big-O เขียนเป็น เป็นวิธีทางคณิตศาสตร์สำหรับจัดการกับค่าประมาณ เวลาที่เราเขียนว่า sort routine ตัวหนึ่ง sort ระเบียน รายการ ด้วยเวลา เรากำลังบอกง่ายๆ ว่าเวลาที่แย่ที่สุด (worst-case) จะแปรผันตามกำลังสองของ ถ้าจำนวนระเบียนเพิ่มขึ้นเป็นสองเท่า เวลาก็จะเพิ่มขึ้นประมาณสี่เท่า ให้คิดว่า หมายถึง ในระดับของ (on the order of)

สัญกรณ์ เป็นการกำหนด upper bound ของค่าที่เรากำลังวัดอยู่ (เวลา, หน่วยความจำ ฯลฯ) ถ้าเราบอกว่าฟังก์ชันหนึ่งใช้เวลา เราก็รู้ว่า upper bound ของเวลาที่ใช้จะไม่โตเร็วไปกว่า บางครั้งเราอาจได้ฟังก์ชัน ที่ค่อนข้างซับซ้อน แต่เพราะพจน์ที่มีดีกรีสูงสุดจะครอบงำค่าทั้งหมดเมื่อ เพิ่มขึ้น ธรรมเนียมปฏิบัติคือให้ตัดพจน์ดีกรีต่ำๆ ทิ้งไปทั้งหมด และไม่ต้องใส่ค่าคงที่ที่คูณอยู่ด้วย:

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

Figure 3, ​ Runtimes of various algorithms ​ แสดง notation ที่พบบ่อยหลายแบบที่คุณจะเจอ พร้อมกราฟเปรียบเทียบเวลารันของอัลกอริทึมแต่ละประเภท เห็นได้ชัดว่าทุกอย่างจะเริ่มควบคุมไม่อยู่ ทันทีที่เกินกว่า

ยกตัวอย่างเช่น สมมติคุณมี routine ที่ใช้เวลาหนึ่งวินาทีในการประมวลผล 100 records แล้วถ้าต้องประมวลผล 1,000 records ล่ะ จะใช้เวลาเท่าไหร่? ถ้าโค้ดของคุณเป็น ก็จะยังใช้เวลาหนึ่งวินาทีเท่าเดิม ถ้าเป็น ก็คงต้องรอประมาณสามวินาที จะเพิ่มขึ้นแบบเชิงเส้นไปถึงสิบวินาที ส่วน จะใช้เวลาประมาณ 33 วินาที ถ้าคุณโชคร้ายเจอ routine แบบ ก็นั่งรอกันยาวๆ 100 วินาทีเลยครับ และถ้าใช้อัลกอริทึมแบบเอ็กซ์โพเนนเชียล ก็อาจจะต้องไปชงกาแฟมาดื่มก่อน เพราะ routine ของคุณน่าจะเสร็จในอีกประมาณ ปีข้างหน้า แล้วอย่าลืมบอกเราด้วยว่าจักรวาลจบลงยังไงนะครับ

สัญกรณ์ ไม่ได้ใช้ได้แค่กับเวลาเท่านั้น คุณยังใช้มันแทนทรัพยากรอื่นๆ ที่อัลกอริทึมใช้ได้ด้วย เช่น บ่อยครั้งก็มีประโยชน์ในการโมเดลการใช้หน่วยความจำ (ดูตัวอย่างได้ในแบบฝึกหัด)

	คงที่ (Constant) — เข้าถึง element ใน array, statement ง่ายๆ
	ลอการิทึม (Logarithmic) — binary search ฐานของลอการิทึมไม่มีผล ดังนั้นจึงเท่ากับ ด้วยเช่นกัน
	เชิงเส้น (Linear) — sequential search
	แย่กว่าเชิงเส้น แต่ก็ไม่ได้แย่มาก (เวลารันเฉลี่ยของ quicksort, heapsort)
	กำลังสอง (Square law) — selection sort, insertion sort
	กำลังสาม (Cubic) — การคูณเมทริกซ์ สองตัว
	เอ็กซ์โพเนนเชียล (Exponential) — traveling salesman problem, set partitioning

Figure 3. เวลารันของอัลกอริทึมแบบต่างๆ (Runtimes of various algorithms)

กราฟแสดงการคำนวณเวลารันของอัลกอริทึมแบบต่างๆ แกนนอนแทนค่า n และแกนตั้งแทนค่าเวลารัน เส้นกราฟของอัลกอริทึม O (C power n) แบบ set cover, O (n squared) แบบ nested arrays และ O (n natural log n) แบบ heap sort search จะเริ่มจากจุดกำเนิดและเพิ่มขึ้นอย่างรวดเร็ว (โค้งขึ้นแบบเว้าขึ้น) ส่วนเส้นกราฟของ O (log n) แบบ binary search เริ่มจากจุดกำเนิด เพิ่มขึ้นถึงระดับหนึ่งแล้วเข้าสู่สภาวะคงที่ เส้นตรงที่เพิ่มขึ้นของ O (n) แบบ sequential search เริ่มจากจุดกำเนิดเช่นกัน และสุดท้ายเส้นคงที่ของ O (1) แบบ array access จะขนานกับแกนนอน

Common Sense Estimation (การประมาณด้วยสามัญสำนึก)

คุณสามารถประมาณ order ของอัลกอริทึมพื้นฐานหลายตัวได้ด้วยสามัญสำนึกครับ

Simple loops (Loop ธรรมดา)

ถ้า loop ธรรมดาวิ่งจาก ถึง อัลกอริทึมนั้นก็มักจะเป็น — เวลาเพิ่มขึ้นแบบเชิงเส้นตามค่า ตัวอย่างเช่น exhaustive search, การหาค่าสูงสุดใน array และการสร้าง checksum

Nested loops (Loop ซ้อนกัน)

ถ้าคุณซ้อน loop หนึ่งไว้ในอีก loop หนึ่ง อัลกอริทึมของคุณจะกลายเป็น โดยที่ และ คือขีดจำกัดของ loop ทั้งสอง กรณีนี้พบได้บ่อยใน sorting algorithm ง่ายๆ อย่าง bubble sort ที่ loop ด้านนอกจะไล่สแกนแต่ละ element ใน array ทีละตัว ส่วน loop ด้านในจะหาตำแหน่งที่ควรวาง element นั้นในผลลัพธ์ที่ sort แล้ว sorting algorithm แบบนี้มักจะเป็น

Binary chop (การตัดครึ่งแบบ Binary)

ถ้าอัลกอริทึมของคุณตัดสิ่งที่ต้องพิจารณาออกครึ่งหนึ่งทุกครั้งที่วนลูป มันก็มักจะเป็นแบบลอการิทึม ทั้ง binary search ของ list ที่ sort แล้ว, การไล่ traverse binary tree และการหาบิตแรกที่ถูกตั้งค่าใน machine word ล้วนเป็น ได้ทั้งหมด

Divide and conquer (แบ่งแยกแล้วเอาชนะ)

อัลกอริทึมที่แบ่ง input ออกแล้วทำงานกับสองครึ่งนั้นแยกกัน จากนั้นค่อยรวมผลลัพธ์เข้าด้วยกัน อาจเป็น ตัวอย่างคลาสสิกคือ quicksort ที่ทำงานโดยแบ่งข้อมูลออกเป็นสองครึ่งแล้ว sort แต่ละครึ่งแบบ recursive แม้ในทางเทคนิคจะเป็น แต่เพราะพฤติกรรมของมันจะแย่ลงเมื่อได้รับ input ที่ sort มาแล้ว เวลารันเฉลี่ยของ quicksort จึงเป็น

Combinatoric (เชิงการจัดหมู่)

เมื่อไหร่ก็ตามที่อัลกอริทึมเริ่มพิจารณา permutation ของสิ่งต่างๆ เวลารันของมันอาจควบคุมไม่อยู่ได้ เพราะ permutation เกี่ยวข้องกับ factorial (มี รูปแบบการจัดเรียงของตัวเลข 1 ถึง 5) ลองจับเวลาอัลกอริทึมเชิงการจัดหมู่กับ 5 elements ดู มันจะใช้เวลานานขึ้นถึง 6 เท่า เมื่อรันกับ 6 elements และนานขึ้น 42 เท่าเมื่อรันกับ 7 elements ตัวอย่างเช่นอัลกอริทึมสำหรับปัญหาที่ขึ้นชื่อว่า hard หลายๆ ปัญหา ไม่ว่าจะเป็น traveling salesman problem, การจัดของลงกล่องให้เหมาะสมที่สุด, การแบ่งชุดตัวเลขให้แต่ละชุดมีผลรวมเท่ากัน และอื่นๆ บ่อยครั้งที่มีการใช้ heuristic เพื่อลดเวลารันของอัลกอริทึมประเภทนี้ในโดเมนปัญหาที่เจาะจง

Algorithm Speed in Practice (ความเร็วของอัลกอริทึมในทางปฏิบัติ)

ไม่น่าเป็นไปได้ที่คุณจะใช้เวลาไปมากมายในอาชีพการงานเพื่อเขียน sort routine เอง เพราะตัวที่มีอยู่ใน library ต่างๆ ที่คุณเข้าถึงได้มักจะทำงานได้ดีกว่าอะไรก็ตามที่คุณเขียนเองโดยไม่ลงแรงมากๆ อยู่แล้ว แต่อัลกอริทึมพื้นฐานประเภทที่เราอธิบายไปก่อนหน้านี้ ก็ยังโผล่มาให้เห็นอยู่เรื่อยๆ ทุกครั้งที่คุณเขียน loop ธรรมดา คุณก็รู้แล้วว่าคุณมีอัลกอริทึม ถ้า loop นั้นมี loop ซ้อนอยู่ข้างใน คุณก็กำลังมองที่ คุณควรถามตัวเองว่าค่าพวกนี้จะโตได้มากแค่ไหน ถ้าตัวเลขมีขอบเขตจำกัด คุณก็จะรู้ว่าโค้ดจะใช้เวลารันนานแค่ไหน แต่ถ้าตัวเลขขึ้นอยู่กับปัจจัยภายนอก (เช่น จำนวน records ใน batch run ตอนกลางคืน หรือจำนวนชื่อใน list ของคน) คุณอาจต้องหยุดคิดถึงผลกระทบที่ค่าที่มากๆ อาจมีต่อเวลารันหรือการใช้หน่วยความจำครับ

Tip 63	ประมาณ Order ของอัลกอริทึมที่คุณใช้

มีวิธีบางอย่างที่คุณใช้รับมือกับปัญหาที่อาจเกิดขึ้นได้ ถ้าคุณมีอัลกอริทึมที่เป็น ลองหาวิธี divide-and-conquer ที่จะพาคุณลงมาที่ ดูครับ

ถ้าคุณไม่แน่ใจว่าโค้ดของคุณจะใช้เวลานานแค่ไหน หรือใช้หน่วยความจำเท่าไหร่ ลองรันดูโดยปรับจำนวน record ของ input หรืออะไรก็ตามที่น่าจะส่งผลต่อเวลารัน แล้วพล็อตผลลัพธ์ออกมา คุณก็จะเริ่มเห็นภาพรูปทรงของกราฟได้ไม่ยาก มันโค้งขึ้น เป็นเส้นตรง หรือค่อยๆ แบนราบลงเมื่อขนาด input เพิ่มขึ้น? แค่สามสี่จุดก็น่าจะพอให้คุณเห็นภาพแล้วครับ

อีกเรื่องที่ควรพิจารณาคือสิ่งที่คุณทำในโค้ดจริงๆ loop แบบง่ายๆ อาจทำงานได้ดีกว่า loop ที่ซับซ้อน สำหรับค่า ขนาดเล็กๆ โดยเฉพาะถ้าอัลกอริทึม นั้นมี inner loop ที่ต้นทุนสูง

ท่ามกลางทฤษฎีทั้งหมดนี้ อย่าลืมว่ายังมีเรื่องเชิงปฏิบัติที่ต้องคำนึงถึงด้วย เวลารันอาจดูเหมือนเพิ่มขึ้นแบบเชิงเส้นสำหรับ input ขนาดเล็ก แต่พอป้อนโค้ดด้วยข้อมูลหลักล้าน records เวลาจะแย่ลงทันทีเพราะระบบเริ่ม thrash ถ้าคุณทดสอบ sort routine ด้วย random input keys คุณอาจจะแปลกใจตอนที่มันเจอ input ที่ถูก sort มาแล้วเป็นครั้งแรก พยายามครอบคลุมทั้งฐานทางทฤษฎีและทางปฏิบัติ หลังจากประมาณกันมาทั้งหมดนี้ สิ่งเดียวที่นับได้จริงๆ คือความเร็วของโค้ดคุณตอนรันบน production environment ด้วยข้อมูลจริง ซึ่งนำไปสู่ tip ถัดไปของเราครับ

Tip 64	ทดสอบค่าที่คุณประมาณไว้

ถ้าการจับเวลาให้แม่นยำเป็นเรื่องยาก ให้ใช้ code profiler เพื่อนับจำนวนครั้งที่แต่ละขั้นตอนในอัลกอริทึมของคุณถูกเรียกใช้ แล้วพล็อตตัวเลขเหล่านั้นเทียบกับขนาดของ input

Best Isn't Always Best (ดีที่สุดไม่ได้แปลว่าดีที่สุดเสมอไป)

คุณยังต้อง Pragmatic ในการเลือกอัลกอริทึมที่เหมาะสมด้วย ตัวที่เร็วที่สุดไม่ได้แปลว่าเหมาะกับงานที่สุดเสมอไป ถ้า input set มีขนาดเล็ก insertion sort ธรรมดาๆ ก็ทำงานได้ดีพอๆ กับ quicksort และใช้เวลาเขียนกับ debug น้อยกว่าด้วย คุณยังต้องระวังด้วยว่าถ้าอัลกอริทึมที่คุณเลือกมี setup cost สูง สำหรับ input set ขนาดเล็ก setup cost นี้อาจกลบเวลารันจนหมด และทำให้อัลกอริทึมนั้นไม่เหมาะสมเลยก็ได้

ระวัง premature optimization ด้วยนะครับ การตรวจสอบให้แน่ใจก่อนว่าอัลกอริทึมนั้นเป็น bottleneck จริงๆ ก่อนจะทุ่มเวลาอันมีค่าไปกับการปรับปรุงมัน ถือเป็นความคิดที่ดีเสมอ

Related Sections Include (หัวข้อที่เกี่ยวข้อง)

• Topic 15, ​ Estimating ​

Challenges (ความท้าทาย)

• นักพัฒนาทุกคนควรมีความรู้สึกเข้าใจว่าอัลกอริทึมถูกออกแบบและวิเคราะห์อย่างไร Robert Sedgewick ได้เขียนหนังสือชุดหนึ่ง ที่เข้าใจง่ายในหัวข้อนี้ ( Algorithms  [SW11] An Introduction to the Analysis of Algorithms  [SF13] และเล่มอื่นๆ) เราแนะนำให้คุณหาหนังสือของเขาสักเล่มมาไว้ในคอลเลกชัน และตั้งใจอ่านมันจริงๆ ครับ

• สำหรับใครที่ชอบรายละเอียดมากกว่าที่ Sedgewick ให้ไว้ ลองอ่านหนังสือชุด Art of Computer Programming ของ Donald Knuth ที่เป็นเล่มอ้างอิงหลัก ซึ่งวิเคราะห์อัลกอริทึมหลากหลายแบบไว้อย่างละเอียด

  • The Art of Computer Programming, Volume 1: Fundamental Algorithms  [Knu98]
  • The Art of Computer Programming, Volume 2: Seminumerical Algorithms  [Knu98a]
  • The Art of Computer Programming, Volume 3: Sorting and Searching  [Knu98b]
  • The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1  [Knu11] .

• ในแบบฝึกหัดแรกที่ตามมา เราจะมาดูการ sort array ของเลข long integer กัน แล้วถ้า key มีความซับซ้อนมากกว่านี้ และมี overhead ในการเปรียบเทียบ key ที่สูงล่ะ จะส่งผลอย่างไร? โครงสร้างของ key มีผลต่อประสิทธิภาพของ sort algorithm หรือไม่ หรือว่า sort ที่เร็วที่สุดก็ยังเร็วที่สุดอยู่ดี?

Exercises (แบบฝึกหัด)

Exercise 28 ( possible answer )

เราเขียน sort routine ง่ายๆ ชุดหนึ่ง [54] ด้วยภาษา Rust ลองรันมันบนเครื่องต่างๆ ที่คุณมี ตัวเลขที่ได้เป็นไปตามกราฟที่คาดไว้หรือไม่? คุณสรุปอะไรได้บ้างเกี่ยวกับความเร็ว ของเครื่องต่างๆ ของคุณ? การตั้งค่า compiler optimization ต่างๆ ส่งผลอย่างไรบ้าง?

Exercise 29 ( possible answer )

ใน ​ Common Sense Estimation ​ เราบอกว่า binary chop เป็น คุณพิสูจน์ได้ไหม?

Exercise 30 ( possible answer )

ใน Figure 3, ​ Runtimes of various algorithms ​ เราบอกว่า เท่ากับ (หรือลอการิทึมฐานอะไรก็ได้) คุณอธิบายได้ไหมว่าทำไม?