高效实现“ThenBy”排序

Question

因为Unity/Mono内存分配限制的缘故（长话短说不重要），我需要编写Linq的“立即”模式实现。

除了ThenBy外，我希望所有操作都能与真实的Linq一样快或更快。然而我的实现方式显然存在问题，当使用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;


}

然后在排序函数中，我会创建一个 lambda 函数按顺序应用排序 - 所以最终我得到的是一个看起来像 Comparer<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();
    }

- Mike Talbot

---

大部分的 CPU 时间花费在哪里？ - usr

很难确定，因为分析工具很差。我能说的最好的是，它在排序和比较中（基本上就是那个lambda函数）。 - Mike Talbot

当然可以 - 不过内容比较多。我认为我可以找出必要的部分... - Mike Talbot

好的，我已经添加了。这是我手头有的版本，它将orderby的值传递给thenby - 正如我所说，性能差不多。 - Mike Talbot

在实际的LINQ中，OrderBy()返回IOrderedEnumerable，你可能想利用这一点。另外，你有检查过mono实现的源代码吗？ - svick

Answer 1

我需要猜测一下，但我仍然会尝试解决这个问题。我认为我们应该尝试摆脱嵌套的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;
   };
}

将循环展开，以便在排序过程中不再出现数组。所有这些都是为了解决我们没有静态知识来处理排序函数结构的问题。如果比较函数只是由调用者提供，那么速度会更快。更新：重现（吞吐量比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);
        }

- usr

---

抱歉 - 不好意思，速度会慢2倍，恐怕无法满足您的需求。 - Mike Talbot

即使慢一些，我也无法相信会慢2倍。因此，我写了一个重现程序，它快了50%。代码已添加到帖子中。要么你的测量有问题，要么你正在运行调试模式或附加了调试器（是的，即使附加了调试器也会阻止优化）。 - usr

性能指标相当变化多端，令人困惑。不如我所想的那么容易进行优化。但所有实现都比 LINQ 快大约两倍。 - usr

是的，那就是我在其中添加的跟踪信息 xD 对此很抱歉！回归基础知识后，结果确实显示枚举更快：）但比Linq慢，可能与列表优于数组有关。 - Mike Talbot

虽然这很奇怪，因为单个排序情况要快得多。 - Mike Talbot

Answer 2

我正在按照[类型]，然后按照[价格]这种方式对我的物品进行排序

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

- Hippo Games