การวัดประสิทธิภาพของ Algorithm (Algorithm Efficiency Analysis)

ดร.บุญญฤทธิ์ อุยยานนวาระ
ภาควิชาคอมพิวเตอร์และเทคโนโลยีสารสนเทศ
สถาบันเทคโนโลยีนานาชาติสิรินธร
มหาวิทยาลัยธรรมศาสตร์

โอเค เรารู้แล้วหล่ะว่า Algorithm คือกระบวนการในการแก้ปัญหา และรู้แล้วว่าปัญหาคืออะไร ปัญหามีประมาณกี่ประเภท แล้วรู้ว่าเราจะเรียน Algorithm ไปทำไม งั้นมาเริ่มเขียน Algorithm กันดีกว่า

การเขียน Algorithm โดยปกติก็คือ การถ่ายทอดกระบวนการความคิด สิ่งที่เราคิดออกไปให้คนอื่นได้รับรู้ได้ เพราะฉนั้นก็คือการถ่ายทอดสิ่งที่อยู่ในหัวของเราออกไปบนกระดาษให้ได้ และปัจจุบันเราก็มีกรรมวิธีในการแทนความคิดอย่างหลากหลายกันออกไป แต่วิธีที่ได้รับการยอมรับในวงการคอมพิวเตอร์ก็พอจะมีอยู่ซัก 4-5 วิธีด้วยกัน เช่น Conceptual Flow, Flowchart, Pseudocode หรือ Descriptive แต่เราขอเลือกมาเรียนกันซัก 2 อันก็พอ คือ Conceptual Flow กะ Pseudocode เพราะเห็นว่าเป็นแบบที่ได้รับความนิยมอยู่ในปัจจุบัน (แปลว่ามันอาจจะเชยไปในอนาคต เหมือนกับที่เมื่อก่อนเค้าใช้กันแต่ Flowchart แต่ในปัจจุบันการใช้ flowchart ก็ลดน้อยถอยลงไป เพราะว่ามันอธิบายกรรมวิธีที่ซับซ้อนไม่ค่อยได้ หรือถ้าได้ก็ต้องทำ flowchart ที่ซับซ้อนซึ่งก็ก่อให้เกิดเป็นปัญหาของตัวมันเอง กลายเป็นต้องมาแก้ปัญหาการทำ flowchart ไปซะแทน)

Conceptual Flow

การถ่ายทอด Algorihtm ด้วย Conceptual Flow เป็นเหมือนการถ่ายทอดความคิดออกมาทีละขั้นเหมือนกับที่เราคิดจริงๆ โดยไม่มีเงื่อนไขของกฏเกณใดๆให้ปวดหัว (ไม่เหมือนกับ flowchart ที่มีโครงสร้างและสัญลักษณ์ต้องจำ) ซึ่งตรงนี้นอกจากจะทำให้คนอื่นเข้าใจ Algorithm ของเราแล้ว ยังเป็นการฝึกการถ่ายทอดความคิดของเราเองอีกด้วย

การถ่ายทอดความคิดด้วยวิธีนี้ก็เป็นธรรมชาติที่สุด คือ อธิบายขั้นตอนแต่ละขั้นในการแก้ปัญหาโดยละเอียด ชัดเจน ทีละขั้นๆ จนจบกระบวนการแก้ปัญหา โดยใช้แค่วงกลมบอกถึงแต่ละขั้นตอนของความคิด และ ลูกศร ในการระบุทิศทางการไหลของความคิด แค่นั้นเอง

ยกตัวอย่างเปรียบเทียบง่ายๆเพื่อให้เห็นภาพก็แล้วกันครับ เหมือนกับคู่มือทำเค๊กกล้วยหอมไงครับ ถ้าคุณเปิดตำราทำอาหาร คุณก็จะพบว่าการทำเค๊กกล้วยหอมก็มี input เป็น น้ำตาล กล้วยหอม แป้ง ไข่ เป็นต้น คราวนี้ถ้าคุณลงมือปฏิบัติตาม algorithm การทำเค้กกล้วยหอม เช่น ขั้นที่ 1 ตอกไข่ ขั้นที่ 2 ตี 30 ที ขั้นที่ 3 เปิดเตาอบไว้ที่อุณหภูมิ 150 องศา ไปเรื่อยๆแบบนี้ สุดท้าย ไม่ว่าใครทำ ก็จะได้ output เป็นเค้กกล้วยหอมเสมอไงครับ

