c# - 高效实现 "ThenBy"排序

Question

我必须编写 Linq 的“立即”模式实现(由于 Unity/Mono 的内存分配限制 - 长话短说，并不重要)。

在我来到 ThenBy 之前，我对所有性能与真正的 Linq 一样快或更快的东西感到满意.显然，我应用此方法的方法存在缺陷，因为我的性能下降到实际速度的 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;


}

然后我在排序函数中所做的是创建一个按顺序应用排序的 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();
    }

Answer 1

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

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