如何快速判斷列表是否包含列表？

Question

有多個相關問題，但我正在尋找特定於我的案例的解決方案。有一個（通常）14個整數的數組，每個範圍在1到34之間。如何快速判斷特定靜態列表中的每個int是否至少在該數組中出現過一次？

僅供參考，我目前使用此代碼，這是寫入儘可能地類似於規範，所以它肯定可以大大提高：

if (array.Count < 13) { 
    return; 
} 

var required = new int[] { 
    0*9 + 1, 
    0*9 + 9, 
    1*9 + 1, 
    1*9 + 9, 
    2*9 + 1, 
    2*9 + 9,     
    3*9 + 1, 
    3*9 + 2, 
    3*9 + 3, 
    3*9 + 4, 
    3*9 + 5, 
    3*9 + 6, 
    3*9 + 7, 
}; 

IsThirteenOrphans = !required.Except (array).Any(); 

所需的列表不是動態的，即它在運行時總是一樣的。使用Linq是可選的，主要方面是性能。

編輯：

• 輸入陣列未被排序。
• 輸入值可能會出現多次。
• 輸入數組將包含至少14個項目，即比所需數組多1個。
• 只有1個需要的數組，它是靜態的。
• 所需的值是不同的。
• 您可能會認爲直方圖創建起來很便宜。

更新：我也對排序輸入數組的解決方案感興趣。

Answer 1

理念1
如果你需要幾個required列表進行比較，那麼你可能排序輸入列表，然後簡單地通過迭代進行比較。但排序當然不是太快，但也不會太慢。但是，如果您與幾個必需的列表進行比較，排序的開銷可能會很快攤銷。

一旦數組進行排序比較是微不足道的：

for(int i = 0; i < 14; i++) 
    if(arr[i] != required[i]) return false; 

return true; 

理念2
或者，如果14個整數是不同的/獨特的，你可以簡單地required HashSet的，做

input.Count(i => required.Contains(i)) == 14 

但我不知道沒有實際測試它，如果這比排序更快。

思想3
計算一個快速散列其是下在14個整數排列不變，並比較它的require已知值。只有在散列匹配的情況下才能進行更昂貴的比較。

//Prepare/precalculated 
int[] hashes = new int[34]; 
Random random = new Random(); 
for(int i = 0; i < 34; i++) 
    hashes[i] = random.NextInt(); 

//On each list 
int HashInts(int[] ints) 
{ 
    int result = 0; 
    foreach(int i in ints) 
    result += hashes[i - 1]; 

    return result; 
} 

值的hashes明智的選擇可能會提高它一下，但隨機值應該罰款。

理念4
創建直方圖：

int[] CreateHistogram(int[] ints) 
{ 
    int[] counts = new int[34]; 
    foreach(int i in ints) 
    { 
    counts[i - 1]++; 
    } 

    return counts; 
} 

可以避開陣列通過重用現有陣列創建性能是否真的重要。

Answer 2

您可以輕鬆地遍歷項目並找出是否有任何項目丟失。通過你的例子，我明白你只是想知道是否有任何需要的項目在數組中缺失。所以你可以寫

bool notContains = false; 

foreach (var iddd in required) 
{ 
    foreach (var ar in array) 
    { 
     if (iddd == ar) notContains=true; 
    } 

    if (notContains == false) break; 
} 

這比你的方法快很多。查看下面的代碼添加了計時器。你的方法用了5毫秒，但新的策略0毫秒

System.Diagnostics.Stopwatch aTimer = new System.Diagnostics.Stopwatch(); 
aTimer.Start(); 

var IsThirteenOrphans = !required.Except(array).Any(); 
aTimer.Stop(); 

System.Diagnostics.Stopwatch bTimer = new System.Diagnostics.Stopwatch(); 
bTimer.Start(); 
bool notContains = false; 

foreach (var iddd in required) 
{ 
    foreach (var ar in array) 
    { 
     if (iddd == ar) notContains=true;    
    } 

    if (notContains == false) break; 
} 

bTimer.Stop(); 

Answer 3

編輯： 所以我理解你的問題，可能有一些不錯的過度複雜的解決方案。另一個問題是，它有多好的表現。

