C#最快交集的2组排序数字

Question

我正在计算我的应用程序的时间关键部分中的两组排序数字的交集.这个计算是整个应用程序的最大瓶颈,所以我需要加快速度.

我尝试过一些简单的选项,目前正在使用它:

foreach (var index in firstSet)
{
    if (secondSet.BinarySearch(index) < 0)
        continue;

    //do stuff
}

这两个firstSet和secondSet的类型列表.

我也尝试过使用LINQ:

var intersection = firstSet.Where(t => secondSet.BinarySearch(t) >= 0).ToList();

然后循环intersection.

但是,由于这两个集合都已排序,我觉得有更好的方法.请注意,我无法从集中删除项目以使其变小.两套通常每件约50件.

请帮助我们,因为我没有太多时间来完成这件事.谢谢.

注意:我这样做了大约530万次.所以每微秒都很重要.

Answer 1

如果您有两个已排序的集合,则可以实现比LINQ开箱即用的更快的交集.

基本上,保持两个IEnumerator<T>光标打开,每组一个.在任何时候,提前取较小值.如果它们在任何点匹配,则将它们推进,依此类推,直到到达任一迭代器的末尾.

关于这一点的好处是你只需要遍历每个集合一次,你就可以在O(1)内存中进行迭代.

这是一个示例实现 - 未经测试,但它确实编译:)它假设两个传入序列都是无重复和排序的,两者都根据提供的比较器(传入Comparer<T>.Default):

(答案结尾处有更多文字!)

static IEnumerable<T> IntersectSorted<T>(this IEnumerable<T> sequence1,
    IEnumerable<T> sequence2,
    IComparer<T> comparer)
{
    using (var cursor1 = sequence1.GetEnumerator())
    using (var cursor2 = sequence2.GetEnumerator())
    {
        if (!cursor1.MoveNext() || !cursor2.MoveNext())
        {
            yield break;
        }
        var value1 = cursor1.Current;
        var value2 = cursor2.Current;

        while (true)
        {
            int comparison = comparer.Compare(value1, value2);
            if (comparison < 0)
            {
                if (!cursor1.MoveNext())
                {
                    yield break;
                }
                value1 = cursor1.Current;
            }
            else if (comparison > 0)
            {
                if (!cursor2.MoveNext())
                {
                    yield break;
                }
                value2 = cursor2.Current;
            }
            else
            {
                yield return value1;
                if (!cursor1.MoveNext() || !cursor2.MoveNext())
                {
                    yield break;
                }
                value1 = cursor1.Current;
                value2 = cursor2.Current;
            }
        }
    }
}

编辑:如评论中所述,在某些情况下,您可能有一个输入比另一个输入大得多,在这种情况下,您可以使用二进制搜索从较大集合中较小集合中的每个元素中节省大量时间.这需要随机访问较大的集合(但这只是二进制搜索的先决条件).您甚至可以通过使用前一个结果中的匹配来为二进制搜索提供下限,从而使它比天真的二进制搜索稍好一些.所以假设你在一个集合中寻找值1000,2000和3000,每个整数从0到19,999.在第一次迭代中,您需要查看整个集合 - 您的起始下限/上限索引将分别为0和19,999.但是,在索引1000处找到匹配后,下一步(您正在寻找2000)可以从较低的索引2000开始.随着您的进展,您需要搜索的范围逐渐变窄.然而,这是否值得额外的实施成本是另一回事.

Answer 2

由于两个列表都已排序,您可以通过最多迭代一次来获得解决方案(您也可以跳过一个列表的一部分,具体取决于它们包含的实际值).

该解决方案保留了我们尚未检查的列表部分的"指针",并比较它们之间每个列表的第一个未检查的数字.如果一个小于另一个,则指向它所属列表的指针将递增以指向下一个数字.如果它们相等,则将数字添加到交集结果中,并且两个指针都递增.

var firstCount = firstSet.Count;
var secondCount = secondSet.Count;
int firstIndex = 0, secondIndex = 0;
var intersection = new List<int>();

while (firstIndex < firstCount && secondIndex < secondCount)
{
    var comp = firstSet[firstIndex].CompareTo(secondSet[secondIndex]);
    if (comp < 0) {
        ++firstIndex;
    }
    else if (comp > 0) {
        ++secondIndex;
    }
    else {
        intersection.Add(firstSet[firstIndex]);
        ++firstIndex;
        ++secondIndex;
    }
}

以上是解决这一特定问题的教科书C风格方法,考虑到代码的简单性,我会惊讶地看到更快的解决方案.

Answer 3

你正在使用效率相当低的Linq方法来完成这类任务,你应该选择Intersect作为起点.

var intersection = firstSet.Intersect(secondSet);

试试这个.如果你测量它的性能并且仍然觉得它很笨拙,那就去寻求进一步的帮助(或者按照Jon Skeet的方法).