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

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个项目.
• 只有一个必需的数组,它是静态的.
• 所需的值是不同的.
• 您可能认为直方图的创建成本很低.

更新:我也对排序输入数组的解决方案感兴趣.

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;
}

如果性能确实很重要，您可以通过重用现有数组来避免创建数组。