static void Main(string[] args) 
{ 
    var required = new int[] 
         { 
          0*9 + 1, 
          0*9 + 9, 
          1*9 + 1, 
          1*9 + 9, 
          2*9 + 1, 
          2*9 + 9, 
          3*9 + 1, 
          3*9 + 2, 
          3*9 + 3, 
          3*9 + 4, 
          3*9 + 5, 
          3*9 + 6, 
          3*9 + 7, 
         }; 

    precomputed = required.Select((x, i) => new { Value = x, Offset = (UInt16)(1 << i) }).ToDictionary(x => x.Value, x => x.Offset); 

    for (int i = 0; i < required.Length; i++) 
    { 
     precomputedResult |= (UInt16)(1 << i); 
    } 

    int[] array = new int[34]; // your array goes here.. 
    Console.WriteLine(ContainsList(array)); 

    Console.ReadKey(); 
} 

// precompute dictionary 
private static Dictionary<int, UInt16> precomputed; 
// precomputed result 
private static UInt16 precomputedResult = 0; 

public static bool ContainsList(int[] values) 
{ 
    UInt16 result = 0; 
    for (int i = 0; i < values.Length; i++) 
    { 
     UInt16 v; 
     if (precomputed.TryGetValue(values[i], out v)) 
      result |= v; 
    } 

    return result == precomputedResult; 
} 

Answer 4

如果你願意，你不應該使用LINQ快速的方式，如果給定的列表項都是波紋管35可以刪除喜歡counting sortif (lst[i] < 35) 最多一次波紋管答案遍歷目錄，並且行爲：

public bool FindExactMatch(int[] array, List<int> lst) 
{ 
    bool[] a34 = new bool[35]; 

    foreach(var item in array) 
    { 
     a34[item] = true; 
    } 

    int exact = 0; 

    for (int i = 0; i < lst.Count; i++) 
    { 
     if (a34[lst[i]]) 
     { 
      exact++; 
      if (exact == array.Length) return true; 

      a34[lst[i]] = false; 
     } 
    } 

    return false; 
} 

的排序列表，如果列表大小大，你可以做lst.BinarySearch(array[i])這需要14 *的log（n）* C1最多，而且我認爲，如果你實現它可能會變得更快它足夠的效率也和我沒」用我自己的實現來測試二進制搜索，但Min，Max，Sort in linq比（在4到10次之間）慢你自己（好）的實施。 如果排序列表大小很小，我更喜歡使用上面的算法，因爲常量c1在上述算法中很小，並且在二進制搜索算法中可能較大。

Answer 5

如果你有一個34 +位整數類型可用和C風格位操作，那麼你可以從變量列表中計算出一個整數V（如果列表是v [0]，v [1]，..）。那麼V是（1 < v 0 [0]）|（1 < < v [1]）...其中1與V具有相同的類型）並且對於靜態列表具有預定義的這樣的整數S，類似地計算。然後測試以查看變量列表中是否包含靜態列表（S &_V）== 0.

Answer 6

一種可能性是更改存儲數據的方式。由於可能的值的範圍被限制爲1-34，而不是存儲號碼的列表，你可以存儲每個數字目前的計數：

int[] counts = new int[34]; 

如果您的列表中有一個1和兩個三分球，然後計算[0] == 1個& &計數[2] = 2（可以交替使用基於1的索引如果使事情更快（更少的減法。））

我們評估每個列表中的詮釋出現至少有一次，您只需按順序爲每個x索引數組，然後驗證所有計數[x]> 0.將數據從計數形式轉換爲列表形式會產生開銷，但這只是一個問題，如果您也經常需要以列表形式查看數據。這種存儲格式的另一個優點是添加/刪除計數不會涉及多於一個數組元素;在列表形式中，刪除列表中間的元素需要多個元素的副本。

Answer 7

這看起來像一個很好的候選人位運算，因爲所需的值是不同的，靜態的，1和34，不保存需要作爲數組之間，將其保存爲一個常量ULONG。在您要檢查的數組中，創建一個新的ulong，通過左移每個值並逐位或。

const ulong comparator = (1UL << 1) | (1UL << 9) | (1UL << 10) | (1UL << 18) | (1UL << 19) | (1UL << 27) | (1UL << 28) | (1UL << 29) | (1UL << 30) | (1UL << 31) | (1UL << 32) | (1UL << 33) | (1UL << 34); 

public static bool ContainsDistinct13Values(int[] array) 
{ 
    ulong word = 0; 
    foreach (int i in array) 
    { 
     word |= (1UL << i); 
    } 
    return word == comparator; 
}