Cholwich’s blog

ไม่ได้เขียนอะไรใหม่ๆ ที่นี่มาเกือบครึ่งปี เพราะงานยุ่ง แล้วก็ยังเสพติด twitter และ facebook งอมแงมอีกต่างหาก วันนี้มีเวลาว่าง (จริงๆ ก็ไม่ว่างหรอก แต่ขี้เกียจทำงานที่ควรจะทำ) เลยเอา Go Programming Language ที่พัฒนาโดย Google มาลองเล่นดู เนื่องจากผมใช้ Mac OS X ซึ่งเป็นแพลตฟอร์มที่สนับสนุนอยู่แล้ว ก็เลยติดตั้งไม่ยาก แค่มี XCode อยู่ แล้วลง mercurial เพิ่ม ก็สามารถโหลดซอร์สโค้ดคอมไพเลอร์ของ Go มาคอมไพล์เองได้เลย ใช้เวลาคอมไพล์ตัวคอมไพเลอร์สั้นมาก แป๊บเดียวเสร็จ ประทับใจพอสมควร

จากนั้นก็เลยลองเขียนโปรแกรมแบบมั่วๆ (เพราะยังงงกับ syntax อยู่) เพื่อแก้ปัญหา N-Queens แบบง่ายๆ (ใช้ backtracking search ด้วย recursive ดื้อๆ เอานี่แหละ) โดยใช้ Go:

package main
 
import "fmt"
 
var N int = 10
 
func nqueens(board []int, filled int) int {
	var attack bool = false;
	if filled == N-1 {
		for i:=0; i<N; i++ {
			fmt.Printf("%d\t", board[i])
		}
		fmt.Printf("\n");
		return 1
	}
	filled += 1;
	for i:=0; i<N; i++ {
		board[filled] = i;
		attack = false;
		for j:=0; j<filled; j++ {
			dy := board[j]-board[filled];
			dx := j - filled;
			if (board[j] == board[filled]) || 
			(dy/dx == 1 || dy/dx == -1) && (dy%dx == 0) {
				attack = true;
				break
			}
		}		
		if !attack {
			nqueens(board, filled)
		}	
	}
	return 0
}
 
func main() {
	var board []int = make([]int, N);
	nqueens(board, -1);
}

ด้วยความอยากรู้ ก็เลยลองเอาโปรแกรมนี้เอามาแปลงเป็นภาษา C แบบตรงๆ บรรทัดต่อบรรทัด

#include<stdio.h>
#include<stdlib.h>
 
const int N=10;
 
int nqueens(int *board, int filled) {
	int i,j,attack,dy,dx;
	if (filled == N-1) {
		for(i=0; i<N; i++)
			printf("%d\t", board[i]);
		printf("\n");
		return 1;
	}
	filled++;
	for(i=0; i<N; i++) {
		board[filled] = i;
		attack = 0;
		for(j=0; j<filled; j++) {
			dy = board[j]-board[filled];
			dx = j - filled;
			if ((board[j] == board[filled]) ||
			((dy/dx == 1 || dy/dx == -1) && (dy%dx == 0))){
				attack = 1;
				break;
			}
		}
		if (!attack)
			nqueens(board, filled);
	}
	return 0;
}
 
main() {
	int *board = (int *)malloc(sizeof(int)*N);
	nqueens(board, -1);
}

เสร็จแล้วก็ลองเขียน Python อีกโปรแกรมหนึ่ง

def nqueens(board, filled):
	global N
	if filled == N-1:
		for i in board:
			print "%d\t" % board[i],
		print
		return True
	filled+=1
	for i in xrange(0, N):
		board[filled] = i
		attack = False
		for j in xrange(0, filled):
			dy = board[j]-board[filled]
			dx = j - filled
			if board[j] == board[filled] or ((dy/dx == 1 or dy/dx == -1) and dy%dx==0):
				attack = True
				break
		if not attack:
			nqueens(board, filled)
	return 0
N=10
board = [0]*N
nqueens(board, -1)

ทดลองรัน (ด้วย N=10) แล้วจับเวลาง่ายๆ ด้วย time ก็จะได้ผลเป็น

ประสิทธิภาพแบบคร่าวๆ ก็ถือว่าใช้ได้ทีเดียว ไม่ได้แย่กว่า C นัก แต่ไม่รู้ว่าผมชินกับภาษา C มากเกินไปหรือเปล่า ทำให้ผมรู้สึกแปลกๆ งงๆ กับ syntax ของ Go มันดูไม่ค่อยสวยงามยังไงไม่รู้ บอกไม่ถูก เหมือนแค่เอา C มาตัดบางส่วนออก เพราะกลัวจะพิมพ์เยอะเกินไป มันเลยดูขัดๆ อีกอย่าง Go ก็ไม่ได้เขียนสั้นๆ ง่ายๆ ได้เหมือน Python ผมว่าโครงสร้าง syntax ของ C กับ Python สวยงามกว่าเยอะ แต่ผมก็ยังไม่ลอง concurrent programming ที่เป็นจุดขายของ Go เหมือนกัน เอาไว้หนีงานมาลองใหม่คราวหน้าละกัน

