目前我有一个list100 万个integers，我检查每个integer2000 个的黑名单integer。这大约需要 2 分钟。
for(int i = 0; i< MillionIntegerList.Length ; i++)
{
for(int blacklisted = 0; blacklisted < TwoThousandIntegerList.Length ; blacklisted++)
if(i==blacklisted)
i = 0; //Zero is a sentinel value
}
这总共进行了 2,000,000,000 次迭代（循环）。有没有更好的方法我没有看到？谢谢
现在有三个选项 - 前两个更通用，因为它们不依赖于MillionIntegerList排序（最初没有指定）。在大列表已经排序的情况下，第三个更可取。
选项1
是的，使用 LINQ 肯定有更好的方法：
var common = MillionIntegerList.Intersect(TwoThousandIntegerList).ToList();
这将在内部使用通过HashSet<int>构建的TwoThousandIntegerList，然后查找其中的每个元素——这将比每次MillionIntegerList都遍历整个元素要高效得多。TwoThousandIntegerList
如果您只想要非黑名单，您需要：
var valid = MillionIntegerList.Except(TwoThousandIntegerList).ToList();
请注意，如果您只需要对结果进行一次迭代，则应删除该ToList调用 - 我已将其包含在内以实现结果，以便可以廉价地多次检查它们。如果您只是在迭代，则Intersector的返回值Except只会流式传输结果，从而在内存使用方面便宜得多。
选项 2
如果您不想依赖 LINQ to Objects 的实现细节，但仍需要基于哈希的方法：
var hashSet = new HashSet<int>(TwoThousandIntegerList);
hashSet.IntersectWith(MillionIntegerList);
// Now use hashSet
选项 3
使用大列表已排序这一事实的方法肯定会很有用。
假设您也不介意先对黑名单进行排序，您可以编写一个像这样的流（和通用）实现（未经测试）：
// Note: to use this, you'd need to make sure that *both* sequences are sorted.
// You could either sort TwoThousandIntegerList in place, or use LINQ's OrderBy
// method.
public IEnumerable<T> SortedIntersect<T>(this IEnumerable<T> first,
IEnumerable<T> second) where T : IComparable<T>
{
using (var firstIterator = first.GetEnumerator())
{
if (!firstIterator.MoveNext())
{
yield break;
}
using (var secondIterator = second.GetEnumerator())
{
if (!secondIterator.MoveNext())
{
yield break;
}
T firstValue = firstIterator.Current;
T secondValue = secondIterator.Current;
while (true)
{
int comparison = firstValue.CompareTo(secondValue);
if (comparison == 0) // firstValue == secondValue
{
yield return firstValue;
}
else if (comparison < 0) // firstValue < secondValue
{
if (!firstIterator.MoveNext())
{
yield break;
}
firstValue = firstIterator.Current;
}
else // firstValue > secondValue
{
if (!secondIterator.MoveNext())
{
yield break;
}
secondValue = secondIterator.Current;
}
}
}
}
}
（如果你愿意，你可以采用 aIComparer<T>而不是依赖于 T 具有可比性。）
由于大列表已排序。通过对小列表进行排序（非常快）然后进行线性合并，您可能会获得最佳结果。您只需要查看大（和小）列表中的每个项目一次，并且不需要在后台创建 Hashtable。
有关如何执行此操作的想法，请参阅 MergeSort 的合并功能部分。
在我看来，您需要的是 Enumerable.Except Method (IEnumerable, IEnumerable)
您的方法需要 O(n*n) 时间。考虑这些优化：
1)
如果您的整数不是太大，您可以使用 bool 数组（例如，如果最大可能的整数是 1000000，则使用 bool[] b = new bool[1000000]）。现在要将数字 K 添加到黑名单中，请使用 b[K] = true。检查是微不足道的。这在 O(n) 中有效。您也可以使用 BitArray
2)
整数可以足够大。使用二叉搜索树存储黑名单（例如 SortedSet）。它有 O(logN) 插入和检索时间。所以总的来说它是O（N * logN）。语法与 List (Add(int K), Contains(int K)) 相同，忽略重复项
我认为最好的解决方案是使用布隆过滤器，如果布隆过滤器说一个元素可能在黑名单中，只需检查黑名单是否不是误报（可以在 O(Log(n) 中完成）已排序）。该解决方案具有时间效率，并且几乎不使用额外的空间，这使得它比使用哈希集好得多。
这是谷歌在 Chrome 中用于黑名单的解决方案。
对较长的列表进行二进制搜索怎么样，因为它是排序的。
foreach(integer blacklisted in TwoThousandIntegerList)
{
integer i = MillionIntegerList.binarySearch(blacklisted)
if(i==blacklisted){
//Do your stuff
}
}
该解决方案仅花费O(m log n)时间，其中 m 是小列表的大小，n 是较长列表的大小。警告：此解决方案假定MillionIntegerList没有重复值。
如果不是这种情况，那么您可以遍历重复，因为它们必须位于连续的块中。为此，我将假设这MillionInterList是一个记录列表，每个记录都有 avalue和 an index。
foreach(integer blacklisted in TwoThousandIntegerList)
{
integer index = MillionIntegerList.binarySearch(blacklisted)
//Find the index of the first occurrence of blacklisted value
while(index > 0 && MillionIntegerList[index - 1].value == blacklisted){
--index;
}
while(MillionIntegerList[index].value == blacklisted){
//Do your stuff
++index;
}
}
此解决方案的成本为O(m log n + mk)，其中k是在 中找到的每个列入黑名单的整数的平均重复数 MillionInterList。
将 HashSet 用于阻止列表。
foreach(integer i in MillionIntegerList)
{
//check if blockedlist contains i
//do what ever you like.
}
List 的使用Except方法。这将起作用