【C#】降順（逆順）ソートと Reverse()

降順ソートを行う際にArray.SortしてからArray.Reverseを行っているコードを見たのをきっかけに整理。

最初は、上記手段ははじめから降順ソートを行うよりReverse()の処理が増えるぶんさすがに不利なのではという印象を受けた。
けれど、以前の記事でも触れたが（Arrayが内部で用いる）SpanのReverse()は速い。
ということは、これが冴えたやり方なのか……？となり、降順ソートを行う他手段と比較することにした。

まずはLINQ。LINQはその名もOrderDescending()を擁している。

// double[] array;
public double[] ByLINQ() => array.OrderDescending().ToArray();

ToArray()は条件が以降と揃ってないのだけれど、今回はこれで。

次はデリゲート。IComparable<T>.CompareToの符号を反転してお手軽降順。

public double[] ByDelegate()
{
    Array.Sort(array, (x, y) => -x.CompareTo(y));
    return array;
}

次はIComparer。

private class DescComparer : IComparer<double>
{
    public int Compare(double x, double y) => -x.CompareTo(y);
}

public double[] ByComparer()
{
    Array.Sort(array, new DescComparer());
    return array;
}

そしてReverse()。

public double[] ByReverse()
{
    Array.Sort(array);
    Array.Reverse(array);
    return array;
}

上記をBenchmarkDotNetにて比較。
内容は、Random.NextDoubleで生成した65536個のdoubleのソート。

上記内容以外の比較用コード折りたたみ

private double[] stored = Array.Empty<double>();
private double[] array = Array.Empty<double>();

[GlobalSetup]
public void Setup()
{
    stored = new double[1<<16];
    array = new double[stored.Length];

    var rand = Random.Shared;
    for (int i = 0; i < stored.Length; i++)
    {
        stored[i] = rand.NextDouble();
    }
}

[IterationSetup]
public void ItrSetup()
{
    stored.CopyTo(array, 0);
}

     Method |      Mean |    Error |    StdDev | Allocated |
----------- |----------:|---------:|----------:|----------:|
     ByLINQ | 16.206 ms | 4.649 ms | 0.2548 ms | 1311568 B |
 ByDelegate |  9.765 ms | 2.650 ms | 0.1452 ms |     600 B |
 ByComperer |  9.272 ms | 1.093 ms | 0.0599 ms |     688 B |
  ByReverse |  4.047 ms | 1.446 ms | 0.0792 ms |     600 B |

Reverse()が良い、という結果になった。

配列のサイズなどの条件次第でまた変わってくるかもしれないけれど、Reverse()を用いるのはかなり有力に思えた。

てくメモ

trivial な notes

【C#】降順（逆順）ソートと Reverse()