如何高效匹配大型集合

我有大量的foo類型的對象集合。 foo類型的每個對象都有100個屬性（所有字符串）加上一個id。 bar類型的對象也具有這100個屬性。如何高效匹配大型集合

我想從集合中找到類型爲foo的匹配對象，其中所有這些屬性都與bar匹配。

除了暴力方法，有沒有一個優雅的算法，我們可以計算foo對象的簽名一次，併爲bar對象執行相同的操作並更有效地匹配？

foo s是在成千上萬和bar是在百萬。

來源

2011-10-25 Barka

[散列]（http://en.wikipedia.org/wiki/Hash_function）？ – brc

什麼是上下文？ –

達斯維達在那裏有一個點......我從來沒有想過我會站在黑暗的一面！

我去了什麼，我認爲是行業的最佳工具：

嵌入式數據庫：Google's LevelDB - 它比大多數數據庫解決方案在那裏快。
散列函數：Google's CityHash - 它是快速它提供了優秀的哈希！
JSON Serialization

嵌入式數據庫

使用嵌入式數據庫的目標是，你會得到的性能將優於大多數的數據庫解決方案，你很可能會遇到。我們可以談論LevelDB有多快，但plenty of other people have already talked about it quite a bit，所以我不會浪費時間。嵌入式數據庫允許您存儲鍵/值對，並快速在數據庫中找到它們。

哈希函數

一個好的哈希函數將會很快，它會提供非重複散列的良好分佈。 CityHash速度非常快，並且發行速度非常快，但同樣如此：我不會浪費時間，因爲lot of other people have already talked about the performance of CityHash。您可以使用散列函數來散列對象，然後使用唯一鍵在數據庫中查找它們。

JSON序列化

JSON序列化是什麼，我上面顯示的對立面：它是非常緩慢的，它會降低任何性能增益你CityHash實現，但它給你一個很簡單的方法來湊整個對象。您將對象序列化爲JSON字符串，然後使用CityHash對字符串進行散列。儘管事實上你已經失去了CityHash的性能收益，因爲你花了很多時間將對象序列化爲JSON，但你仍然可以獲得具有非常好的散列函數的好處。

的結論

您可以存儲數十億條記錄的性LevelDB，你將能夠爲其提供哈希快速檢索你要找的只是精確值。
爲了生成密鑰，可以使用JSON序列化和CityHash對JSON字符串進行哈希處理。
使用鍵找到匹配的對象！

享受！

來源

2011-10-25 05:22:50 Kiril

如果你有所有匹配的屬性。這意味着它們實際上是相同的對象。那是對的嗎？

在任何情況下，您都希望使用具有良好散列算法的Map/Dictionary/Table來查找匹配對象。

無論您使用哪種語言，您都應該重寫gethashcode並等於實現它的方法。

如果你有一個很好的散列算法，你的訪問時間將是O（1）。否則它可以達到O（n）。

根據您的內存限制，您想要在地圖中存儲foos，存儲酒吧可能需要大量空間，您可能沒有。

來源

2011-10-25 03:46:48 DarthVader

數百萬條目的非平凡大小..我更希望他們被存儲在數據庫中。我可能會創建一個我索引列並使用現有對象的散列填充它。這會導致O（logn）運行時查找，但具有實際的內存使用情況。 – bdares

這就是我所說的，他/她會想要在Dictionary中存儲數千個。 – DarthVader

地圖，字典和表格是可以在用戶應用程序（通常在RAM）或其他地方實現的數據結構，但是我想指出，使用DBMS的實現來說明大尺寸是最有意義的。 – bdares

哈希是非常好的，簡單的實現。但我想建議你該算法：

地圖的100個字符串屬性，以一個大的字符串（例如，使用固定長度爲每個屬性串聯）應此對象的唯一標識。所以我們第一組有1000個字符串，第二組有1毫升字符串。
如果第一組包含它，則問題將減少以找出第二組中的每個字符串。
製作trie第一組數據結構
檢查trie中字符串S是否爲O（| S |）的共同性。 | S | - 長度爲S.

所以...算法的共同性是-o（Sum（| Ai |）+ Sum（| Bi |））= O（max（Sum（| Ai |），Sum |畢|））= O（總和（|畢|））爲您的問題艾 - 對於第一套串唯一的ID，碧 - 串唯一的ID爲第二組

UPDATE：。 特里需要O（ Sum（| Ai |）* | Alphabet |）空間最差

來源

2011-10-25 06:24:15

嘗試不太友善。他可以有一個非常大的特洛伊木馬，可能會消耗大量的內存，哈希碼，你代表一個單一的數字實體。 – DarthVader

@DarthVader，一般 - 是的。但有時候我們有小字母或小首字母，但很多查詢，比如「如果字符串包含在第一組」。並且字符串S的搜索共謀是**明確** O（| S |）。 –

如何高效匹配大型集合

回答

相關問題