Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 16691] ファイルの概要

このコミットは、Go言語の標準ライブラリ sort パッケージに安定ソート (stable sorting) の実装を追加するものです。具体的には、ボトムアップマージソートと、P.-S. KimおよびA. KutznerによるSymMergeアルゴリズムを用いたインプレースマージを組み合わせています。これにより、同値の要素の相対的な順序を保持したままソートを行う機能が提供されます。

コミット

commit 1135ef153f41915d18d5435d5ac2e1345b019d6e
Author: Volker Dobler <dr.volker.dobler@gmail.com>
Date:   Mon Jul 1 21:20:33 2013 -0400

    sort: implement stable sorting
    
    This CL provides stable in-place sorting by use of
    bottom up merge sort with in-place merging done by
    the SymMerge algorithm from P.-S. Kim and A. Kutzner.
    
    The additional space needed for stable sorting (in the form of
    stack space) is logarithmic in the inputs size n.
    Number of calls to Less and Swap grow like O(n * log n) and
    O(n * log n * log n):
    Stable sorting random data uses significantly more calls
    to Swap than the unstable quicksort implementation (5 times more
    on n=100, 10 times more on n=1e4 and 23 times more on n=1e8).
    The number of calls to Less is practically the same for Sort and
    Stable.
    
    Stable sorting 1 million random integers takes 5 times longer
    than using Sort.
    
    BenchmarkSortString1K      50000       328662 ns/op
    BenchmarkStableString1K    50000       380231 ns/op  1.15 slower
    BenchmarkSortInt1K         50000       157336 ns/op
    BenchmarkStableInt1K         500       191167 ns/op  1.22 slower
    BenchmarkSortInt64K         1000     14466297 ns/op
    BenchmarkStableInt64K        500     16190266 ns/op  1.12 slower
    
    BenchmarkSort1e2          200000        64923 ns/op
    BenchmarkStable1e2         50000       167128 ns/op  2.57 slower
    BenchmarkSort1e4            1000     14540613 ns/op
    BenchmarkStable1e4           100     58117289 ns/op  4.00 slower
    BenchmarkSort1e6               5   2429631508 ns/op
    BenchmarkStable1e6             1  12077036952 ns/op  4.97 slower
    
    R=golang-dev, bradfitz, iant, 0xjnml, rsc
    CC=golang-dev
    https://golang.org/cl/9612044

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/1135ef153f41915d18d5435d5ac2e1345b019d6e

元コミット内容

このコミットは、Go言語の sort パッケージに安定ソート機能を追加します。これは、P.-S. KimとA. KutznerによるSymMergeアルゴリズムを用いたボトムアップマージソートとインプレースマージによって実現されます。安定ソートに必要な追加のスタック空間は入力サイズ n に対して対数的です。Less メソッドの呼び出し回数は O(n log n)、Swap メソッドの呼び出し回数は O(n log n log n) で増加します。

ベンチマーク結果によると、安定ソートは不安定なクイックソート実装と比較して、特に Swap 呼び出し回数が大幅に増加します（n=1e8 で23倍）。Less 呼び出し回数は両者でほぼ同じです。全体的な実行時間では、100万個のランダムな整数を安定ソートする場合、通常のソートの約5倍の時間がかかります。

変更の背景

Go言語の sort パッケージには、これまで不安定なソートアルゴリズム（主にクイックソート）が提供されていました。しかし、特定のアプリケーションでは、同値の要素の相対的な順序を保持する「安定ソート」が必要となる場合があります。例えば、複数のキーでソートを行う場合、安定ソートであれば後続のソートが先行のソート結果を破壊することなく、期待通りの順序を維持できます。

このコミットは、このような安定ソートのニーズに応えるために導入されました。特に、追加のメモリ使用量を最小限に抑えつつ、実用的なパフォーマンスを持つインプレース安定ソートアルゴリズムの導入が目指されました。コミットメッセージには、他の安定ソートアルゴリズムの評価も含まれており、既存のソリューションがGoの sort.Interface の制約（Swap 操作のみが利用可能であること）や、安定性、インプレース性、パフォーマンスのバランスにおいて課題があったことが示唆されています。

前提知識の解説

ソートアルゴリズム