แต่ algorithm ที่ไม่ดี ก็อาจจะบรรยายแต่ละขั้นตอนอย่างคลุมเคลือ เช่น ขั้นที่ 2 ตีไข่ จนกว่าไข่จะผสมกันดี หรือ ขั้นที่ 3 ตั้งไฟเตาอบไว้ที่พอร้อนพอดี ซึ่งถ้าคุณอธิบาย algorithm ในลักษณะแบบนี้จะทำให้ programmer หรือ คนที่จะมาทำตาม algorithm ของคุณ ทำ 10 คนอาจจะไม่ได้เค้กกล้วยหอมทั้ง 10 คนเป็นต้น

โอเค งั้นเราลองเขียน Conceptual Flow กันซักอันนึงก็แล้วกัน โดยดูปัญหา Nag Screen ง่ายๆกันดังนี้ครับ

ปัญหานี้ดูเหมือนว่าจะง่ายเกินไป แต่ก็เป็นจุดเริ่มต้นที่ดีในการเริ่มต้น 555 โอเค งั้นเอาเป็นว่า เราลองมาเขียน conceptual flow เพื่อแก้ปัญหานี้ (และได้เอาไว้ใช้บอกให้โปรแกรมเมอร์เขียนโปรแกรมตาม conceptual flow นี้) (เดี๋ยวผมมาทำเป็น flow แล้วเอามาแปะให้อีกที)

1.
2.
3.
4.

พอจะเห็นภาพแล้วนะครับ จะเห็นได้ชัดว่าแม้วิธีแรกจะสามารถบรรยาย Algorithm ในหัวเราออกมาได้อย่างง่ายดาย งั้นลองทดลองเขียน conceptual flow ด้วยตัวเองดูซักอันนะครับ กับปัญหา Travelling Salesman ตามนี้

จะเห็นได้ชัดว่า conceptual flow เป็นวิธีที่ใช้สามารถบรรยาย Algorithm ในหัวเราออกมาได้อย่างง่ายดาย แต่มันออกจะไม่เป็นทางการไปหน่อย คือมันออกจะเหมือนต่างคนต่างอธิบายด้วยสไตล์ของตัวเอง ไม่มีความเป็นกลาง คนอื่นอาจจะไม่เข้าใจสิ่งทีเราบอก ไม่เป็นมาตรฐาน คนไทยอาจจะรู้เรื่อง แต่ฝรั่งมาอ่านแล้วงง ประมาณนั้น เราก็เลยคงต้องเรียนรู้การถ่ายทอดความคิดในการแก้ปัญหาอีกรูปแบบที่ดูจะมีโครงสร้างที่ชัดเจนมากว่า นั่นก็คือ Pseudocode นั่นเอง

Pseudo Code

โอเค เราเริ่มเข้าเรื่องมีสาระและทางการมากขึ้นแล้วนะครับ (555 หลายคนเริ่มเครียด)

แม้ว่า Pseudocode จะดูเหมือนการถ่ายทอด Algorithm ที่เป็นมาตราฐาน แต่เอาเข้าจริงๆก็ไม่ได้มีมาตรฐานที่ชัดเจนว่า การเขียน Algorithm ด้วย Pseudocode ทีเหมือนกันทั้งโลก เพียงแต่ลักษณะที่เราใช้จะใกล้เคียงกันทั้งหมด หมายความว่า แม้โครงสร้างไม่เหมือนกันเป๊ะ แต่อ่านแล้วก็เข้าใจกันได้ทั่วโลกนั่นแหล่ะ

เอาหล่ะ แล้วเขียน Pseudocode นี่เป็นไง

