TAG

首都機能移轉 (2) 歌詞 (2) 靠北文 (40) 戲言 (30) 糟糕 (7) ACG (23) Assembly (2) Boost (2) C (31) C++ (69) CMake (4) CSIE (67) Debian (34) Design_Pattern (2) Django (1) Eclipse (1) en_US (13) FFmpeg (3) FoolproofProject (26) FreeBSD (2) Git (4) GNU_Linux (65) IDE (5) Java (11) JavaScript (19) KDE (15) Khopper (16) KomiX (3) Kubuntu (18) Life (1) Lighttpd (2) Mac_OS_X (2) Opera (1) PHP (2) PicKing (2) Programing (21) Prolog (1) Python (7) QSnapshot (2) Qt (30) Qt_Jambi (1) Regular_Expression (1) Shell_Script (7) Talk (98) VirtualBox (7) Visual_Studio (13) Windows (18) zh_TW (36)

2007年7月29日 星期日

初試啼聲 on Ruby

出於好奇,我想試試某些號稱是「真正的高階語言」的直譯式語言,初步選定的目標為Perl, Python, Ruby;但是Perl的寫作風格過於自由,Python又太死了,而且我不喜歡它的物件傳遞方式,所以最後用Ruby試著寫了一個質數表。
而開發速度的確是令我相當驚訝,即使這只是一個很簡單的程序。
#!/usr/bin/env ruby

SIZE = 100
prime = Array.new( SIZE, true )
prime[0, 1] = false, false
i = 2
while i ** 2 < prime.length
 if prime[i]
  j = i
  while j * i < prime.length
    if prime[j*i]
     prime[j*i] = false
    end
   j += 1
  end
 end
 i += 1
end

i = 0
prime.length.times do
 if prime[i]
  puts i
 end
 i += 1
end
雖然在這個例子裡把Array初始化,但是其實只要讓直譯器知道該變數是屬於Array這個class就夠了,不論是大小或是型態有沒有宣告都無所謂;因為Ruby[?]是泛型語言,變數並沒有真正的固定型態,而陣列裡也不需要放置相同物件,也可以在裡面放其他的多維陣列,不需對齊。
它的動態性也值得一提,因為你可以在class定義完成後再增減它的成員[?]
但是它的執行速度也同樣地令我吃驚[?];諸君可以試著把上例的SIZE改成20000000,再跑跑看,我相信跑出來的時間會令你印象深刻。
同樣的演算法,用C或是C++來寫大約只要2.3~2.5秒左右,但是Ruby的情況,它可以用到兩分多鐘。
也許是因為直譯器經常要late binding吧,就像是C++的virtual function用多了的後果一樣。
總之,因為以上的結果,在需要複雜計算的時候Ruby並不算是個好選擇....也許哪天我會去試Python吧。

2007年7月22日 星期日

Sorting

這篇的主題主要是針對多筆資料的同時排序。
這樣說也許不太確切吧,比方說,現在有五十個人分別從1編到50號,並給每個人的身長,求以高矮順序排列的座號。
這時候該怎麼寫?
由於C的qsort和C++的sort都只能排一個一維陣列,像這種排序的同時要保留其他資訊的位置時[?],也許有人的做法是建立兩個陣列,一個放身高,另一個放座號,然後自己寫一個sorting function。
不過這樣好像有點麻煩,因為quick sort實在是很煩,bubble有夠慢,而且又有現成的函式可用,像這種問題要怎麼解決?
其實用簡單的資料結構就可以漂亮地解決。
以上述問題為例:
// C version:
typedef struct Prop
{
 double height;
 unsigned int index;
}Prop;
typedef struct Array
{
 Prop *content;
 unsigned int size;
}Array;
// C++ version:
struct Prop
{
 double height;
 unsigned int index;
};
struct Array
{
 Prop *content;
 unsigned int size;
};
先建立一個結構,內容是每個人的資料,也就是double的height[?]和unsigned int的index[?]。然後再建立一個Array的結構把它包起來。
我為什麼不直接就用Prop這個結構去建立陣列呢?其實只是我個人的喜好而已,因為與其另外再宣告一個變數放陣列目前長度,不如直接用結構把它跟陣列本身綁起來,對我來說比較好懂。
使用動態陣列存也只是我個人的喜好,各位高興也可以換成固定陣列。
由於是動態陣列,所以要先建立出陣列空間[?]
Array people;
// C version:
people.content = (Prop*)malloc( sizeof( Prop ) * people.size );
// C++ version:
people.content = new Prop[people.size];
到了這步,我假設你已把資料全部正確的放進陣列裡了。
好了,問題來了,qsort和sort都不認得這個結構的大小判斷,compiler會很直接的發給你一張好人卡,那接下來要怎麼辦?
注意到,sort其實可以放第三個argument,也就是compare function的address,而qsort則是一定要放入compare function。要動手腳的地方就在這裡。
// C version:
int compare( const void *a, const void *b )
{
 return ( ( Prop* )a )->height > ( ( Prop* )b )->height;
}
qsort( people.content, people.size, sizeof( Prop ), compare );
// C++ version:
bool compare( Prop a, Prop b )
{
 return a.height < b.height;
}
sort( people.content, people.content + people.size, compare );
也就是說,其實可以藉由自訂compare function的方式來自訂要用哪個元素排序。
注意,C的qsort和C++的sort排序的條件不同,qsort是當compare為true時做swap,sort則是當compare為false時做swap,當發現sort出來的結果怪怪的時候,請檢查compare function。
最後請記得,有多少個malloc就要有多少個free,有多少個new就要有多少個delete,有借有還,再借不難唄:P
// C version:
free( ( void* )people.content );
// C++ version:
delete[] people.content;