合并2组排序值的最快方法是什么？速度(大O)在这里很重要;不清楚 – 假设这已经完成了数百万次.
假设您不知道值的类型或范围,但是具有高效的IComparer< T>.和/或IEqualityComparer< T>.
给出以下数字：
var la = new int[] { 1,2,4,5,9 };
var ra = new int[] { 3,6,7,8 };
我期待1,3,8,9.以下存根可用于测试代码：
static void Main(string[] args)
{
var la = new int[] { 1,9 };
var ra = new int[] { 3,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)
{
}
解决方法
这将使您的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％.