555 ตรงนี้รอแป๊บ หิวแล้วเดี๋ยวกลับมาเขียนต่อให้นะคร้าบบ :-D

ปัญหา -> algorithm A -> f(n) -> O(xx)
ปัญหา -> algorithm B -> f(n) -> O(xx)

Asymptotic Order of Growth

ในการวัดประสิทธิภาพของ Algorithm นั้นทำได้หลายวิธีด้วยกัน แต่ตัววัดที่แพร่หลาย ที่มักจะใช้ชี้ถึงประสิทธิภาพของ algorithm คือ เวลา หรือ ความเร็ว นั่นเอง เพราะเป็นการวัดแบบ black box ว่าถ้าหากว่ากรรมวิธีแก้ปัญหาที่ดีมันจะต้องกินเวลาที่มันต้องใช้ในการประมวลผลแก้ปัญหาน้อยนั่นเอง 

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

ลองจินตนาการดูว่า เรามีปัญหาเดียวกันแต่คิดแก้ปัญหาโดยคนทั่วโลก เราจะทำอย่างไรถึงจะเปรียบเทียบประสิทธิภาพของ algorithm จากทั่วโลกได้ โดยใช้สิ่งแวดล้อมเดียวกัน หรือถ้ามีคนคิด algorithm นึงไว้เมื่อ 50 ปีที่แล้ว ทำอย่างไรคนนั้นถึงจะได้ run โปรแกรมของเค้าบนเครื่องเดียวกับที่พวกเราใช้ในปัจจุบัน ไม่มีทาง

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

แล้ว f(n) ที่ว่านี้ก็ได้มาจากการนับ ปริมาณงานที่ algorithm หนึ่งๆใช้ในการประมวลผล input n ชิ้น

บิ๊กโอ Big Oh

ความหมายของ Big O

Big O เป็น upper bound ของ worst case ของ algorithm ซึ่งหมายความว่า algorithm นี้จะทำงานไม่แย่ไปกว่า Big O ของมันแล้ว ซึ่งก็เหมือนกับเป็นตัวบอกถึง ประสิทธิภาพของ algorithm นั้นๆนั่นเอง เพื่อใช้ในการเปรียบเทียบ algorithm หลายอันเข้าด้วยกัน

algorithm ที่อยู่ใน O(n) ก็หมายความว่าถ้าใช้ algorithm นี้ประมวลข้อมูล n อย่าง มันจะมีขั้นตอนในการประมวลผลประมาณ n ครั้ง

ส่วน algorithm ที่อยู่ใน O(n³) ก็หมายความว่าถ้าใช้ algorithm นี้ประมวลข้อมูล n อย่าง มันจะมีขั้นตอนในการประมวลผลประมาณ n³ ครั้ง และไม่ช้าไปกว่านั้น

ด้วยวิธีนี้เราถ้าเรารู้ Big O ของ algorithm ใดๆ เราก็พอที่จะเปรียบเทียบความสามารถในการแก้ปัญหาของ algorithm นั้นๆได้แล้ว อย่างเช่น O(n) นั้นเร็วกว่า O(n³) เห็นๆ ถ้าประมวลข้อมูลเท่าๆกัน

เอาอย่างนี้ก็แล้วกัน ถ้ายังรู้สึกงงๆ ผมยกตัวอย่างง่ายๆ ประกอบเพื่อให้เห็นภาพ (ทั้งที่มันไม่ค่อยเกี่ยวเท่าไหร่) เหมือนกับถามว่า ยานพาหนะคันนี้มีประสิทธิภาพแค่ไหน ถ้าเราบอกว่า ยานพาหนะความเร็วประมาณจักรยาน หรือ ยานพาหนะนี้มีความเร็วประมาณรถยนต์ หรือ ยานพาหนะนี้มีความเร็วประมาณเครื่องบินไอพ่น เราก็พอจะเห็นภาพได้ว่ายานพาหนะนี้มีประสิทธิภาพด้านความเร็วแค่ไหน ซึ่งถ้าหากเราเอายานพาหนะมาเปรียบเทียบกัน เราก็จะรู้ทันทีว่าอันไหนดีกว่าอันไหน หรือมีประสิทธิภาพอยู่ประมาณใด