ソートアルゴリズムは、データの集合を特定の順序（昇順または降順）に並べ替えるための手順です。

  • 安定ソート (Stable Sort): ソート対象の要素の中に、比較基準において等しい値を持つものが複数存在する場合、それらの要素のソート前の相対的な順序がソート後も保持されるソートアルゴリズムを指します。例えば、[(A, 1), (B, 2), (C, 1)] を値でソートする場合、安定ソートでは [(A, 1), (C, 1), (B, 2)] のように、値が同じ A と C の元の順序が保たれます。不安定ソートでは [(C, 1), (A, 1), (B, 2)] のようになる可能性もあります。
  • 不安定ソート (Unstable Sort): 同値の要素の相対的な順序が保持されないソートアルゴリズムです。Goの sort.Sort は、このコミット以前は主にクイックソートをベースとした不安定ソートでした。
  • インプレースソート (In-place Sort): ソートを行う際に、入力データが格納されているメモリ領域以外に、ごくわずかな追加メモリ（通常は O(1) または O(log n)）しか必要としないソートアルゴリズムです。
  • マージソート (Merge Sort): 分割統治法に基づくソートアルゴリズムです。データを半分に分割し、それぞれを再帰的にソートし、その後ソートされた2つの部分リストをマージして1つのソート済みリストを作成します。
    • ボトムアップマージソート (Bottom-up Merge Sort): 再帰を使わず、小さなソート済みサブリストから始めて、徐々に大きなサブリストをマージしていくマージソートの一種です。これにより、スタックオーバーフローのリスクを回避できます。
  • クイックソート (Quicksort): 分割統治法に基づくソートアルゴリズムで、通常は非常に高速ですが、安定ではありません。

計算量 (Complexity)

  • 時間計算量 (Time Complexity): アルゴリズムの実行時間が入力サイズ n の増加に伴ってどのように変化するかを示す指標です。O(n log n) は効率的なソートアルゴリズムの典型的な時間計算量です。O(n log n log n) は O(n log^2 n) とも書かれ、O(n log n) よりもわずかに悪い性能を示します。
  • 空間計算量 (Space Complexity): アルゴリズムの実行に必要な追加メモリ量が入力サイズ n の増加に伴ってどのように変化するかを示す指標です。O(log n) は対数的な空間使用量を示し、非常に効率的です。

sort.Interface

Go言語の sort パッケージは、ジェネリックなソートを可能にするために sort.Interface インターフェースを定義しています。このインターフェースは以下の3つのメソッドを持ちます。

  • Len() int: ソート対象の要素数を返します。
  • Less(i, j int) bool: インデックス i の要素がインデックス j の要素よりも小さい場合に true を返します。
  • Swap(i, j int): インデックス i と j の要素を入れ替えます。

このインターフェースの制約（特に Swap しか要素の移動方法がないこと）が、インプレース安定ソートの実装を複雑にする要因となります。

技術的詳細

このコミットで導入された安定ソートは、以下の技術的要素を組み合わせています。

  1. ボトムアップマージソート: 再帰的な呼び出しを避け、スタック空間を節約するために採用されています。これは、まず小さなブロック（blockSize）ごとに挿入ソートを行い、その後、ブロックサイズを倍々にしながらマージを繰り返すことで実現されます。
  2. インプレースマージ: マージソートの主要な課題の一つは、マージ操作に追加の作業用配列が必要となることです。このコミットでは、P.-S. KimとA. KutznerによるSymMergeアルゴリズムを使用して、追加のメモリをほとんど使わずにインプレースでマージを行います。
  3. SymMergeアルゴリズム: このアルゴリズムは、2つのソート済みサブシーケンス data[a:m] と data[m:b] をインプレースでマージするために設計されています。その核心は、適切な位置に要素を配置するために、ブロック回転 (block rotation) を効率的に利用することです。コミットメッセージでは、このアルゴリズムが data.Less への O(M*log(N/M + 1)) 回の呼び出しと、data.Swap への O((M+N)*log(M)) 回の呼び出しを必要とすると説明されています（ここで M と N はマージされる2つのサブシーケンスの長さ）。
  4. rotate 関数: SymMergeアルゴリズムの重要な補助関数として rotate が実装されています。これは、配列内の連続する2つのブロック u = data[a:m] と v = data[m:b] を x u v y から x v u y の形に回転させるものです。この操作は data.Swap を最大 b-a 回呼び出すことで行われます。コミットメッセージでは、この回転が Swap 操作の観点から最適であると説明されています。
  5. 計算量の分析: コミットメッセージには、安定ソート全体の計算量に関する詳細な分析が含まれています。
    • Less 呼び出し回数: O(n log n)
    • Swap 呼び出し回数: O(n log^2 n) (または O(n log n log n)) これは、マージソートの各イテレーションで Less 呼び出しが O(n)、Swap 呼び出しが O(n * i)（i はイテレーション番号）となるため、合計で log n 回のイテレーションを通じて O(n log n) と O(n log^2 n) になるという導出が示されています。
  6. パフォーマンス特性: ベンチマーク結果が示唆するように、この安定ソート実装は、Goの既存の不安定ソート（クイックソート）と比較して、特に Swap 操作のオーバーヘッドにより、実行時間が長くなります。これは、インプレース安定ソートの一般的な特性であり、追加のメモリを使用しないことと引き換えに、要素の移動回数が増える傾向があるためです。

