chakrit

แลปคราวนี้เป็นเรื่องของการเรียงข้อมูลเหมือนครั้งที่แล้ว แต่ว่าคราวนี้ใช้วิธีการที่ค่อนข้างเร็วกว่า อันได้แก่ Radix Sort, Bucket Sort, Counting Sort และ Merge Sort

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

แต่จริงๆ แล้ววิธีการแหวกแนวพวกนี้มันเข้าใจง่ายกว่าวิธีที่ผ่านๆ มามาก และหลายๆ วิธีก็เขียนง่ายกว่าด้วย ตัวอย่างเช่น Heap Sort กับ Counting Sort ความซับซ้อนในการ Implement นี่ต่างกันลิบลับ ยิ่งถ้ารวมเวลาในการ Debug ไปด้วยแล้วนี่ยิ่งเยอะเลย แต่มันก็มีข้อเสียอย่างที่บอกนั่นแหล่ะนะ คือมันค่อนข้างเฉพาะเจาะจงกับลักษณะของข้อมูล ก็เลยเค้นประสิทธิภาพออกมาได้มากกว่าวิธีที่ไม่เฉพาะเจาะจง

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

โปรแกรมที่ทำงานเร็วที่สุดนี่ เขาวัดกันตรงนี้แหล่ะ ไม่ใช่ว่าแค่เขียน Quick Sort เหมือนกันแล้วจะถือว่าเร็วเท่ากัน เขาวัดกันที่รายละเอียด ความ “เฉพาะทาง” และการจัดการกับ “ข้อจำกัด” ของ Algorithm ที่เขียนมามากกว่า ตัวอย่างเช่นโปรแกรม Defragment ที่เรียงข้อมูลบน Harddisk จากวันเวลาที่ใช้งานล่าสุด ไฟล์ไหนใช้งานบ่อย ก็ต้องเรียงเอาไว้ข้างหน้า ลองคิดดูว่าจะทำยังไงให้ได้ประสิทธิภาพสูงสุด Access Time สูงสุดและมี File Fragmentation น้อยที่สุด เรื่องเล็กๆ น้อยๆ พวกนี้แหล่ะที่ทำเงินให้กับโปรแกรม Diskeeper ที่ใช้อยู่ได้อย่างมหาศาล

กรุณาอย่า Copy ส่ง ไม่ว่าด้วยกรณีใดๆ ก็ตาม - Download