C# 最快速求两个已排序数字集合的交集

Question

C# 最快速求两个已排序数字集合的交集

11

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

我尝试了一堆简单的选项，目前正在使用以下方法：

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

    //do stuff
}

firstSet和secondSet都是List类型。

我还尝试使用LINQ：

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

接下来需要遍历 intersection 集合。这两个集合都是有序的，因此我感觉有更好的方法可以实现。请注意，我不能从集合中删除项目以使它们变小。两个集合通常每个包含大约50个项目。

希望大家能够帮助我，因为我没有太多时间完成这件事。谢谢。

注意：我需要执行这个操作大约530万次，因此每微秒都很重要。

- gligoran

决定创建 UNION 问题，因为这是我实现的内容：https://dev59.com/YlrUa4cB1Zd3GeqPk47F - Jonathan Dickinson

5个回答

8

因为两个列表都已排序，所以您最多只需遍历它们一次即可得出解决方案（根据它们实际包含的值，您还可以跳过其中一个列表的一部分）。

此解决方案将“指针”保留在我们尚未检查的列表部分，并将每个列表的第一个未检查数字进行比较。如果其中一个数字小于另一个数字，则将其所属的列表指针递增以指向下一个数字。如果它们相等，则将该数字添加到交集结果中，并且两个指针都会递增。

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风格方法，考虑到代码的简洁性，如果能看到更快的解决方案，我会感到惊讶。

- Jon

是的，这基本上是我的方法的非流式版本 - 尽管您假设CompareTo始终返回-1、0或1，而不是条件为“小于0”、0和“大于0”。 - Jon Skeet

@JonSkeet：没错。还有一个C风格的bug。:)已经修复了，感谢你发现它。 - Jon

+1 个好方法。谢谢。你的方法更容易理解，如果我想将其与代码融合，那就太棒了。例如，可以进行某种处理，而不是将值添加到交集列表中。 - gligoran

5

针对这种情况，您使用的Linq方法效率相对较低。建议您采用Intersect作为起点。

var intersection = firstSet.Intersect(secondSet);

尝试这个。如果您对其性能进行测量后仍然发现它难以处理，请寻求进一步的帮助（或者可能采用Jon Skeet的方法）。

- Anthony Pegram

我之前尝试过，但如果我没记错的话，它比前两个版本的效果更差。无论如何，我认为Jon Skeet的解决方案是最快的。 - gligoran

@gligoran，这很奇怪。我自己对 Where / Binary 搜索与 Intersect 的测试观察到了大数据集性能的巨大提升，但我会让你回忆起你使用自己的真实数据的观察。 - Anthony Pegram

我确实有一个大数据集，但交集发生在算法的深处，所以我总是对大约50个元素的2个集合进行交集运算，但我必须这样做约530万次。据我所知，Intersect不要求集合被排序，因此它将执行双重循环的2500次迭代，而如果我没记错的话，Jon Skeet的版本只需要50次迭代。Where/Binary可能需要50 * log_2(50)次迭代，即略低于300次。但我可能错了。 - gligoran

@gligoran，Intersect 是将第一个集合加载到 HashSet（1 次遍历）中，然后检查第二个集合中每个元素是否存在的等价操作（1 次遍历）。在 HashSet 中进行查找的复杂度为 O(1)。这种方法应该是相对最优的，但在处理已排序数据的情况下，不如 Jon 的方法那么最优。 - Anthony Pegram

2

我使用了Jon的方法，但需要对非常大的集合执行数十万次的交集操作，并且需要更好的性能。我遇到的情况是列表大小严重不平衡（例如5和80,000），并希望避免迭代整个大列表。

我发现检测不平衡并切换到另一种算法在特定数据集上给我带来了巨大的好处：

public static IEnumerable<T> IntersectSorted<T>(this List<T> sequence1,
        List<T> sequence2,
        IComparer<T> comparer)
{
    List<T> smallList = null;
    List<T> largeList = null;

    if (sequence1.Count() < Math.Log(sequence2.Count(), 2))
    {
        smallList = sequence1;
        largeList = sequence2;
    }
    else if (sequence2.Count() < Math.Log(sequence1.Count(), 2))
    {
        smallList = sequence2;
        largeList = sequence1;
    }

    if (smallList != null)
    {
        foreach (var item in smallList)
        {
            if (largeList.BinarySearch(item, comparer) >= 0)
            {
                yield return item;
            }
        }
    }
    else
    {
        //Use Jon's method
    }
}

我仍然不确定你达到盈亏平衡的点是什么，需要进行更多测试。

- Spencer Rose

我认为这是一个合理的方法，但是：

如果 IEnumerables 不是 List 或类似的类型，则调用 Count() 4 次可能会非常昂贵；更不用说多次枚举了。
这可以通过将第二个 if 改为 else if 来改进。
BinarySearch() 对于 IEnumerable 不可用，因此仅当 largeList 是 List 或 Array 时才有效；要么更改其类型，要么在必要时进行转换。

- elnigno

更新为使用列表。 - Spencer Rose

0

尝试使用以下代码：

firstSet.InterSect (secondSet).ToList ()

或者

firstSet.Join(secondSet, o => o, id => id, (o, id) => o)

- Yahia

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jon Skeet · Accepted Answer

如果您有两个已排序的集合，您可以实现比使用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开始。随着进展，您需要搜索的范围逐渐缩小。然而，是否值得花费额外的实现成本是另一回事。