コアとなるコードの変更箇所

src/pkg/sort/sort.go

  • Stable(data Interface) 関数が追加されました。
    • これはボトムアップマージソートのメインロジックを実装しています。
    • まず、小さなブロック（blockSize = 20）ごとに insertionSort を適用します。
    • その後、blockSize を倍々にしながら symMerge を呼び出してマージを繰り返します。
  • symMerge(data Interface, a, m, b int) 関数が追加されました。
    • P.-S. KimとA. KutznerのSymMergeアルゴリズムを実装しています。
    • data[a:m] と data[m:b] の2つのソート済みサブシーケンスをインプレースでマージします。
    • 内部で rotate 関数を呼び出します。
    • 再帰的に自身を呼び出すことで、マージ処理を分割します。
  • rotate(data Interface, a, m, b int) 関数が追加されました。
    • data[a:m] と data[m:b] の2つの連続するブロックを回転させます。
    • swapRange を使用して要素を効率的に入れ替えます。
  • swapRange(data Interface, a, b, n int) 関数が追加されました。
    • data[a:a+n] と data[b:b+n] の範囲の要素を入れ替えます。

src/pkg/sort/sort_test.go

  • Stable 関数用のベンチマークテストが追加されました (BenchmarkStableString1K, BenchmarkStableInt1K, BenchmarkStableInt64K, BenchmarkStable1e2, BenchmarkStable1e4, BenchmarkStable1e6)。
  • TestStableBM が追加され、testBentleyMcIlroy 関数が Stable 関数をテストできるように修正されました。
  • TestStableInts が追加され、基本的な安定ソートの機能テストを行います。
  • intPairs 型と関連メソッド (Len, Less, Swap, initB, inOrder) が追加されました。これは、安定性をテストするために、値が同じ要素の元の順序を追跡するためのヘルパー構造体です。
  • TestStability が追加され、ランダムなデータ、既にソートされたデータ、逆順にソートされたデータに対して Stable 関数の安定性を検証します。
  • TestCountStableOps が追加され、Stable 関数が実行する Swap と Less の操作回数をカウントし、ログに出力します。

コアとなるコードの解説

Stable 関数

func Stable(data Interface) {
	n := data.Len()
	blockSize := 20 // 小さなブロックのサイズ
	a, b := 0, blockSize
	for b <= n {
		insertionSort(data, a, b) // まず小さなブロックを挿入ソート
		a = b
		b += blockSize
	}
	insertionSort(data, a, n) // 残りの部分を挿入ソート

	for blockSize < n { // ボトムアップマージソートのループ
		a, b = 0, 2*blockSize
		for b <= n {
			symMerge(data, a, a+blockSize, b) // 2つのブロックをマージ
			a = b
			b += 2 * blockSize
		}
		symMerge(data, a, a+blockSize, n) // 残りの部分をマージ
		blockSize *= 2 // ブロックサイズを倍にする
	}
}

Stable 関数は、ボトムアップマージソートの主要なエントリポイントです。

  1. 初期挿入ソート: まず、配列を小さな固定サイズのブロック（blockSize）に分割し、それぞれのブロックを insertionSort でソートします。挿入ソートは小さな配列に対しては効率的であり、この初期ステップはマージソートの効率を向上させます。
  2. ボトムアップマージ: その後、blockSize を2倍にしながらループを回します。各イテレーションでは、現在の blockSize の2倍の長さのセグメントを対象に、symMerge 関数を呼び出して2つのソート済みサブ配列をマージしていきます。これにより、徐々に大きなソート済みセグメントが構築され、最終的に配列全体がソートされます。

