logo标签列表

C#最快的两个排序值集合的并集方法

c#.netunionsortedset
7

如何以最快的速度合并两个已排序值集合？这里速度（大O）非常重要，不需要过于清晰明了-假定这将被执行数百万次。

假定您不知道值的类型或范围，但拥有一个有效的IComparer<T>和/或IEqualityComparer<T>。

给出以下一组数字：

var la = new int[] { 1, 2, 4, 5, 9 };
var ra = new int[] { 3, 4, 5, 6, 6, 7, 8 };

我希望得到1、2、3、4、5、6、7、8、9。以下是可用于测试代码的存根：

static void Main(string[] args)
{
    var la = new int[] { 1, 2, 4, 5, 9 };
    var ra = new int[] { 3, 4, 5, 6, 6, 7, 8 };

    foreach (var item in UnionSorted(la, ra, Int32Comparer.Default))
    {
        Console.Write("{0}, ", item);
    }
    Console.ReadLine();
}

class Int32Comparer : IComparer<Int32>
{
    public static readonly Int32Comparer Default = new Int32Comparer();
    public int Compare(int x, int y)
    {
        if (x < y)
            return -1;
        else if (x > y)
            return 1;
        else
            return 0;
    }
}

static IEnumerable<T> UnionSorted<T>(IEnumerable<T> sortedLeft, IEnumerable<T> sortedRight, IComparer<T> comparer)
{
}
相关链接：https://dev59.com/oGw05IYBdhLWcg3wkik-#7164983 - Jonathan Dickinson
1
你了解这些内容吗？例如，你知道它们都是介于0到63之间的整数吗？你了解这些集合的大小吗？如果你愿意严格限制内容的大小和范围，你可以获得巨大的性能提升。 - Eric Lippert
2
这是归并排序中的“合并”步骤。http://en.wikipedia.org/wiki/Merge_sort - BrokenGlass
@Chad 列表已经排序 - 这是预先知道的，HashSet 有开销，因为它假设值不是这样的。 - Jonathan Dickinson
2
@jdv-Jan de Vaan：不要那样做；整数减法与整数比较并不是相同的操作。如果y-x溢出会怎么样？请参考http://blogs.msdn.com/b/ericlippert/archive/2011/01/27/spot-the-defect-bad-comparisons-part-three.aspx以了解详细信息，如果你是那种喜欢编写错误比较函数的人，你可能也想阅读该系列的其余部分。 - Eric Lippert
显示剩余8条评论
4个回答
3
下面的方法返回正确结果：
static IEnumerable<T> UnionSorted<T>(IEnumerable<T> sortedLeft, IEnumerable<T> sortedRight, IComparer<T> comparer)
{
    var first = true;

    var continueLeft = true;
    var continueRight = true;

    T left = default(T);
    T right = default(T);

    using (var el = sortedLeft.GetEnumerator())
    using (var er = sortedRight.GetEnumerator())
    {
        // Loop until both enumeration are done.
        while (continueLeft | continueRight)
        {
            // Only if both enumerations have values.
            if (continueLeft & continueRight)
            {
                    // Seed the enumeration.
                    if (first)
                    {
                        continueLeft = el.MoveNext();
                        if (continueLeft)
                        {
                            left = el.Current;
                        }
                        else 
                        {
                            // left is empty, just dump the right enumerable
                            while (er.MoveNext())
                                yield return er.Current;
                            yield break;
                        }

                        continueRight = er.MoveNext();
                        if (continueRight)
                        {
                            right = er.Current;
                        }
                        else
                        {
                            // right is empty, just dump the left enumerable
                            if (continueLeft)
                            {
                                // there was a value when it was read earlier, let's return it before continuing
                                do
                                {
                                    yield return el.Current;
                                }
                                while (el.MoveNext());
                            } // if continueLeft is false, then both enumerable are empty here.
                            yield break;
                        }

                        first = false;
                    }

                // Compare them and decide which to return.
                var comp = comparer.Compare(left, right);
                if (comp < 0)
                {
                    yield return left;
                    // We only advance left until they match.
                    continueLeft = el.MoveNext();
                    if (continueLeft)
                        left = el.Current;
                }
                else if (comp > 0)
                {
                    yield return right;
                    continueRight = er.MoveNext();
                    if (continueRight)
                        right = er.Current;
                }
                else
                {
                    // The both match, so advance both.
                    yield return left;
                    continueLeft = el.MoveNext();
                    if (continueLeft)
                        left = el.Current;
                    continueRight = er.MoveNext();
                    if (continueRight)
                        right = er.Current;
                }
            }
            // One of the lists is done, don't advance it.
            else if (continueLeft)
            {
                yield return left;
                continueLeft = el.MoveNext();
                if (continueLeft)
                    left = el.Current;
            }
            else if (continueRight)
            {
                yield return right;
                continueRight = er.MoveNext();
                if (continueRight)
                    right = er.Current;
            }
        }
    }
}

