4

Linq の「即時」モードの実装を作成する必要があります (Unity/Mono のメモリ割り当て制限のため - 長い話ですが、それほど重要ではありません)。

私はThenBy. 私のパフォーマンスが実際の取引よりも 4 倍遅くなるため、これを適用する私の方法には明らかに欠陥があります。

だから私が今していることは -

各OrderBy,ThenBy節について

  • 各セレクターの結果のリストを作成し、セレクター評価のすべての結果をリストに追加します
  • 2 つのパラメーターからインデックス付けされたリストを使用するデフォルトの比較子を使用するラムダを作成します。

次のようになります。

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;


}

次に、並べ替え関数で行うことは、並べ替えを順番に適用するラムダを作成することです。そのため、最終的には a のように見え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();
    }
4

2 に答える 2

4

推測する必要がありますが、まだこれを狙っています。ネストされたラムダのものを取り除き、変換を委任する必要があると思います。それがどれだけうまくいくかはわかりません。ソート関数は次のようになります。

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);
        }
于 2013-02-02T22:40:54.370 に答える
0

このように[種類]、[価格]の順で商品を並べ替えています

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 に答える