symMerge 関数

func symMerge(data Interface, a, m, b int) {
	if a >= m || m >= b { // 無効な範囲またはマージ不要な場合
		return
	}

	mid := a + (b-a)/2 // 全体の中心
	n := mid + m       // マージ後の右側の開始点（仮）
	start := 0
	if m > mid { // 左側のサブシーケンスが右側より長い場合
		start = n - b
		r, p := mid, n-1
		for start < r { // 二分探索で回転の開始点を決定
			c := start + (r-start)/2
			if !data.Less(p-c, c) {
				start = c + 1
			} else {
				r = c
			}
		}
	} else { // 右側のサブシーケンスが左側より長いか同じ場合
		start = a
		r, p := m, n-1
		for start < r { // 二分探索で回転の開始点を決定
			c := start + (r-start)/2
			if !data.Less(p-c, c) {
				start = c + 1
			} else {
				r = c
			}
		}
	}
	end := n - start
	rotate(data, start, m, end) // 決定した範囲を回転
	symMerge(data, a, start, mid) // 左半分を再帰的にマージ
	symMerge(data, mid, end, b)   // 右半分を再帰的にマージ
}

symMerge は、安定ソートの核心となるインプレースマージアルゴリズムです。 data[a:m] と data[m:b] の2つのソート済み部分配列をマージします。 この関数は再帰的に動作し、マージ対象の範囲を分割しながら処理を進めます。 主要なステップは、rotate 関数を呼び出す前に、二分探索を用いて適切な回転の開始点を見つけることです。この回転によって、マージされるべき要素が正しい相対位置に移動します。

rotate 関数

func rotate(data Interface, a, m, b int) {
	i := m - a // 左ブロックの長さ
	if i == 0 {
		return
	}
	j := b - m // 右ブロックの長さ
	if j == 0 {
		return
	}

	if i == j { // 両ブロックの長さが同じ場合
		swapRange(data, a, m, i) // 一括で入れ替え
		return
	}

	p := a + i
	for i != j { // ブロックの長さが異なる場合、GCDベースの回転
		if i > j {
			swapRange(data, p-i, p, j)
			i -= j
		} else {
			swapRange(data, p-i, p+j-i, i)
			j -= i
		}
	}
	swapRange(data, p-i, p, i) // 最終的な入れ替え
}

rotate 関数は、配列内の2つの連続するブロック data[a:m] と data[m:b] を効率的に入れ替えるためのユーティリティです。例えば、[X][A][B][Y] のような配列で [A] が data[a:m]、[B] が data[m:b] だとすると、これを [X][B][A][Y] のように変換します。 この関数は、ブロックの長さ i と j に応じて異なる戦略を取ります。長さが同じ場合は swapRange で一括で入れ替えます。長さが異なる場合は、ユークリッドの互除法に似た方法で、より短いブロックを繰り返しスワップすることで回転を実現します。これにより、Swap 操作の回数を最小限に抑えつつ、インプレースでブロックを移動させることができます。

関連リンク

参考にした情報源リンク

  • P.-S. Kim and A. Kutzner, "Stable Minimum Storage Merging by Symmetric Comparisons", Algorithms - ESA 2004, volume 3221 of Lecture Notes in Computer Science, pages 714-723. Springer, 2004. (SymMergeアルゴリズムの原論文)
  • Jyrki Katajainen, Tomi A. Pasanen and Jukka Teuhola, "Practical in-place mergesort", Nordic Journal of Computing 3,1 (1996), 27-40. (コミットメッセージで言及されている他のアルゴリズム)
  • J.I. Munro and V. Raman, "Fast Stable In-Place Sorting with O(n) Data Moves", Algorithmica (1996) 16, 115-160. (コミットメッセージで言及されている他のアルゴリズム)
  • Denham Coates-Evely, "In-Place Merging Algorithms", Department of Computer Science, Kings College, January 2004. (インプレースマージアルゴリズムに関するレビュー)
  • Go言語のコードレビューシステム (Gerrit): https://golang.org/cl/9612044 (このコミットのコードレビューページ)