空间复杂度约为O(6)，时间复杂度约为O(max(n,m))（其中m是第二个集合的大小）。
2
这段代码有些 bug。第一，需要在 else if (continueRight) 之后加上 yield return。另外我认为“seed the enumeration” 部分应该在 while 循环之后，以防两个集合都为空。 - mcintyre321
如果两个列表都为空，则当前版本返回一个具有零元素的列表。 - Pac0
实际上，只要其中一个列表为空，0 就会被添加。 - Pac0
我对“空输入集”边缘情况进行了修复。我将所有额外的逻辑放在现有的if(first)块中，所以它不应该通过在每个迭代中添加更多分支来妨碍此代码的良好性能。@Jonathan Dickinson，请告诉我这是否对你的答案进行了过多编辑，如果是，我会另外提供一个答案。 - Pac0
2
我会给LINQ以信任，认为这可能是你在不编写过多代码的情况下能够获得的最快速度：
var result = la.Union(ra);

编辑：

谢谢，我漏掉了排序部分。

你可以这样做：

var result = la.Union(ra).OrderBy(i => i);
是的，但它并不假定列表已排序，并且问题确实要求“最快”的实现。 - Jonathan Dickinson
@Kevin，你能告诉我们时间和空间的大O复杂度吗？ - Jonathan Dickinson
@kd7，你是正确的，我完全错了。对此感到抱歉。 - JBSnorro
4
警告，下面是一个玩笑：这肯定是最快的方法，毫无疑问。相比于50多行代码，只需写一行代码？但我知道你可能想要最高效的代码。 - Kevin Kalitowski
@Kevin - 是的，这是基于假设某人需要一个类似这样的地方（由于分析器指示它是热点）。从之前的问题中可以看出：“注意：我要执行这个操作大约530万次。所以每微秒都很重要。” - Jonathan Dickinson
显示剩余4条评论
2

这将使您的UnionSorted函数稍微不那么通用，但是您可以通过对类型进行假设来进行小改进。如果您在循环内部执行比较（而不是调用Int32Comparer），那么可以节省一些函数调用开销。

因此，您的UnionSorted声明变成了这样...

static IEnumerable<int> UnionSorted(IEnumerable<int> sortedLeft, IEnumerable<int> sortedRight)

然后在循环内部执行此操作，摆脱对comparer.Compare()的调用...

//var comp = comparer.Compare(left, right); // too slow

int comp = 0;
if (left < right)
    comp = -1;
else if (left > right)
    comp = 1;

在我的测试中，这个速度快了约15%。

哇，这差别还真大。如果你能链接到我的答案，我可能得接受你的回答。 - Jonathan Dickinson
哦，这是调试版还是发布版，带有调试器还是没有？ - Jonathan Dickinson
@Jonathan - 这是一个发布版本，没有调试器。我使用了你的示例数组循环了1000万次。性能差距可能会随着更大的列表而扩大。 - Steve Wortham
@Jonathan - 顺便说一下，我也尝试完全放弃IEnumerable，而是直接通过数组进行迭代，但结果发现这样做大约慢了3倍。我很想知道为什么。但你的方法显然更快。 - Steve Wortham
数组边界检查。我认为Array中的IEnumerable有一些魔法可以防止它。你可以尝试使用不安全的代码。 - Jonathan Dickinson
啊，有点明白了。我还找到了这篇关于IEnumerable的小文章……http://weblogs.asp.net/justin_rogers/archive/2004/10/01/236837.aspx - Steve Wortham
0

我会这样解决问题。（我做了一个假设，这显著减轻了这个问题的难度，只是为了说明这个想法。）

假设：集合中包含的所有数字都是非负数。

创建一个至少有n位的字，其中n是您预期的最大值。（如果您预期的最大值是12，则必须创建一个16位的字。）

迭代两个集合。对于每个值val，将val-th位与1进行或运算。

完成后，计算设置为1的位数。创建该大小的数组。 逐个检查每个位，如果设置了第n位，则将n添加到新数组中。

据我所了解，这个程序的性能为O(2nm)（其中m是第二个集合）。 - Jonathan Dickinson
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接