C#最快联合2组排序值

Question

合并2组排序值的最快方法是什么？速度(大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)
{
}

Answer 1

这将使您的 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%。