算法匹配整數

Question

的列出了每一天，我們有大約50,000的數據結構的情況下（這最終可能增長要大得多）封裝了以下內容：

DateTime AsOfDate; 
int key; 
List<int> values; // list of distinct integers 

這可能是不相關的，但列表values是具有屬性的不同整數的列表，對於給定值AsOfDate，values的並集覆蓋所有值key產生不同整數的列表。也就是說，在同一天的兩個不同的values列表中不會顯示整數。

該列表通常包含非常少的元素（介於一到五之間），但有時只要五十個元素。

鑑於相鄰的日子，我們試圖找到這些對象的實例，其中兩天的key值不同，但列表values包含相同的整數。

我們使用以下算法。通過

string signature = String.Join("|", values.OrderBy(n => n).ToArray()); 

轉換列表values爲一個字符串，然後散列signature爲整數，責令造成的散列碼列表（一個列表的每一天），這兩個表走尋找匹配，然後檢查，看看如果相關的鍵不同。 （同時檢查相關列表以確保我們沒有散列衝突。）

是否有更好的方法？

Answer 1

你可能只是散列列表本身，而不是通過String。

除此之外，我認爲你的算法幾乎是最優的。假設沒有哈希碰撞，它是O（n log n + m log m）其中n和m是您比較的兩天中每一天的條目數。 （排序是瓶頸。）

如果您使用將哈希值插入的桶數組（實質上是一個哈希表），則可以在O（n + m）中執行此操作。您可以比較兩個桶數組O（max（n，m）），假定長度取決於條目的數量（以獲得合理的負載因子）。

通過使用HashSet.IntersectWith（）並編寫一個合適的比較函數，應該可以讓庫爲您完成此操作（看起來您正在使用.NET）。

你不能比O（n + m）做得更好，因爲每個條目至少需要訪問一次。

編輯：誤讀，修正。

Answer 2

排序問題？即第1天的[1,2]和第2天的[2,1]是否相等？如果他們是，那麼哈希可能無法正常工作。您可以使用排序的數組/矢量來幫助進行比較。

另外，它是什麼樣的密鑰？它有一個確定的範圍（例如0-63）嗎？您可能能夠將它們連接成大整數（可能需要超過64位的精度）和散列，而不是轉換爲字符串，因爲這可能需要一段時間。

Answer 3

在其他答案的基礎上，您可以通過在每個列表的所有元素之間創建一個簡單構建的低成本散列，使該過程更快。 你不必訂購你的清單，所有你會得到的是一個int比字符串更容易和更快地存儲。

然後，您只需要使用生成的XORed號碼作爲哈希表的鍵，並在插入之前檢查該鍵的存在。 如果已經有一個現有的密鑰，那麼只有對相應的列表進行排序並進行比較。

如果您發現匹配，您仍然需要對它們進行比較，因爲使用簡單XOR可能會發生一些衝突。
我認爲結果會比重新排列數組並將它們轉換爲字符串的速度快得多，並且內存佔用率要低得多。

如果您要自己實現List<>，那麼您可以在其中構建XOR鍵的生成，以便在列表中的每個操作時重新計算它。
這將使檢查重複列表的過程更快。

代碼

下面是實現這個第一嘗試。

Dictionary<int, List<List<int>>> checkHash = new Dictionary<int, List<List<int>>>(); 

public bool CheckDuplicate(List<int> theList) { 
    bool isIdentical = false; 
    int xorkey = 0; 
    foreach (int v in theList) xorkey ^= v; 

    List<List<int>> existingLists; 
    checkHash.TryGetValue(xorkey, out existingLists); 
    if (existingLists != null) { 
     // Already in the dictionary. Check each stored list 
     foreach (List<int> li in existingLists) { 
      isIdentical = (theList.Count == li.Count); 
      if (isIdentical) { 
       // Check all elements 
       foreach (int v in theList) { 
        if (!li.Contains(v)) { 
         isIdentical = false; 
         break; 
        } 
       } 
      } 
      if (isIdentical) break; 
     } 
    } 
    if (existingLists == null || !isIdentical) { 
     // never seen this before, add it 
     List<List<int>> newList = new List<List<int>>(); 
     newList.Add(theList); 
     checkHash.Add(xorkey, newList); 
    } 
    return isIdentical; 
} 

不是最優雅最簡單的還是一見鍾情閱讀，這是相當「hackey」，我甚至不能確定它的性能比從Guffa越雅緻版更好。
它通過在字典中存儲List<int>的列表來處理XOR鍵中的衝突。

如果找到重複鍵，我們循環遍歷每個先前存儲的列表，直到發現不匹配。

關於代碼的好處是它應該可以像在大多數情況下所能獲得的那樣快，並且在發生衝突時比編譯字符串更快。

Answer 4

爲列表實現IEqualityComparer，然後您可以將該列表用作字典中的鍵。

如果列表進行排序，也可能是這樣簡單：

IntListEqualityComparer : IEqualityComparer<List<int>> { 

    public int GetHashCode(List<int> list) { 
     int code = 0; 
     foreach (int value in list) code ^=value; 
     return code; 
    } 

    public bool Equals(List<int> list1, List<int> list2) { 
     if (list1.Count != list2.Coount) return false; 
     for (int i = 0; i < list1.Count; i++) { 
     if (list1[i] != list2[i]) return false; 
     } 
     return true; 
    } 

} 

現在，您可以創建一個使用的IEqualityComparer字典：

Dictionary<List<int>, YourClass> day1 = new Dictionary<List<int>, YourClass>(new IntListEqualityComparer()); 

添加的所有項目從第一然後從第二天開始循環查看項目，並檢查字典中是否存在密鑰。由於IEqualityComprarer都處理哈希碼和比較，所以您不會得到任何錯誤匹配。

您可能想要測試一些計算散列碼的不同方法。示例中的示例工作正常，但可能無法爲您的特定數據提供最佳效率。哈希碼對字典工作的唯一要求是相同的列表總是獲得相同的哈希碼，所以你可以做任何你想要計算的東西。目標是爲字典中的鍵獲取儘可能多的不同散列碼，以便每個存儲桶中有儘可能少的項目（使用相同的散列碼）。

Answer 5

將它放在SQL數據庫中可能是值得的。如果你不想擁有一個完整的DBMS，你可以使用sqlite。

這將使唯一性檢查和聯合和這些類型的操作非常簡單的查詢，並將非常有效。如果它再次需要，它還可以讓您輕鬆存儲信息。

Answer 6

您是否考慮總結值列表以獲取可用作預先檢查不同列表是否包含相同值集的整數？

雖然會有更多的碰撞（相同的總和並不一定意味着相同的一組值），但我認爲它可以首先減少大部分所需的比較組。