4

我必须编写 Linq 的“立即”模式实现（由于 Unity/Mono 的内存分配限制 - 长篇大论，并不是很重要）。

在我来到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 - 所以我最终得到一个看起来像 aComparer<int>并返回正确排序的函数。

它开始了这种非常糟糕的表现。我已经尝试过使用柯里化和不同签名的版本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();
    }
4

2 回答 2

4

我需要猜测，但我仍在尝试。我认为我们应该尝试摆脱嵌套的 lambda 东西和委托转换。我不确定它的表现如何。排序函数应该是这样的：

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;
   };
}

展开循环，以便在排序期间不再出现数组。

所有这些实际上都是在解决我们对排序函数的结构没有静态知识的事实。如果比较函数只是调用者提交的，那会快得多。

更新：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);
        }
于 2013-02-02T22:40:54.370 回答
0

我以这种方式按 [Type] 然后按 [Price] 对我的项目进行排序

Items = Items.OrderBy(i => i.Type).ToList();

for (var j = 0; j < Items.Count - 1; j++) // ordering ThenBy() AOT workaround
{
    for (var i = 0; i < Items.Count - 1; i++) 
    {
        if (Items[i].Type == Items[i + 1].Type && Items[i].Price > Items[i + 1].Price)
        {
            var temp = Items[i];

            Items[i] = Items[i + 1];
            Items[i + 1] = temp;
        }
    }
}
于 2015-11-01T20:10:32.633 回答