首页 / C# / c# – “ThenBy”排序的有效实现
c# – “ThenBy”排序的有效实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了c# – “ThenBy”排序的有效实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5242字,纯文字阅读大概需要8分钟。
内容图文
我不得不写一个Linq的“立即”模式实现(由于Unity / Mono上的内存分配限制 – 长篇故事,并不是很重要).
我很高兴一切都比真正的Linq表现得快或快,直到我来到ThenBy.很明显,我的应用方法存在缺陷,因为我的性能下降到实际速度的4倍.
所以我现在正在做的是 –
对于每个OrderBy,ThenBy子句
>为每个选择器的结果创建一个列表,将选择器评估的所有结果添加到列表中
>创建一个使用默认比较器的lambda,它使用从两个参数索引的列表
它看起来像这样:
public static IEnumerable<T> OrderByDescending<T,TR>(this IEnumerable<T> source, Func<T,TR> clause, IComparer<TR> comparer = null)
{
comparer = comparer ?? Comparer<TR>.Default;
var linqList = source as LinqList<T>;
if(linqList == null)
{
linqList = Recycler.New<LinqList<T>>();
linqList.AddRange(source);
}
if(linqList.sorter!=null)
throw new Exception("Use ThenBy and ThenByDescending after an OrderBy or OrderByDescending");
var keys = Recycler.New<List<TR>>();
keys.Capacity = keys.Capacity > linqList.Count ? keys.Capacity : linqList.Count;
foreach(var item in source)
{
keys.Add(clause(item));
}
linqList.sorter = (x,y)=>-comparer.Compare(keys[x],keys[y]);
return linqList;
}
public static IEnumerable<T> ThenBy<T,TR>(this IEnumerable<T> source, Func<T,TR> clause, IComparer<TR> comparer = null)
{
comparer = comparer ?? Comparer<TR>.Default;
var linqList = source as LinqList<T>;
if(linqList == null || linqList.sorter==null)
{
throw new Exception("Use OrderBy or OrderByDescending first");
}
var keys = Recycler.New<List<TR>>();
keys.Capacity = keys.Capacity > linqList.Count ? keys.Capacity : linqList.Count;
foreach(var item in source)
{
keys.Add(clause(item));
}
linqList.sorters.Add((z,x,y)=>z != 0 ? z : comparer.Compare(keys[x],keys[y]));
return linqList;
}
然后我在sort函数中做的是创建一个按顺序应用排序的lamda – 所以我最终得到一个看起来像Comparer< int>的函数.并返回正确的顺序.
它开始这个非常糟糕的表现.我已经尝试使用currying和OrderBy和ThenBy函数的不同签名版本,但没有什么比这更快,我想知道我是否只是错过了关于多键排序的技巧.
排序变量和功能:
public List<Func<int,int,int,int>> sorters = new List<Func<int, int, int, int>>();
public Func<int,int,int> sorter;
public List<int> sortList = new List<int>();
bool sorted;
private List<T> myList = new List<T>();
void ResolveSorters()
{
if(sorter==null)
return;
Func<int,int,int> function = null;
if(sorters.Count==0)
{
function = sorter;
}
else
{
function = sorter;
foreach(var s in sorters)
{
var inProgress = function;
var current = s;
function = (x,y)=>current(inProgress(x,y), x,y);
}
}
sortList.Capacity = sortList.Capacity < myList.Count ? myList.Count : sortList.Capacity;
sortList.Clear();
sortList.AddRange(System.Linq.Enumerable.Range(0,myList.Count));
//var c = myList.Count;
/*for(var i =0; i < c; i++)
sortList.Add(i);*/
sortList.Sort(new Comparison<int>(function));
sorted = true;
sorters.Clear();
}
解决方法:
我需要猜测,但我仍然在拍这个.我认为我们应该尝试摆脱嵌套的lambda内容并委托转换.我不确定它的表现如何. sort函数应该是这样的:
Func<int, int, int>[] sorters = ...; //fill this. it really should be an array!
Comparison<int> = (a, b) => {
foreach (var s in sorters) {
var cmp = s(a, b);
if(cmp != 0) return cmp;
}
return 0;
};
所以我们摆脱了嵌套的调用.现在都是一个简单的循环.您可以为小循环大小构建专用版本:
Func<int, int, int>[] sorters = ...; //fill this. it really should be an array!
switch (sorters.Length) {
case 2: {
var s0 = sorters[0], s1 = sorters[1];
Comparison<int> = (a, b) => {
var cmp = s0(a, b);
if(cmp != 0) return cmp;
var cmp = s1(a, b);
if(cmp != 0) return cmp;
return 0;
};
}
展开循环,以便在排序期间不再出现任何数组.
所有这些都是因为我们没有对sort函数结构的静态知识这一事实.如果比较函数刚刚由调用者传递,那将会快得多.
更新:Repro(吞吐量比LINQ高100%)
Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
Func<int, int, int>[] sorters = new Func<int, int, int>[]
{
(a, b) => (a & 0x1).CompareTo(b & 0x1),
(a, b) => (a & 0x2).CompareTo(b & 0x2),
(a, b) => (a & 0x4).CompareTo(b & 0x4),
(a, b) => a.CompareTo(b),
};
Func<int, int, int> comparisonB = sorters[0];
for (int i = 1; i < sorters.Length; i++)
{
var func1 = comparisonB;
var func2 = sorters[i];
comparisonB = (a, b) =>
{
var cmp = func1(a, b);
if (cmp != 0) return cmp;
return func2(a, b);
};
}
var comparisonC = new Comparison<int>(comparisonB);
Comparison<int> comparisonA = (a, b) =>
{
foreach (var s in sorters)
{
var cmp = s(a, b);
if (cmp != 0) return cmp;
}
return 0;
};
Func<int, int, int> s0 = sorters[0], s1 = sorters[1], s2 = sorters[2], s3 = sorters[3];
Comparison<int> comparisonD = (a, b) =>
{
var cmp = s0(a, b);
if (cmp != 0) return cmp;
cmp = s1(a, b);
if (cmp != 0) return cmp;
cmp = s2(a, b);
if (cmp != 0) return cmp;
cmp = s3(a, b);
if (cmp != 0) return cmp;
return 0;
};
{
GC.Collect();
var data = CreateSortData();
var sw = Stopwatch.StartNew();
Array.Sort(data, comparisonC);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalSeconds);
}
{
GC.Collect();
var data = CreateSortData();
var sw = Stopwatch.StartNew();
Array.Sort(data, comparisonA);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalSeconds);
}
{
GC.Collect();
var data = CreateSortData();
var sw = Stopwatch.StartNew();
Array.Sort(data, comparisonD);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalSeconds);
}
{
GC.Collect();
var data = CreateSortData();
var sw = Stopwatch.StartNew();
foreach (var source in data.OrderBy(x => x & 0x1).ThenBy(x => x & 0x2).ThenBy(x => x & 0x4).ThenBy(x => x))
{
}
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalSeconds);
}
内容总结
以上是互联网集市为您收集整理的c# – “ThenBy”排序的有效实现全部内容,希望文章能够帮你解决c# – “ThenBy”排序的有效实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。