初試啼聲 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吧。

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;