ซึ่งในแง่ของ Big O แล้ว เราก็พอจะมีระดับความสามารถของ algorithm อยู่หลายระดับเช่นกัน เช่นว่า O(log n) อันนี้เร็วมากเทียบได้กับเครื่องบินเจ็ตก็แล้วกัน ส่วน O (2ⁿ) อันนี้ช้าเป็นจักรยานเลย เป็นต้น ซึ่ง class ต่างๆของ Big O ก็ถูกบรรยายเอาไว้แล้วในหัวข้อถัดไปนั่นเอง

และเพื่อให้เห็นภาพ ว่าคุณควรจะเลือกใช้ algorithm ไหนในการแก้ปัญหา เอาเป็นว่า สมมุติว่าปัญหาของคุณคือ ต้องเดินทางจากเมืองไทยไปอังกฤษ แล้วมีอัลกอริทึ่มให้เลือกใช้หลายอัน ถามว่าคุณอยากจะเลือกใช้ algorithm ที่อยู่ในคลาสไหน ระหว่าง algorithm ที่มีประสิทธิภาพใน class ของ จักรยาน กับ algorithm ที่มีประสิทธิภาพใน class ของ เครื่องบินเจ็ต และถ้าหากว่าถ้าคุณใช้ algorithm ที่มีประสิทธิภาพใน class ของ จักรยาน งานนี้ของคุณอาจจะใช้เวลาหลายเดือนในการแก้ปัญหา เมื่อเทียบกับไม่กี่ชั่วโมง ถ้าหากใช้ algorithm ที่มีประสิทธิภาพใน class ของ เครื่องบินเจ็ต เป็นต้น

ถ้าจะให้เรียงลำดับ Big O มาตรฐาน (ที่เจอบ่อยๆ) เปรียบเทียบกับความเร็วของยวดยานแล้วละก็ ได้ประมาณนี้ครับ (ประมาณแบบขำๆนะครับน้อง อย่าซีเรียส)

+ O(1) - เหมือนเครื่อง ว๊าบ หรือ เครื่องย้ายมวลสาร คือ ไกลแค่ไหนไม่เเก่ยว ใช้เวลาในการเดินทางเท่ากันเสมอ
+ O(log n) - อันนี้ก็น่าจะ เครื่องบินโดยสาร 

+ O(n) - อันนี้ ประมาณ รถสูตร 1 หรือ ฟอร์มูล่าวัน ก็แล้วกัน ระยะทางไกลขึ้น ก็ขับนานขึ้น เป็นสัดส่วนตรงๆ

+ O(n log n) - อันนี้เอาเป็น รถยนต์ ทั่วไป คือ แย่กว่า formula 1 แต่ไม่มากมายนัก

+ O(n²) - อันนี้ เป็น ซักระดับ มอร์เตอร์ไซด์ 

+ O(n³) - เอาอันนี้เป็น ซัก จักรยาน 

+ O(2ⁿ) - อันนี้ช้ามากเลยครับ ประมาณว่าคนเดิน

+ O(n!) - อันนี้ช้าโคตรๆ ประมาณ เต่าเดิน ครับ

A Survey of common running times

+ O(1) - Constant Time Algorithm 
เป็น algorithm ที่เร็วที่สุดเท่าที่จะเร็วได้แล้ว คือ ทำงานทุกครั้งใช้เวลาเท่ากันเสมอ ไม่ว่า input จะใหญ่แค่ไหน โครงสร้าง input จะซับซ้อนแค่ไหน algorithm ประเภทนี้ไม่ค่อยมีให้เห็นนัก และแก้ปัญหาได้ไม่กี่อย่าง ยกตัวอย่างเช่น การแทรกค่าใหม่เข้าไปที่จุดท้ายสุดของ linked list (ซึ่งไม่ว่า input จะใหญ่แค่ไหน linked list จะยาวแค่ไหน การ insert โหนดใหม่เข้าไปก็ใช้เวลาเท่าเดิมอยู่ดี)

