ทบทวน 2 : สถิติ 10 อันดับสูงสุด

    เมื่อประมาณปี 1991 ปีที่นายซัดดัมบุกคูเวต ปีนั้นผมเปิด BBS ที่ชื่อว่า Zovixjaque ถ้าใครไม่รู้จัก BBS ก็ให้คิดว่ามันเป็น Server ที่ให้บริการข่าวสาร และ file สำหรับ download เราต้องต่อ Modem เข้าไปเล่น ต้อง login และ ใส่ password ผมเพิ่งได้รับ Modem ความเร็วสูงสุดในยุคนั้นคือ 2400 bps เอามาหัดเล่น BBS พอผ่านไปได้หนึ่งอาทิตย์ชักจะมันเลยเปิด BBS เองซะเลย เน้นเนื้อหาทางด้านการเขียนโปรแกรม ตั้งชื่อว่า Zovixjaque ทำไมชื่อถึงประหลาดอย่างนี้ ที่จริงก็ไม่มีอะไรมาก ผมเอาตัวที่ราคาแพงที่สุดในเกมส์ scrabble ซึ่งเป็นตัวที่มีการใช้น้อยที่สุด หายากที่สุด 5 ตัวคือ z x j v q ผสมกับสระ a e i o u ซึ่งเป็นตัวที่หาง่ายมากในคำภาษาอังกฤษ จับมารวมกันให้มันอ่านเป็นคำได้ ความหมายโดยนัยก็คือ BBS แห่งนี้มีทั้งของหายากที่สุด และหาง่ายที่สุด นั่นก็คือมีครบทุกอย่างนั่นเอง

    เมื่อเปิดมาได้ระยะหนึ่ง ผมก็อยากเก็บสถิติว่า ใครนะที่เข้ามาบ่อยที่สุด หรือใครเข้ามา download มากที่สุด หรือสถิติอะไรก็แล้วแต่ 10 อันดับแรก มีโปรแกรมที่เป็น Third Party ทำสามารถทำสถิติแบบนี้ได้เป็นของฝรั่ง วิธีการทำงานก็คล้ายกับ CGI สมัยนี้ครับ คือมันต้อง shell ออกจากโปรแกรม BBS แล้วมา run โปรแกรมทำสถิติ ซึ่งในโปรแกรมนี้มันจะไปอ่านข้อมูลจาก file ที่เก็บ data ต่างๆ เอามาประมวลผล จนได้คำตอบ แล้วก็ render ออกมาเป็น ANSI page ซึ่งแนวคิดไม่หนี กับ web page เพียงแค่ไม่มีรูปภาพ Graphic เท่านั้น

    ในสมัยนั้น memory จำกัดมากครับ ถึเครื่องงผมจะมี memory ถึง 4MB แต่โปรแกรม BBS เกือบทุกตัวทำงานใน Real Mode ซึ่งทำให้มองเห็น Memory เพียง 640 kb โดยปกติแล้วเมื่อโปรแกรม BBS shell ตัวเองออกมา มันจะเหลือ memory เพียงประมาณ 50kb เท่านั้น ซึ่งไม่ค่อยพอใช้งานนัก

    โปรแกรมฝรั่งที่ว่า จึงใช้หลักการที่เรียกว่า External Sort ซึ่งใช้ Harddisk เป็น Buffer แทน Memory ผลก็คือว่าสามารถทำลายกำแพง 50kb ได้ แต่จะได้แค่ไหนขึ้นอยู่กับขนาดของ harddisk ที่มีครับ โดยปกติแล้ว มันต้องใช้เนื้อที่เป็นสองเท่าครับ ทำไมเป็นสองเท่า ผมคงไม่พูด ให้ลองไปอ่าน Alogirithm ที่ชื่อว่า Tape Sort เอาเองครับ จุดอ่อนของวิธีนี้คืออะไรรู้ไหมครับ ใช่ครับช้าบรม BBS ขนาดปานกลาง ผมเคยเจอแล้วครับ มันใช้เวลากว่าครึ่งชั่วโมงถึงแสดงผลลัพธ์ได้

    มาวันหนึ่งเด็กฝรั่งคนหนึ่งที่เล่น BBS กลุ่มเดียวกัน ถ้าจำไม่ผิด แกเป็นลูกฑูตสวิสเซอแลนด์ แกทำสิ่งที่น่าทึ่งครับ คือแกเขียนโปรแกรมแบบเดียวกันครับ ใช้ Turbo Pascal เขียน สามารถทำความเร็วให้เหลือเพียง 1 นาที เท่านั้น ผมวิเคราะห์ดูแล้วว่า แกดึงเอา data ทุกตัวลง memory ก่อน แล้วเอา Quick Sort ซึ่งเป็น Routine จากโปรแกรมตัวอย่างที่ Borland ให้ไว้ใน Turbo Pascal มาใช้ ซึ่ง Quick Sort เป็นที่ทราบกันว่าความเร็วสูงมาก แต่คุณคงรู้นะครับว่าจุดอ่อนของวิธีนี้คือ มันไม่สามารถทำลายกำแพง 50 kbได้

    ถ้าผมบอกคุณว่า ผมมีวิธีที่ดีกว่า ใช้เวลาเพียง 12 วินาที และยังทำลายกำแพง 50kb ได้ ไม่เพียงแค่ทำลายได้แบบโปรแกรมฝรั่งนะครับ วิธีของผมไม่กิน เนื้อที่ของ harddisk เลย คุณจะเชื่อรีเปล่า ผมทำได้อย่างไร เรามาลองดูกัน

    ผมเห็นว่าความต้องการนั้น เพียงแค่ต้องการ 10 ลำดับสูงสุด ไม่ใช่การเรียงทุกลำดับ ดังนั้นทำไมผมต้องหาที่เก็บสำหรับทุก record ด้วย ผมเก็บแค่ 10 ตำแหน่งก็พอ เมื่อเมื่อไหร่ที่มันเกิน 10 ผมก็ตัดตัวที่ 11 ทิ้งไป เท่านี้ก็ไม่เปลืองที่แล้วครับ

    ส่วนเวลาที่จะมีการแทรก recordใน array ผมต้องเลื่อนทุกตัวไปอีกตำแหน่ง ซึ่งผมว่ามันช้าไปหน่อย ผมเลยเปลี่ยนให้มันเป็น linked list เวลาแทรกอะไรมันก็จะง่าย เท่านี้แหละครับมันก็เร็วได้ จะเห็นได้ว่าวิธีที่ทำให้เร็วกว่าหรือดีกว่านั้น ไม่จำเป็นต้องเป็นวิธีที่ซับซ้อนกว่าเสมอไป จากตัวอย่างนี้จะเห็นได้ว่า วิธีการทำ External Sort นั้นเป็นวิธีการที่ยุ่งยากมาก คนเขียนได้นี่ต้องเก่งมากครับ  แต่วิธีของเขาเป็นวิธีที่ไม่เหมาะสมเอาเสียเลย แต่วิธีที่ผมทำให้ดีนั้นเรียบง่ายกว่ามาก แถมยังได้ผลลัพธ์ที่ดีกว่าครับ