programming C, go, programming, python

ในไลบรารีมาตรฐานของภาษาซี มีฟังก์ชันสำหรับจัดการข้อมูลที่สำคัญอยู่ 2 ฟังก์ชัน คือ bsearch สำหรับการค้นหาข้อมูลแบบ binary search และ qsort สำหรับเรียงลำดับข้อมูลโดยใช้อัลกอริทึม quick sort โดยปกตินักศึกษาส่วนใหญ่มักจะไม่ใช้ เพราะมันดูเหมือนจะยุ่งยากซับซ้อน โดยเฉพาะเรื่องเกี่ยวกับ pointer วันนี้ต้องเขียนโปรแกรมเพื่อเรียงลำดับสายอักขระ เลยเอามาเขียนอธิบายวิธีการใช้ไว้หน่อย เผื่อจะเป็นประโยชน์ต่อตัวเอง และคนที่ผ่านมาเห็น

void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))

จาก function prototype จะเห็นว่าฟังก์ชันนี้ต้องการ argument 4 ตัว คือ

1. base เป็น pointer ที่ชี้ไปยังอะเรย์ที่ใช้เก็บข้อมูลทั้งหมด
2. nmemb ใช้ระบุจำนวนสมาชิกของอะเรย์ที่ต้องการเรียงลำดับ
3. size กำหนดขนาดของข้อมูลแต่ละชุด ซึ่งจำเป็นต้องใช้เวลาย้ายข้อมูลสลับตำแหน่งกัน
4. compar เป็น pointer ที่ชี้ไปยังฟังก์ชัน เพื่อเปรียบเทียบสมาชิกแต่ละตัวในอะเรย์ ฟังก์ชันนี้ควรจะให้ค่าน้อยกว่าศูนย์ เท่ากับศูนย์ และมากกว่าศูนย์ เช่นเดียวกับฟังก์ชัน strcmp

ตัวอย่าง ผมต้องการเรียงลำดับสตริง ซึ่งในภาษาซีจะใช้ char * ดังนั้นผมจึงสร้างตัวแปรแบบ char ** เพื่อเป็นอะเรย์สำหรับเก็บ pointer ที่ชี้ไปยังสตริงแต่ละตัว ส่วน nmemb ก็คือจำนวนสมาชิกของอะเรย์ กับ size ก็คือ sizeof(char) หาได้ไม่ยาก ปัญหาหลักอยู่ที่ฟังก์ชันสำหรับเปรียบเทียบข้อมูล ซึ่งจะเห็นว่าเรามีฟังก์ชัน strcmp สำหรับเปรียบเทียบสตริงอยู่แล้ว เพียงแต่ prototype อาจจะไม่เหมือนกัน เลยต้องทำฟังก์ชันขึ้นมาห่อไว้หน่อย

int compare(const void *a, const void *b) {
    const char **pa = (const char **)(a);
    const char **pb = (const char **)(b);
    return strcmp((*pa), (*pb));
}

อ้อ เวลาฟังก์ชัน qsort เรียก compar มาทำงาน จะเรียกโดยส่ง pointer ที่ชี้ไปยังสมาชิก 2 ตัวในอะเรย์ไปให้ ฉะนั้นจึงต้องมา cast ให้เป็น char ** ก่อน แล้วถึงจะไปเรียกใช้ strcmp ได้ ส่วนการเรียกฟังก์ชัน qsort ก็แค่

qsort(a, n, sizeof(char *), compare);

สุดท้ายที่อยากฝากไว้ก็คือ “don’t reinvent the wheel” เราควรจะใช้สิ่งที่มีอยู่แล้วให้เป็นประโยชน์ให้มากที่สุด โดยเฉพาะอย่างยิ่งฟังก์ชันมาตรฐานต่างๆ เพราะฟังก์ชันเหล่านี้ได้รับการพัฒนามายาวนาน ผ่านร้อนผ่านหนาวมาเยอะ น่าจะทำงานได้ดีกว่าการเขียนฟังก์ชันขึ้นมาใช้งานเอง แต่ทั้งนี้ไม่ได้บอกว่าไม่ควรทำเองนะ เพียงแต่พยายามปรับใช้สิ่งต่างๆ ที่มีอยู่ให้ดี เพื่อจะได้มีเวลาไปทำให้สิ่งใหม่ๆ

อ้างอิง: man qsort

programming C, programming, qsort