[インデックス 16691] ファイルの概要

このコミットは、Go言語の標準ライブラリ sort パッケージに安定ソート (stable sorting) の実装を追加するものです。具体的には、ボトムアップマージソートと、P.-S. KimおよびA. KutznerによるSymMergeアルゴリズムを用いたインプレースマージを組み合わせています。これにより、同値の要素の相対的な順序を保持したままソートを行う機能が提供されます。

コミット

commit 1135ef153f41915d18d5435d5ac2e1345b019d6e
Author: Volker Dobler <dr.volker.dobler@gmail.com>
Date:   Mon Jul 1 21:20:33 2013 -0400

    sort: implement stable sorting
    
    This CL provides stable in-place sorting by use of
    bottom up merge sort with in-place merging done by
    the SymMerge algorithm from P.-S. Kim and A. Kutzner.
    
    The additional space needed for stable sorting (in the form of
    stack space) is logarithmic in the inputs size n.
    Number of calls to Less and Swap grow like O(n * log n) and
    O(n * log n * log n):
    Stable sorting random data uses significantly more calls
    to Swap than the unstable quicksort implementation (5 times more
    on n=100, 10 times more on n=1e4 and 23 times more on n=1e8).
    The number of calls to Less is practically the same for Sort and
    Stable.
    
    Stable sorting 1 million random integers takes 5 times longer
    than using Sort.
    
    BenchmarkSortString1K      50000       328662 ns/op
    BenchmarkStableString1K    50000       380231 ns/op  1.15 slower
    BenchmarkSortInt1K         50000       157336 ns/op
    BenchmarkStableInt1K         500       191167 ns/op  1.22 slower
    BenchmarkSortInt64K         1000     14466297 ns/op
    BenchmarkStableInt64K        500     16190266 ns/op  1.12 slower
    
    BenchmarkSort1e2          200000        64923 ns/op
    BenchmarkStable1e2         50000       167128 ns/op  2.57 slower
    BenchmarkSort1e4            1000     14540613 ns/op
    BenchmarkStable1e4           100     58117289 ns/op  4.00 slower
    BenchmarkSort1e6               5   2429631508 ns/op
    BenchmarkStable1e6             1  12077036952 ns/op  4.97 slower
    
    R=golang-dev, bradfitz, iant, 0xjnml, rsc
    CC=golang-dev
    https://golang.org/cl/9612044

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/1135ef153f41915d18d5435d5ac2e1345b019d6e

元コミット内容

このコミットは、Go言語の sort パッケージに安定ソート機能を追加します。これは、P.-S. KimとA. KutznerによるSymMergeアルゴリズムを用いたボトムアップマージソートとインプレースマージによって実現されます。安定ソートに必要な追加のスタック空間は入力サイズ n に対して対数的です。Less メソッドの呼び出し回数は O(n log n)、Swap メソッドの呼び出し回数は O(n log n log n) で増加します。

ベンチマーク結果によると、安定ソートは不安定なクイックソート実装と比較して、特に Swap 呼び出し回数が大幅に増加します（n=1e8 で23倍）。Less 呼び出し回数は両者でほぼ同じです。全体的な実行時間では、100万個のランダムな整数を安定ソートする場合、通常のソートの約5倍の時間がかかります。

変更の背景

Go言語の sort パッケージには、これまで不安定なソートアルゴリズム（主にクイックソート）が提供されていました。しかし、特定のアプリケーションでは、同値の要素の相対的な順序を保持する「安定ソート」が必要となる場合があります。例えば、複数のキーでソートを行う場合、安定ソートであれば後続のソートが先行のソート結果を破壊することなく、期待通りの順序を維持できます。

このコミットは、このような安定ソートのニーズに応えるために導入されました。特に、追加のメモリ使用量を最小限に抑えつつ、実用的なパフォーマンスを持つインプレース安定ソートアルゴリズムの導入が目指されました。コミットメッセージには、他の安定ソートアルゴリズムの評価も含まれており、既存のソリューションがGoの sort.Interface の制約（Swap 操作のみが利用可能であること）や、安定性、インプレース性、パフォーマンスのバランスにおいて課題があったことが示唆されています。

前提知識の解説

ソートアルゴリズム