topten.cs

using System;
class Node
{
	public int num;
	public Node next;
	public Node prev;
}
class Hello
{ 	public static void Main()
	{
		int i, num;
		Node start, node, walk, last;
		Random rand = new Random();
		
		start  = last = null;
		for (i=0; i<10000000; i++) {
			num = rand.Next();
			if (i>=10 && last.num >= num)
			{
				continue;
			}
			node = new Node();
			node.num = num;

			if (i==0) {
				start = last = node;
				continue;
			}
			walk = start;
			
			while (walk != null) {
				if (node.num > walk.num) {
					node.next = walk;
					node.prev = walk.prev;
					if (walk.prev != null)
					{
						walk.prev.next = node;
					}
					if (walk == start)
					{
						start = node;
					}
					
					walk.prev = node;
					break; 				
				}
				walk = walk.next;
			}
			if (i<10 && walk == null) {
				last.next = node;
				node.prev = last;
				last = node;
			} 
			
			if (i>=10 && walk != null)
			{
				last = last.prev;
				last.next = null;
			}
		}
		walk = start;
		while (walk != null) {
			Console.WriteLine(walk.num);
			walk = walk.next;
		}
	}
}

    จากโปรแกรมนี้ ผมใช้ class มาเก็บโครงสร้างของ Node ซึ่งไม่เหมือนกับในหนังสือ Algorithm ทั่วไปที่ใช้ struct จะให้เห็นนะครับว่าในภาษายุคใหม่บางภาษาที่ไม่มี struct เราใช้ class แทนได้ โดยเฉพาะอย่างยิ่งครับกับ Visual Basic มีคนกลุ่มใหญ่ๆ เลยที่คิดว่าภาษา VB นั้นไม่สมบูรณ์เพราะไม่รองรับการทำ Dynamic Allocation ทำให้ไม่สร้างทำ linked list หรือ tree ได้ ซึ่งวันนี้ผมทำให้ดูว่า ที่จริงแล้วทำได้อย่างสบายครับ