Zenn
Happy ElementsPublicationへの投稿
📊

【C#】In-Place Merge Sort を実装してみた

h_miki
2023/12/17に公開
C#
sort
algorithm
tech

「Happy Elements Advent Calendar 2023」 12月17日の記事です。

はじめに

はじめまして。私はHappy Elements株式会社 カカリアスタジオで新規タイトルを開発中のチームで働いている h_miki です。

本記事では、配列の拡張メソッドとして In-Place Merge Sort を実装し、実行速度やメモリ消費量を計測してみたいと思います。[1]

なお、前提として Merge Sort についての基本的な知識はあるものとします。

実装にあたって

In-Place Merge Sort の実装には、部分配列に対する操作が必要です。

部分配列の操作には、操作範囲の先頭と末尾のインデックスを管理する方法などもありますが、今回はわかりやすさ重視で Span<T> を活用しようと思います。

メソッドの実装は Span<T> に対しておこない、配列用のメソッドは単に Span<T> 用のメソッドを呼び出すことにします。

public static void InPlaceMergeSort<T>(this T[] sources, Comparison<T> comparison)
{
    // ここでは Span<T> に変換して, メソッドを呼び出しているだけ.
    sources.AsSpan().InPlaceMergeSort(comparison);
}

In-Place Merge Sort の実装

外枠の実装

基本の構造はよくある Merge Sort と同じで、再帰的に呼び出すメソッドを In-Place なものに置き換えるだけです。

末尾でおこなっているマージ(※)の実装については、次の項目で説明します。

public static void InPlaceMergeSort<T>(Span<T> sources, Comparison<T> comparison)
{
    if (sources.Length < 2)
    {
        return;
    }

    if (sources.Length == 2)
    {
        if (comparison(sources[0], sources[1]) > 0)
        {
            (sources[0], sources[1]) = (sources[1], sources[0]);
        }
        return;
    }

    var halfLength = sources.Length / 2;
    sources.Slice(0, halfLength).InPlaceMergeSort(comparison);
    sources.Slice(halfLength).InPlaceMergeSort(comparison);
    sources.InPlaceMerge(halfLength, comparison);  // ※
}

In-Place Merge の実装

実装方法はいろいろと考えられそうですが、ここでは以下の考え方をベースに実装します。

  1. 前半の部分配列を L 、後半の部分配列を R とする。
  2. L[i] > R[0] が成り立つ最小の i を求める。
  3. L の先頭を i だけずらして L の範囲を縮める。
  4. L[0] <= R[j] が成り立つ最小の j を求める。
  5. R の先頭を j だけずらして R の範囲を縮める(= L の長さが j だけ伸びる)。
  6. L を j 回右に回転させる。
  7. L の先頭を j だけずらして L の範囲を縮める。
  8. L と R の範囲が重なるか R の範囲が無くなるまで、手順 1. ～ 6. を繰り返す。

手順 1. の操作にあたる UpperBound 、手順 3. の操作にあたる LowerBound 、手順 5. の部分配列の右回転の実装については、以降の項目で説明します。

public static void InPlaceMerge<T>(this Span<T> sources, int rightIndex, Comparison<T> comparison)
{
    if (sources.Length < 2 || rightIndex <= 0 || sources.Length <= rightIndex)
    {
        return;
    }

    if (sources.Length == 2)
    {
        if (comparison(sources[0], sources[1]) > 0)
        {
            (sources[0], sources[1]) = (sources[1], sources[0]);
        }
        return;
    }

    var leftIndex = 0;
    while (leftIndex < rightIndex && rightIndex < sources.Length)
    {
        var leftSpan = sources.Slice(leftIndex, rightIndex - leftIndex);
        var rightSpan = sources.Slice(rightIndex);

        if (comparison(leftSpan[0], rightSpan[0]) <= 0)
        {
            leftIndex += leftSpan.UpperBound(rightSpan[0], comparison);
            continue;
        }

        var rotateCount = rightSpan.LowerBound(leftSpan[0], comparison);
        rightIndex += rotateCount;
        sources.Slice(leftIndex, rightIndex - leftIndex).RotateRight(rotateCount);
        leftIndex += rotateCount;
    }
}