ソートアルゴリズムは、データの集合を特定の順序（昇順または降順）に並べ替えるための手順です。

  • 安定ソート (Stable Sort): ソート対象の要素の中に、比較基準において等しい値を持つものが複数存在する場合、それらの要素のソート前の相対的な順序がソート後も保持されるソートアルゴリズムを指します。例えば、[(A, 1), (B, 2), (C, 1)] を値でソートする場合、安定ソートでは [(A, 1), (C, 1), (B, 2)] のように、値が同じ A と C の元の順序が保たれます。不安定ソートでは [(C, 1), (A, 1), (B, 2)] のようになる可能性もあります。
  • 不安定ソート (Unstable Sort): 同値の要素の相対的な順序が保持されないソートアルゴリズムです。Goの sort.Sort は、このコミット以前は主にクイックソートをベースとした不安定ソートでした。
  • インプレースソート (In-place Sort): ソートを行う際に、入力データが格納されているメモリ領域以外に、ごくわずかな追加メモリ（通常は O(1) または O(log n)）しか必要としないソートアルゴリズムです。
  • マージソート (Merge Sort): 分割統治法に基づくソートアルゴリズムです。データを半分に分割し、それぞれを再帰的にソートし、その後ソートされた2つの部分リストをマージして1つのソート済みリストを作成します。
    • ボトムアップマージソート (Bottom-up Merge Sort): 再帰を使わず、小さなソート済みサブリストから始めて、徐々に大きなサブリストをマージしていくマージソートの一種です。これにより、スタックオーバーフローのリスクを回避できます。
  • クイックソート (Quicksort): 分割統治法に基づくソートアルゴリズムで、通常は非常に高速ですが、安定ではありません。

計算量 (Complexity)

  • 時間計算量 (Time Complexity): アルゴリズムの実行時間が入力サイズ n の増加に伴ってどのように変化するかを示す指標です。O(n log n) は効率的なソートアルゴリズムの典型的な時間計算量です。O(n log n log n) は O(n log^2 n) とも書かれ、O(n log n) よりもわずかに悪い性能を示します。
  • 空間計算量 (Space Complexity): アルゴリズムの実行に必要な追加メモリ量が入力サイズ n の増加に伴ってどのように変化するかを示す指標です。O(log n) は対数的な空間使用量を示し、非常に効率的です。

sort.Interface

Go言語の sort パッケージは、ジェネリックなソートを可能にするために sort.Interface インターフェースを定義しています。このインターフェースは以下の3つのメソッドを持ちます。

  • Len() int: ソート対象の要素数を返します。
  • Less(i, j int) bool: インデックス i の要素がインデックス j の要素よりも小さい場合に true を返します。
  • Swap(i, j int): インデックス i と j の要素を入れ替えます。

このインターフェースの制約（特に Swap しか要素の移動方法がないこと）が、インプレース安定ソートの実装を複雑にする要因となります。

技術的詳細

このコミットで導入された安定ソートは、以下の技術的要素を組み合わせています。

  1. ボトムアップマージソート: 再帰的な呼び出しを避け、スタック空間を節約するために採用されています。これは、まず小さなブロック（blockSize）ごとに挿入ソートを行い、その後、ブロックサイズを倍々にしながらマージを繰り返すことで実現されます。
  2. インプレースマージ: マージソートの主要な課題の一つは、マージ操作に追加の作業用配列が必要となることです。このコミットでは、P.-S. KimとA. KutznerによるSymMergeアルゴリズムを使用して、追加のメモリをほとんど使わずにインプレースでマージを行います。
  3. SymMergeアルゴリズム: このアルゴリズムは、2つのソート済みサブシーケンス data[a:m] と data[m:b] をインプレースでマージするために設計されています。その核心は、適切な位置に要素を配置するために、ブロック回転 (block rotation) を効率的に利用することです。コミットメッセージでは、このアルゴリズムが data.Less への O(M*log(N/M + 1)) 回の呼び出しと、data.Swap への O((M+N)*log(M)) 回の呼び出しを必要とすると説明されています（ここで M と N はマージされる2つのサブシーケンスの長さ）。
  4. rotate 関数: SymMergeアルゴリズムの重要な補助関数として rotate が実装されています。これは、配列内の連続する2つのブロック u = data[a:m] と v = data[m:b] を x u v y から x v u y の形に回転させるものです。この操作は data.Swap を最大 b-a 回呼び出すことで行われます。コミットメッセージでは、この回転が Swap 操作の観点から最適であると説明されています。
  5. 計算量の分析: コミットメッセージには、安定ソート全体の計算量に関する詳細な分析が含まれています。
    • Less 呼び出し回数: O(n log n)
    • Swap 呼び出し回数: O(n log^2 n) (または O(n log n log n)) これは、マージソートの各イテレーションで Less 呼び出しが O(n)、Swap 呼び出しが O(n * i)（i はイテレーション番号）となるため、合計で log n 回のイテレーションを通じて O(n log n) と O(n log^2 n) になるという導出が示されています。
  6. パフォーマンス特性: ベンチマーク結果が示唆するように、この安定ソート実装は、Goの既存の不安定ソート（クイックソート）と比較して、特に Swap 操作のオーバーヘッドにより、実行時間が長くなります。これは、インプレース安定ソートの一般的な特性であり、追加のメモリを使用しないことと引き換えに、要素の移動回数が増える傾向があるためです。

