【雑記】上位 k 件を得る (3) - 余談

前回記事までの余談。余談なので雑記。
【C#】上位 k 件を得る (2) - ヒープセレクトと部分ソート - てくメモ

部分ソートの適用場面のひとつとして、k 件を得ることに対して母数が大きいということ以外に、何らかの理由でソートに伴う要素の交換回数そのものを減らしたい、ということを挙げた。

世にある例として、東方キャラソートというものがある。

これは、東方 Project という作品世界に登場するキャラクターでいわゆるキャラランキングをつくるサービス。
毎年催されている人気投票の投票対象を決めるために利用されていたりする。

そして、以下のリンク先で確認したところ、投票先は208ある。
toho-vote.info

素直にやれば N = 208 を人力（！）ソートすることになる。
（※ 実際には前準備として、作品単位・個別キャラ単位で対象を枝刈りすることができる）

さて、この例で全件ソートと部分ソートで交換回数を比較してみる。
持ち票は 7 ということで、部分ソートでは k = 7。

Compareを観測するIComparer<T>を使って計測。

// カウントするだけならこんな仕組みでなくていいけれど、転用
public sealed class ActionComparer<T> : IComparer<T>
{
    private readonly IComparer<T> comparer;
    private readonly Action<T?, T?, int> action;

    public ActionComparer(Action<T?, T?, int> action) : this(action, Comparer<T>.Default) { }
    public ActionComparer(Action<T?, T?, int> action, IComparer<T> comparer)
    {
        this.comparer = comparer;
        this.action = action;
    }

    public int Compare(T? x, T? y)
    {
        var result = comparer.Compare(x, y);
        action(x, y, result);
        return result;
    }
}

以下では記事 (1), (2) に登場したメソッドを注記なく使用している。

const int N = 208;
const int k = 7;

Span<int> span = Enumerable.Range(0, N).ToArray();
SortUtil.Shuffle(span);
Span<int> spanAll = span.ToArray().AsSpan();
Span<int> spanPartial = span.ToArray().AsSpan();
int countCompAll = 0;
var compAll = new ActionComparer<int>((_, _, _) => ++countCompAll);
int countCompPartial = 0;
var compPartial = new ActionComparer<int>((_, _, _) => ++countCompPartial);

spanAll.Sort(compAll);
SortUtil.PartialSort(spanPartial, k, compPartial);

Console.WriteLine($"全件ソート: Compare回数 -> {countCompAll}");
Console.WriteLine($"部分ソート: Compare回数 -> {countCompPartial}");

// 全件ソート: Compare回数 -> 1647
// 部分ソート: Compare回数 -> 296

計算量オーダーは（たぶん）O(n logn) と O(n logk) 。
計算量オーダーが具体的な数値を求めるものじゃないと知りつつ雰囲気を掴むために代入してみると（logの底を 2）、208 * log(208) ≒ 1602、 208 * log(7) ≒ 584。

人間にとって数百の差は大きい。

―― と思いつつ、そもそも論として相対的な差以前に、絶対的な回数が数百ともなると人間にはキツい感じがする。
やるならNの枝刈りはほぼ必須。

比較回数の感触を見ると、ランキング的なものが好きな人が多い一方で、キャラソートがそこまで一般的じゃないのも腑に落ちる。

人間が力尽きる膨大な計算をやってくれるコンピュータの偉大さを改めて感じて終わり。