LowerBound と UpperBound の実装

LowerBound と UpperBound の説明は以下の通りです。

LowerBound:

  • 指定された要素以上の値が現れる最初の位置のインデックスを返します。
  • 存在しない場合は、最後尾のインデックス + 1 (= Length) を返します。

UpperBound:

  • 指定された要素を超える値が現れる最初の位置のインデックスを返します。
  • 存在しない場合は、最後尾のインデックス + 1 (= Length) を返します。

メソッド名の由来は C++ の std::lower_bound と std::upper_bound です。

public static int LowerBound<T>(this Span<T> sources, T value, Comparison<T> comparison)
{
    var leftIndex = -1;
    var rightIndex = sources.Length;
    while (rightIndex - leftIndex > 1)
    {
        var middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
        if (comparison(sources[middleIndex], value) < 0)
        {
            leftIndex = middleIndex;
        }
        else
        {
            rightIndex = middleIndex;
        }
    }
    return rightIndex;
}

public static int UpperBound<T>(this Span<T> sources, T value, Comparison<T> comparison)
{
    var leftIndex = -1;
    var rightIndex = sources.Length;
    while (rightIndex - leftIndex > 1)
    {
        var middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
        if (comparison(sources[middleIndex], value) <= 0)
        {
            leftIndex = middleIndex;
        }
        else
        {
            rightIndex = middleIndex;
        }
    }
    return rightIndex;
}

部分配列の右回転の実装

ここでは実装の簡単さを優先して、Span<T>.Reverse() を 3 回実行することで実現します。

public static void RotateRight<T>(this Span<T> sources, int rotateCount)
{
    sources.Reverse();
    sources.Slice(rotateCount).Reverse();
    sources.Slice(0, rotateCount).Reverse();
}

これで必要なメソッドがすべてそろいました。

計測結果

BenchmarkDotNet を使用して、以下のソートと簡単に比較してみます。

  • LINQ の OrderBy
  • Insertion Sort [2]
  • In-Place Merge Sort (今回実装したもの)

ソート対象は (int key, string value) の配列(要素数: 100,000)です。

| Method           | Mean         | Error      | StdDev    | Ratio  | RatioSD | Allocated | Alloc Ratio |
|----------------- |-------------:|-----------:|----------:|-------:|--------:|----------:|------------:|
| LinqOrderBy      |     12.45 ms |   1.736 ms |  0.095 ms |   1.00 |    0.00 | 4000912 B |       1.000 |
| InsertionSort    | 11,974.64 ms | 805.288 ms | 44.141 ms | 961.64 |   10.02 |     736 B |       0.000 |
| InPlaceMergeSort |    423.56 ms |  71.764 ms |  3.934 ms |  34.01 |    0.28 |     736 B |       0.000 |

きちんとした計測ではありませんが、傾向として

  • LINQ の OrderBy が一番速いが、メモリ消費量が一番多い
  • In-Place Merge Sort は Insertion Sort とメモリ消費量は同じぐらいだが、In-Place Merge Sort の方が速い

ぐらいは言えそうです。

感想

いろいろと改善の余地はあると思いますが、アルゴリズムの全体像はつかめたと思います。

通常は LINQ の OrderBy で十分だと思いますが、何かの機会にお役に立てば幸いです。

参考情報

本記事を執筆するにあたり、以下を参考にいたしました。
有益な情報を公開していただき、ありがとうございます。

脚注

  1. 今回 In-Place Merge Sort を実装しようと思った理由は、単純に「いつか実装してみたいと思っていたから」です。 ↩︎

  2. よくある挿入ソートなので、実装は省略します。 ↩︎

Happy Elements
Happy ElementsPublication

京都でスマートフォン向けゲームを開発・運営している Happy Elements カカリアスタジオの Publication です

Discussion