目前我有一个包含100万个整数的列表list，我会把每个integer与2000个被禁用的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();
这将使用通过TwoThousandIntegerList构建的HashSet<int>，然后在其中查找MillionIntegerList的每个元素 - 这比每次遍历整个TwoThousandIntegerList要高效得多。
如果您只想要非黑名单中的元素，则需要：
var valid = MillionIntegerList.Except(TwoThousandIntegerList).ToList();
ToList调用 - 我已将其包含在内以实现结果的材料化，以便可以以低廉的成本多次检查。如果您只是迭代，Intersect或Except的返回值将只会stream结果，这将在内存使用方面更加便宜。
选项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;
}
}
}
}
}
IComparer<T> 来代替依赖于 T 可比较。）MillionIntegerList已经排序的事实，而哈希查找在最好情况下是O(c)，但在最坏情况下是O(m)，其中m是要放入哈希表的列表的大小，而且这是一个实现细节(而且错误地记录了!)，哪个列表被放入哈希表是不确定的。我更喜欢对TwoThousandIntegerList进行排序，然后并行遍历两个列表，这样排序的复杂度是O(mlog(m))，遍历的复杂度是O(n)。 - Old Pro由于较大的列表已经排序，您可能会通过对小列表进行排序（非常快）然后执行线性合并来获得最佳结果。您只需要查看大（和小）列表中的每个项目一次，而且无需创建后台中的散列表。
请参阅MergeSort的merge function部分，以获取如何执行此操作的想法。
您的方法需要O(n*n) 的时间。 考虑以下优化：
1）
如果您的整数不太大，可以使用布尔数组（例如，如果最大可能的整数为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)），会忽略重复项。
既然长列表已经排序了，为什么不在其上进行二分查找呢？
foreach(integer blacklisted in TwoThousandIntegerList)
{
integer i = MillionIntegerList.binarySearch(blacklisted)
if(i==blacklisted){
//Do your stuff
}
}
这个解决方案只需要 O(m log n) 的时间，其中 m 是小列表的大小，n 是较长列表的大小。 注意： 这个解决方案假设 MillionIntegerList 没有重复值。
如果不是这种情况，那么你可以遍历重复项，因为它们必须位于连续的块中。为此，我将假设 MillionInterList 是一个记录列表，每个记录都有一个 value 和一个 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中找到的每个黑名单整数的平均重复数量。
我认为最好的解决方案是使用Bloom过滤器，如果Bloom过滤器指示一个元素可能在黑名单中，只需检查它是否不是误报（如果黑名单已排序，则可以在O(Log(n))内完成）。
这个解决方案时间效率高，几乎不需要额外的空间，比使用哈希集合要好得多。
这是谷歌在Chrome中用于黑名单的解决方案。
foreach(integer i in MillionIntegerList)
{
//check if blockedlist contains i
//do what ever you like.
}
使用 Except 方法来操作列表。这样做可以起到作用。