[C#]Array.Sort(keys, items) のススメ

写像によるソート

(int Num1, int Num2) の配列を Num1-Num2 の大きさでソートする場合を考えてみます。

このような写像(LINQでいうとSelect)によるソートにはいくつか方法があります。

Comparison<T> によるソート

まず思い浮かぶのは

public (int, int)[] Comparison()
{
    Array.Sort(array, (x, y) => (x.Num1 - x.Num2).CompareTo(y.Num1 - y.Num2));
    return array;
}

と比較をラムダ式で渡す方法です。

IComparer<T> によるソート

ほぼ同じですが、IComparer<T> でもソートできます。

class TupComparer : IComparer<(int Num1, int Num2)>
{
    public int Compare((int Num1, int Num2) x, (int Num1, int Num2) y) => (x.Num1 - x.Num2).CompareTo(y.Num1 - y.Num2);
}
public (int, int)[] Comparer()
{
    Array.Sort(array, new TupComparer());
    return array;
}

Array.Sort(keys, items) でのソート

異なるアプローチとして Array.Sort(keys, items) でのソートもあります。

public (int, int)[] Key()
{
    Func<(int Num1, int Num2), int> func = x => (x.Num1 - x.Num2);
    var keys = new int[array.Length];
    for (int i = 0; i < array.Length; i++)
        keys[i] = func(array[i]);
    Array.Sort(keys, array);
    return array;
}

写像の配列を作成して、それをソートのキーとします。

func は実際にはメソッドの引数などとして受け取る想定です。

ベンチマーク

ベンチマークのコード

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Diagnosers;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;
using BenchmarkDotNet.Toolchains.CsProj;

#if DEBUG
BenchmarkSwitcher.FromAssembly(typeof(BenchmarkConfig).Assembly).Run(args, new DebugInProcessConfig());
#else
_ = BenchmarkRunner.Run(typeof(Benchmark).Assembly);
#endif


public class BenchmarkConfig : ManualConfig
{
    public BenchmarkConfig()
    {
        //AddDiagnoser(MemoryDiagnoser.Default);
        AddExporter(BenchmarkDotNet.Exporters.MarkdownExporter.GitHub);
#if false
        AddJob(Job.ShortRun.WithToolchain(CsProjCoreToolchain.NetCoreApp31));
#else
        AddJob(Job.ShortRun.WithToolchain(CsProjCoreToolchain.NetCoreApp50));
        AddJob(Job.ShortRun.WithToolchain(CsProjCoreToolchain.NetCoreApp31));
        AddJob(Job.ShortRun.WithToolchain(CsProjClassicNetToolchain.Net472));
#endif
    }
}

[Config(typeof(BenchmarkConfig))]
[GroupBenchmarksBy(BenchmarkLogicalGroupRule.ByParams)]
public class Benchmark
{
    private readonly Random rnd = new(42);
    [Params(1 << 20)]
    public int N;

    private Func<(int Num1, int Num2), int> func;
    private (int Num1, int Num2)[] array;
    [GlobalSetup]
    public void GlobalSetup()
    {
        array = new (int Num1, int Num2)[N];
        for (int i = 0; i < array.Length; i++)
            array[i] = (rnd.Next(), rnd.Next());
        func = x => (x.Num1 - x.Num2);
    }

    [Benchmark]
    public (int, int)[] Comparison()
    {
        Array.Sort(array, (x, y) => (x.Num1 - x.Num2).CompareTo(y.Num1 - y.Num2));
        return array;
    }

    class ReverseComparer : IComparer<(int Num1, int Num2)>
    {
        public int Compare((int Num1, int Num2) x, (int Num1, int Num2) y) => (x.Num1 - x.Num2).CompareTo(y.Num1 - y.Num2);
    }

    [Benchmark]
    public (int, int)[] Comparer()
    {
        Array.Sort(array, new ReverseComparer());
        return array;
    }

    [Benchmark]
    public (int, int)[] Key()
    {
        var keys = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
            keys[i] = func(array[i]);
        Array.Sort(keys, array);
        return array;
    }

}

結果

Array.Sort に IComparer を渡さない場合は専用の最適化がされて仮想呼び出しがなくなり非常に高速に動作します。

そのため、上記のソートでは Array.Sort(keys, items) でのソートが Comparison や Comparer でのソートより5, 6倍ほど高速になりました。

.NET CoreならばLINQが高速なのでLINQで Array.Sort(array.Select(func).ToArray(), array); としてしまうのも良いです。

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i7-4790 CPU 3.60GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.202
  [Host]   : .NET Core 5.0.5 (CoreCLR 5.0.521.16609, CoreFX 5.0.521.16609), X64 RyuJIT
  ShortRun : .NET Core 3.1.14 (CoreCLR 4.700.21.16201, CoreFX 4.700.21.16208), X64 RyuJIT

Job=ShortRun  IterationCount=3  LaunchCount=1  
WarmupCount=3  

Method	Toolchain	N	Mean	Error	StdDev
Comparison	.NET Core 3.1	1048576	148.88 ms	11.693 ms	0.641 ms
Comparer	.NET Core 3.1	1048576	146.76 ms	36.676 ms	2.010 ms
Key	.NET Core 3.1	1048576	27.14 ms	17.227 ms	0.944 ms
Comparison	.NET Core 5.0	1048576	150.60 ms	36.800 ms	2.017 ms
Comparer	.NET Core 5.0	1048576	149.59 ms	14.520 ms	0.796 ms
Key	.NET Core 5.0	1048576	26.25 ms	4.077 ms	0.223 ms
Comparison	net472	1048576	178.34 ms	13.304 ms	0.729 ms
Comparer	net472	1048576	165.11 ms	9.073 ms	0.497 ms
Key	net472	1048576	30.34 ms	12.065 ms	0.661 ms