将大型整数列表与较小的整数列表进行比较的最有效方法是什么？

Question

目前我有一list百万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次迭代(循环).有没有更好的方式我没有看到？谢谢

Answer 1

现在有三个选项 - 前两个更通用,因为它们不依赖于MillionIntegerList排序(最初未指定).在已经对大列表进行排序的情况下,第三个是优选的.

选项1

是的,使用LINQ肯定有更好的方法:

var common = MillionIntegerList.Intersect(TwoThousandIntegerList).ToList();

那将在内部使用一个HashSet<int>内置的TwoThousandIntegerList,然后查找其中的每个元素MillionIntegerList- 这将比TwoThousandIntegerList每次完成整个过程更有效.

如果您只想要非黑名单的,您需要:

var valid = MillionIntegerList.Except(TwoThousandIntegerList).ToList();

请注意,如果您只需要迭代结果一次,则应该删除该ToList调用 - 我已将其包含在内以实现结果,以便可以便宜地多次检查它们.如果你只是迭代,返回值Intersect或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;
                }  
            }                
        }
    }
}

(IComparer<T>如果你想要的话,你可以选择一个,而不是依赖于T的可比性.)

Answer 2

由于大型列表已排序.您可以通过排序小列表(非常快)然后进行线性合并来获得最佳结果.您只需要查看大(和小)列表中的每个项目一次,并且不需要在后台创建Hashtable.

请参阅MergeSort 的合并功能部分,了解如何执行此操作.

Answer 3

在我看来,你需要的是Enumerable.Except方法(IEnumerable,IEnumerable)

点击这里http://msdn.microsoft.com/en-us/library/bb300779.aspx