嘗試將大量的 IPv4 位址放在記憶體且快速找到

首先, 這是個緊急的需求, 所以沒時間慢慢磨演算法. 第一時間想到的是變成無符號整數放到陣列, 初始化時使用 quick sort 排序, 搜尋使用 binary search. 果真是太嫩了, 實作出來之後, 效能非常普通.

陣列搜尋

好吧! 只好拿出記憶用起雜湊表, 雜湊函數十分簡單. 第一版: 取高低 16 bits 進行 XOR 取得 bucket 位置, 再建立單向鍊結串列. 第二版為了有效縮短串列, 使用 24 bits 進行 XOR.

第二版

測試數據為從某台 TLD NS 的某一段時間所有來訪的 IPv4 (524,860筆), 搜尋測試為 100,000 次(命中與不命中次數為 1:1, 唯一缺點就是沒有每次跑雜湊函式, 有空再來重作一次測試). 測試結果如下.

測試結果

結論是適合的演算法比較重要, 繼續尋找更快的演算法.

題外話: printf 真是超級耗時的, 可以從不輸出資料的測試結果看出.

向真正的 Hacker 致敬

準備考試真的是太忙碌, 一直沒有注意新聞消息. 相信學過 C 語言的同好們應該都知道 Dennis MacAlistair Ritchie . 在 C 及 UNIX 上的貢獻. 也影響到資訊科技的發展. 很可惜在 2011/10/12 世界失去了這位真正的 Hacker. 


向您至上最高的敬意!  R.I.P.