關於排序與搜尋,演算法多到不行,記得自學過程中,花一星期時間實作完十多種排序演算法,有些演算法做起來蠻複雜的,最後該忘的還是忘得差不多。

這裡要講的不是所有 sort 、search 演算法細節,而是 stdlib.h 裡面提供的兩隻寫好的 function - qsort、bsearch。

 

compare function

 

這兩支在調用時,都必須先寫一個 compare function,做為 callback 使用,該 compare function 格式固定為

int compare_function(const void*, const void*);

要轉型的話在該 function 裡強制轉型,否則無法正常調用。以較簡單的 int 型態而言,比較函式長如此

 

int comp_func(const void* a, const void* b)
{
    return (*(int*)a-*(int*)b);
}

 

若要由大排到小的話,只需改成  return (*(int*)b-*(int*)a); 即可。而較複雜的 struct 也可進行自定義的比較,此部份不贅述。同時為了方便起見,變數假設為下

 

int main()
{
    const int Size = 10;
    int arr[10] = {1,5,3,2,4,8,10}; // Cnt=7
    int *pos, n, Cnt=7;
    const int key1=5, key2=9;

    return 0;
}

 

qsort

 

qsort 放在表頭檔 stdlib.h (cstdlib) 裡面,使用前必須強調,它是 un-stable sort,使用時注意。在調用 qsort 時,語法很簡單

 

// qsort
    puts("\n> --------- qsort ---------- \n");
    qsort((void*)arr, Cnt, sizeof(*arr), comp_func);

 

第一個參數即為 arr,第二個參數為元素個數,第三個參數為每個元素多大,第四個參數便為剛剛給的 compare_function。

調用完後,再將 arr 做輸出,發現 arr 裡之元素都已排序完成。

 

bsearch

 

bsearch 放在 stdlib.h (cstdlib) 裡面,為二分搜尋法,調用上與 qsort 大同小異,唯多了一個 key 參數。使用前,必須保證該 array 是有序排序

 

    n   = Cnt;
    pos = bsearch((const void*)&key1, (const void*)arr, n, sizeof(int), comp_func);
    if(pos==NULL) printf("> can't find key %d\n", key1);
    else printf("find key %d at pos %d\n", key1, pos-arr);

    n   = Cnt;
    pos = bsearch((const void*)&key2, (const void*)arr, n, sizeof(int), comp_func);
    if(pos==NULL) printf("> can't find key %d\n", key2);
    else printf("find key %d at pos %d\n", key2, pos-arr);

 

 

於陣列中沒找到該鍵值時,將傳回  NULL,否則將傳回指向該鍵值之指標。

 

* lfind

 

lfind 為線性搜尋法 (也就是從 arr[0] 一直慢慢找到 arr[n-1] ),目前這隻函式沒被放到標準裡面,少數 compiler (VC) 裡有支援,使用前不需進行排序,VC 是放在 search.h 裡。使用方式與 bsearch 似,但 bsearch 第三個參數是放 size of array (陣列大小),雖 lfind 第三個參數也是放 size of array,但必須以 pointer 方式傳入。

 

    n = Cnt;
    pos = (int*)lfind((void*)&key1,arr,&n,sizeof(*arr),comp_func);
    if(pos==NULL) printf("> can't find key %d\n", key1);
    else printf("> find key %d at pos %d\n", key1, pos-arr);

    n = Cnt;
    pos = (int*)lfind((void*)&key2,arr,&n,sizeof(*arr),comp_func);
    if(pos==NULL) printf("> can't find key %d\n", key2);
    else printf("> find key %d at pos %d\n", key2, pos-arr);

 

 

* lsearch

 

lsearch 使用的也為線性搜尋,也是非標準,VC 放在 search.h 裡。使用方式與 lfind 一模一樣,但有個重要的特性不一樣。

當 lfind 找不到元素值時,將會傳回 NULL,而 lsearch 找不到元素值時,會在陣列的最後一筆資料後面,再加上這筆鍵值,

同時返回新增鍵值之指標。故使用 lsearch 時,最好確定 array 至少還有一個元素的空間可以增加,否則易造成寫入錯誤。

 

    pos = (int*)lsearch((void*)&key1,arr,&n,sizeof(*arr),comp_func);
    if(pos==arr+Cnt) printf("> can't find key %d\n", key1);
    else printf("> find key %d at pos %d\n", key1, pos-arr);

    pos = (int*)lsearch((void*)&key2,arr,&n,sizeof(*arr),comp_func);
    if(pos==arr+Cnt) printf("> can't find key %d\n", key2); // add element to the end.
    else printf("> find key %d at pos %d\n", key2, pos-arr);

 

* 效率高?

 

關於 qsort 與 bsearch 比自己寫的效率還高,這論點筆者保留 (其實是持反對,但懶得實測,所以沒證據的情況下才說 "保留" ) 。

目前在 vc 逐步 trace 情況下,release mode 下進不了 qsort 與 bsearch ,而在 debug mode 下其實查得到 qsort 與 bsearch 和其它兩隻之 source code,扣除掉安全性,其實和一般演算法裡學的 qsort、bsearch 沒什麼兩樣。但相對的,這兩支函式必須塞 compare function pointer,在做 callback 動作時,筆者認為動作是較慢的。

但上述筆者提到,那是在 debug mode 情況下,而 visual c++ runtime library,筆者只知道 debug mode 與 release mode 所調用的 library (dll) 並不相同,故這兩隻函式在 release mode 是否會有不同寫法,使得結果更快,目前除了實測 wall time 外,倒不知如何查證。

還有另一點,微軟的 qsort 應還有考慮其他一般 coder 沒考慮到的因素,約半年前在某論壇裡,看到有人直接 copy 微軟的 qsort 出來改,效果比調用的還快 (這筆者也沒留數據與原參考網址)。

另若真在意 sort 與 search 之效率問題,又不想自己造輪子,可考慮直接使用 c++ , algorithm header,裡面已有 sort、find、binary_search 等寫好的 template library。提一下,STL 裡面的 sort ,用的是 IntroSort,比 qsort 稍佳。另 algorithm 裡之這些 library,善用的話確實比 qsort 與 bsearch 快些,理由這裡不贅述 ( 不贅述的理由也是怕筆者說得不夠清楚,怕誤導), 要數據的話可以再自己實測,或 google " Sorting in C++ vs C"  與 "qsort STL sort",可得到不少訊息,找到的數據,大概都圍繞在 STL 裡之 sort快 2~3 倍左右。

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()