我必須編寫一個比較10'000'000 +實體的程序。實體在數據庫/ csv文件中基本上是平坦的行。比較10萬個實體
比較算法是相當靈活的，它是基於在最終用戶輸入規則的規則引擎和各實體對每一個其他實體相匹配。
我在考慮如何將此任務分解爲更小的工作負載，但我還沒有找到任何東西。由於規則是由最終用戶預先排序輸入的，DataSet似乎是不可能的。
我現在要做的是將整個DataSet放入內存並處理每個項目。但這不是非常高效，需要約。 20 GB的內存（壓縮）。
您知道我如何分割工作量或縮小尺寸嗎？
感謝
如果您的規則處於抽象的最高級別（例如任何未知比較函數），則無法實現您的目標。 10^14比較操作將運行多年。
如果規則不完全總的來說，我看到3個解決方案，優化不同的情況：
如果比較傳遞的，你可以計算哈希（有人已經建議本），做到這一點。哈希值也可能很複雜，不僅僅是你的規則=）。找到很好的散列函數，它可能在很多情況下都有幫助。
如果實體可排序，對它們進行排序。爲此，我建議不要在原地排序，而是建立一個項目的索引（或ID）數組。如果您的比較可以轉換爲SQL（因爲我的理解您的數據在數據庫中），您可以更有效地在DBMS端執行此操作並讀取已排序的索引（例如3,1,2表示ID = 3的項是最低的，ID = 1在中間，ID = 2是最大的）。那麼你只需要比較相鄰的元素。
如果事情值得，我會嘗試使用一些啓發式排序或哈希。我的意思是我會創建散列，它不一定唯一地標識相同的元素，但可以將您的數據集拆分爲絕對沒有一對相同元素的組。然後所有相等的對將在內部組中，並且您可以逐個閱讀組，並且在不是10 000 000的組中進行手動複雜函數計算，但是例如100個元素。另一個子方法是用相同的目的進行啓發式排序，以保證相同的元素不在數據集的不同結尾。之後，您可以逐個讀取元素，並與之前的1000個元素進行比較（已經讀取並保存在內存中）。每次新100時，我都會記憶1100個元素，並保留100個最舊的元素。這將優化您的數據庫讀取。如果您的規則包含像（Attribute1 = Value1）AND（...）這樣的規則或像（Attribute1 < Value2）AND（...）或任何其他簡單規則的規則，則此方法的其他實現也可能是可能的。然後，您可以按照該標準首先進行聚類，然後比較創建的聚類中的項目。
順便說一句，如果你的規則認爲所有10 000 000個元素都相等怎麼辦？你想得到10^14的結果對嗎？這種情況證明，在一般情況下你不能解決這個任務。嘗試做一些限制和假設。
我會創建從每個實體的哈希碼。您可能必須從散列生成中排除該id，然後測試equals。如果你有散列，你可以按字母順序排列所有的散列碼。讓所有實體排列順序意味着檢查雙打非常容易。
當然，但RuleSet可以包含複雜的規則。你不能只比較行。 （例如，您想對字符串進行標準化，計算字符串距離等） – senic 2013-02-28 12:12:33
您是否正在尋找最適合這種分類算法的種類？ 我認爲Divide和Concur似乎很好。 如果算法看起來不錯，您可以有很多其他方法來進行計算。使用MPICH進行特殊的並行處理可能會給你一個最終目的地。
但在決定如何執行之前，您必須先考慮算法是否適合。
我會嘗試考慮規則層次結構。 比方說，規則A是「顏色」，規則B是「形狀」。
如果你的顏色首先鴻溝對象， 比沒有需要比較紅圈藍三角。
這會減少你需要做的比較次數。
如果你想每一個實體與您需要將數據集聚所有實體不是有效地比較，有非常少的原因比較完全無關的事情（比較人類衣服就沒有意義了），我想你的規則會嘗試對數據進行聚類。
，所以你需要將數據集聚，嘗試像K-Means一些聚類算法。
而且看，Apache Mahout
每個實體都與*每*其他實體進行比較？你確定？這是〜5x10^13個組合......如果你能每秒執行一百萬次比較，那將需要超過一年半的時間。 – 2013-02-28 12:09:57
此規則引擎是否已經寫入？這似乎是比C＃更適合於數據庫的工作。 – 2013-02-28 12:13:50
非常多。如果我知道這些規則如何與現在的比較，我可以大大減少工作量。但我不知道他們究竟如何定義匹配規則 – senic 2013-02-28 12:13:55