+ O(log n) - Logarithmic Algorithm 
อันนี้เป็น algorithm ที่เริ่มเป็นความจริงขึ้นมาหน่อย อาจจะเรียกได้ว่าเป็น algorthm ที่เร็วที่สุดในความเป็นจริงแล้ว

+ O(n) - Linear Algorithm 


+ O(n²) - Quadratic Algorithm 

+ O(n³) - Cubic Algorithm 

+ O(2ⁿ) - Polynomial Algorithm

+ O(n!) - Factorial Algorithm class นี้เป็น algorithm ที่ช้าโคตรๆ (555) จนบางทีเค้าไม่อ่านชื่อ class นี้ว่า บิ๊กโอเอ็นแฟคทอเรี่ยล แต่จะอ่านว่า คลาสโอ้โน แทน (สังเกตุ Oh no!) และเป็น algorithm ที่มักจะเอาไว้ใช้ในการแก้ปัญหา combinatorial คือปัญหาที่ต้องการการสร้างทุกๆ combination ของ input ซึ่งอาจจะหาวิธีที่ดีกว่านี้ไม่ได้แล้ว algorithm ใน class นี้ก็ไม่เลวร้ายมากนักถ้าหากว่า ขนาดของ input ยังเล็กอยู่เช่น 5 หรือ 10 (เพราะ 5! หรือ 10! ก็ยังรับได้อยู่) แต่พอขนาดของ input เริ่มเพิ่มจากนี้อีกนิดหน่อย เช่น 15! หรือ 30! นี่เรียกว่าเริ่มรับไม่ได้แล้ว เพราะจำนวนของ combination มันมหาศาลขึ้นเรื่อยๆ

ลองดูสรุปตารางตัวอย่างของเวลาที่ใช้ในการ run ของ algorithm ในแต่ละคลาส 


ดูจากตัวอย่างนี้เป็นการเปรียบเทียบการรันโปรแกรมเพื่อแก้ปัญหาเดียวกัน โดยมี algorithm ที่แตกต่างกัน ดูตัวอย่างตรงที่ n=64 (คือมี input 64 ตัว) ถ้า algorithm ของเราอยู่ใน class O(log n) ละก็ งานชิ้นนี้ก็จะถูกทำเสร็จใน 6 นาโนวินาที แต่ในขณะเดียวกัน ถ้าแก้ปัญหาเดียวกันนี้ จำนวน input เท่ากันนี้ แต่เราใช้ algorithm ที่อยู่ใน O(2ⁿ) งานชิ้นนี้จะทำเสร็จในเวลาถึง 5.85 ศตวรรษ เลยทีเดียว เรียกได้ว่า ถ้าเราวิเคราะห์แล้วว่า algorithm ของเราอยู่ใน class นี้ แล้วต้องประมวลผล input มากว่า 32 ตัวหล่ะก็ ลืมมันไปได้เลย ไม่ต้องไปเขียนโปรแกรมให้เสียเวลา

และขอให้สังเกตุ order of growth คือ ถ้าเราเพิ่ม input ขึ้นเรื่อยๆจะเห็นได้ว่า เวลาที่ใช้ในการประมวลผลของ Class O(log n) เพิ่มขึ้นน้อยมากๆๆเลย แต่ ในขณะที่ algorithm class อื่นๆนั้น เพิ่มเวลาขึ้นมากมาย โดยเฉพาะลองดู class O(n³) นั้นเพิ่มมหาศาลทีเดียว

เห็นประโยชน์ของการวิเคราะห์ความสามารถของ algorithm แล้วใช่มั้ยครับ ถ้ารู้แต่เนิ่นๆ ก็ไม่ต้องเขียนโปรแกรมไปให้เสียเวลา เพราะถ้าอยู่ใน class แย่ๆเราก็ต้องออกแบบ algorithm ใหม่จนว่าจะดีก่อนถึงจะเขียนโปรแกรมครับ