1. 首頁
  2. 問答
  3. 在C中有效實現布隆過濾器？

在C中有效實現布隆過濾器？

2012-06-13 103 views
11

這個問題以前有人問過，但當時沒有答案，所以我決定再次提問。在C中有效實現布隆過濾器？

我需要在C（而不是C++）中有效實現布隆過濾器。如果沒有這樣的東西，我不介意實施一個，如果給予一些很好的參考，以便它不佔用我太多的時間。

我想使用這個數據結構進行插入和測試的比例（1：20k），所以主要是測試密集型的。要測試的數據是64位整數。

來源

2012-06-13 Aman Deep Gautam

+0

這是概率性的。如果您想要確切答案，請使用聯合查找不相交集。在topcoder上搜索這個，應該有一些教程。 – nhahtdh

+1

如果你正在編寫C語言，這不是你需要一個通用庫的東西。它應該少於100行代碼，與集成第三方庫相比，應該花更少的時間來編寫代碼。只需閱讀您最喜愛的維基百科或其他類似算法的描述。 –

+1

@R編寫它會花費更少的時間，但我知道但是高效地編寫它以使其能夠很好地擴展是一個問題。我必須按照10^7的順序測試數據的成員資格，並且使這個查詢比對equi連接的結果進行count（*）查詢更快。在我的實現中，我甚至不能丟失一個毫秒 –

回答

1

鉻具有一個在C++

github link

來源

2012-06-13 02:40:15 eqzx

+0

男人，他們真的需要包括鮑勃詹金斯的版權使用他（公有領域）哈希函數... – tbert

4

不要做過多的自我宣傳，但我已經寫了一個插件，可以過濾掉重複的文本行Geany editor/IDE，它採用布隆過濾器。

執行是在C中，你可以找到它right here on GitHub。這是GPL v3，所以根據您的確切需求，您可能會或可能無法使用它。

對我實施的一些注意事項：

  • 它的設計，以過濾字符串，沒有抽象的密鑰類型。這意味着您將不得不修改密鑰處理以適應您的需求。
  • 它支持非特徵語義，如果您想要，您可以實際使用它進行完全非概率存在測試（請參閱bloom_filter_new()使用的BloomContains回調函數指針）。只需通過NULL即可獲得「純粹」過濾器。
  • 字符串散列函數是Austin Appleby的MurmurHash2。我評估了更新的MurmurHash3，但版本2更容易處理。
  • 爲了適應Geany生態系統，此代碼始終使用GLib類型。

它沒有經過嚴格的性能調整，但應該沒問題。當然，我會感謝您在測試後可能會有的任何反饋！

來源

2012-06-13 06:59:12 unwind

+0

嘿，謝謝它可以非常有幫助的確。我會試一試並告訴你。 –

+0

你能否建議可以使用除glib之外的其他一些庫來實現高性能 –

+0

你能否提出使用glib庫的任何特定動機，除此之外，它使得代碼可移植。 –

相關問題

 相關問題