コアとなるコードの変更箇所

src/pkg/sort/sort.go

  • Stable(data Interface) 関数が追加されました。
    • これはボトムアップマージソートのメインロジックを実装しています。
    • まず、小さなブロック（blockSize = 20）ごとに insertionSort を適用します。
    • その後、blockSize を倍々にしながら symMerge を呼び出してマージを繰り返します。
  • symMerge(data Interface, a, m, b int) 関数が追加されました。
    • P.-S. KimとA. KutznerのSymMergeアルゴリズムを実装しています。
    • data[a:m] と data[m:b] の2つのソート済みサブシーケンスをインプレースでマージします。
    • 内部で rotate 関数を呼び出します。
    • 再帰的に自身を呼び出すことで、マージ処理を分割します。
  • rotate(data Interface, a, m, b int) 関数が追加されました。
    • data[a:m] と data[m:b] の2つの連続するブロックを回転させます。
    • swapRange を使用して要素を効率的に入れ替えます。
  • swapRange(data Interface, a, b, n int) 関数が追加されました。
    • data[a:a+n] と data[b:b+n] の範囲の要素を入れ替えます。

src/pkg/sort/sort_test.go

  • Stable 関数用のベンチマークテストが追加されました (BenchmarkStableString1K, BenchmarkStableInt1K, BenchmarkStableInt64K, BenchmarkStable1e2, BenchmarkStable1e4, BenchmarkStable1e6)。
  • TestStableBM が追加され、testBentleyMcIlroy 関数が Stable 関数をテストできるように修正されました。
  • TestStableInts が追加され、基本的な安定ソートの機能テストを行います。
  • intPairs 型と関連メソッド (Len, Less, Swap, initB, inOrder) が追加されました。これは、安定性をテストするために、値が同じ要素の元の順序を追跡するためのヘルパー構造体です。
  • TestStability が追加され、ランダムなデータ、既にソートされたデータ、逆順にソートされたデータに対して Stable 関数の安定性を検証します。
  • TestCountStableOps が追加され、Stable 関数が実行する Swap と Less の操作回数をカウントし、ログに出力します。

コアとなるコードの解説

Stable 関数

func Stable(data Interface) {
	n := data.Len()
	blockSize := 20 // 小さなブロックのサイズ
	a, b := 0, blockSize
	for b <= n {
		insertionSort(data, a, b) // まず小さなブロックを挿入ソート
		a = b
		b += blockSize
	}
	insertionSort(data, a, n) // 残りの部分を挿入ソート

	for blockSize < n { // ボトムアップマージソートのループ
		a, b = 0, 2*blockSize
		for b <= n {
			symMerge(data, a, a+blockSize, b) // 2つのブロックをマージ
			a = b
			b += 2 * blockSize
		}
		symMerge(data, a, a+blockSize, n) // 残りの部分をマージ
		blockSize *= 2 // ブロックサイズを倍にする
	}
}

Stable 関数は、ボトムアップマージソートの主要なエントリポイントです。

  1. 初期挿入ソート: まず、配列を小さな固定サイズのブロック（blockSize）に分割し、それぞれのブロックを insertionSort でソートします。挿入ソートは小さな配列に対しては効率的であり、この初期ステップはマージソートの効率を向上させます。
  2. ボトムアップマージ: その後、blockSize を2倍にしながらループを回します。各イテレーションでは、現在の blockSize の2倍の長さのセグメントを対象に、symMerge 関数を呼び出して2つのソート済みサブ配列をマージしていきます。これにより、徐々に大きなソート済みセグメントが構築され、最終的に配列全体がソートされます。

