[C#]Array.Sort(keys, items) 권장 사항

매핑 정렬

(int Num1, int Num2)의 배열은 Num1-Num2의 크기에 따라 배열된다.
이와 같은 매핑 (LINQ로 말하자면 Select 은 몇 가지 방법으로 정렬된다.

Compoarison<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)의 정렬은Compoarison과Compoarer의 정렬보다 5, 6배 빠르다.
.NET Core는 LINQ가 빠르기 때문에 LINQArray.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