symMerge 関数

func symMerge(data Interface, a, m, b int) {
	if a >= m || m >= b { // 無効な範囲またはマージ不要な場合
		return
	}

	mid := a + (b-a)/2 // 全体の中心
	n := mid + m       // マージ後の右側の開始点（仮）
	start := 0
	if m > mid { // 左側のサブシーケンスが右側より長い場合
		start = n - b
		r, p := mid, n-1
		for start < r { // 二分探索で回転の開始点を決定
			c := start + (r-start)/2
			if !data.Less(p-c, c) {
				start = c + 1
			} else {
				r = c
			}
		}
	} else { // 右側のサブシーケンスが左側より長いか同じ場合
		start = a
		r, p := m, n-1
		for start < r { // 二分探索で回転の開始点を決定
			c := start + (r-start)/2
			if !data.Less(p-c, c) {
				start = c + 1
			} else {
				r = c
			}
		}
	}
	end := n - start
	rotate(data, start, m, end) // 決定した範囲を回転
	symMerge(data, a, start, mid) // 左半分を再帰的にマージ
	symMerge(data, mid, end, b)   // 右半分を再帰的にマージ
}

symMerge は、安定ソートの核心となるインプレースマージアルゴリズムです。 data[a:m] と data[m:b] の2つのソート済み部分配列をマージします。 この関数は再帰的に動作し、マージ対象の範囲を分割しながら処理を進めます。 主要なステップは、rotate 関数を呼び出す前に、二分探索を用いて適切な回転の開始点を見つけることです。この回転によって、マージされるべき要素が正しい相対位置に移動します。

rotate 関数

func rotate(data Interface, a, m, b int) {
	i := m - a // 左ブロックの長さ
	if i == 0 {
		return
	}
	j := b - m // 右ブロックの長さ
	if j == 0 {
		return
	}

	if i == j { // 両ブロックの長さが同じ場合
		swapRange(data, a, m, i) // 一括で入れ替え
		return
	}

	p := a + i
	for i != j { // ブロックの長さが異なる場合、GCDベースの回転
		if i > j {
			swapRange(data, p-i, p, j)
			i -= j
		} else {
			swapRange(data, p-i, p+j-i, i)
			j -= i
		}
	}
	swapRange(data, p-i, p, i) // 最終的な入れ替え
}

rotate 関数は、配列内の2つの連続するブロック data[a:m] と data[m:b] を効率的に入れ替えるためのユーティリティです。例えば、[X][A][B][Y] のような配列で [A] が data[a:m]、[B] が data[m:b] だとすると、これを [X][B][A][Y] のように変換します。 この関数は、ブロックの長さ i と j に応じて異なる戦略を取ります。長さが同じ場合は swapRange で一括で入れ替えます。長さが異なる場合は、ユークリッドの互除法に似た方法で、より短いブロックを繰り返しスワップすることで回転を実現します。これにより、Swap 操作の回数を最小限に抑えつつ、インプレースでブロックを移動させることができます。

関連リンク

参考にした情報源リンク

  • P.-S. Kim and A. Kutzner, "Stable Minimum Storage Merging by Symmetric Comparisons", Algorithms - ESA 2004, volume 3221 of Lecture Notes in Computer Science, pages 714-723. Springer, 2004. (SymMergeアルゴリズムの原論文)
  • Jyrki Katajainen, Tomi A. Pasanen and Jukka Teuhola, "Practical in-place mergesort", Nordic Journal of Computing 3,1 (1996), 27-40. (コミットメッセージで言及されている他のアルゴリズム)
  • J.I. Munro and V. Raman, "Fast Stable In-Place Sorting with O(n) Data Moves", Algorithmica (1996) 16, 115-160. (コミットメッセージで言及されている他のアルゴリズム)
  • Denham Coates-Evely, "In-Place Merging Algorithms", Department of Computer Science, Kings College, January 2004. (インプレースマージアルゴリズムに関するレビュー)
  • Go言語のコードレビューシステム (Gerrit): https://golang.org/cl/9612044 (このコミットのコードレビューページ)