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

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

このコミットは、Go言語の標準ライブラリである sort パッケージ内の search.go ファイルに対する変更です。search.go は、ソートされたデータ構造に対して二分探索（binary search）を実行するための汎用的な Search 関数、および特定の型（int、float64、string）のスライスに対して二分探索を行うための便利なラッパー関数（SearchInts、SearchFloat64s、SearchStrings）を提供しています。このファイルは、効率的なデータ検索機能の基盤をなしています。

コミット

  • コミットハッシュ: 882eb608b1987e6a7b27256bd13d1c533798381d
  • Author: Shenghou Ma minux.ma@gmail.com
  • Date: Wed Nov 7 05:07:46 2012 +0800

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

https://github.com/golang/go/commit/882eb608b1987e6a7b27256bd13d1c533798381d

元コミット内容

sort: fix comment for various Search routines
Fixes #4205 (again).

R=r, 0xjnml
CC=golang-dev
https://golang.org/cl/6819082

変更の背景

このコミットの主な目的は、sort パッケージ内の Search 関数およびその関連ラッパー関数（SearchInts, SearchFloat64s, SearchStrings）のコメントを修正し、その動作、特に「要素が見つからなかった場合」の戻り値に関する説明を明確にすることです。コミットメッセージにある「Fixes #4205 (again).」という記述は、以前にもこの問題（Issue 4205）が提起され、その解決が試みられたものの、まだ説明が不十分であったか、誤解を招く可能性があったことを示唆しています。

二分探索関数において、探索対象の要素が見つからなかった場合にどのような値を返すかは、APIの使いやすさや誤用防止の観点から非常に重要です。多くのプログラミング言語やライブラリでは、見つからなかった場合に -1 を返す慣習がありますが、Goの sort.Search 関数は、要素が見つからなかった場合にスライスの長さ n を返します。この n という戻り値は、単に「見つからなかった」ことを示すだけでなく、「もし要素が存在するならば、その要素を挿入すべき位置」を示すという、より具体的な意味合いを持っています。この重要なニュアンスがコメントで十分に伝わっていなかったため、開発者が関数を正しく理解し、利用できるようにコメントの修正が必要とされました。

前提知識の解説

Go言語の sort パッケージ

sort パッケージは、Go言語でスライスやユーザー定義のコレクションをソートするための機能を提供します。これには、ソートアルゴリズム（例: クイックソート、ヒープソート）の実装だけでなく、ソートされたデータに対して効率的な検索を行うための二分探索関数も含まれます。

sort.Search 関数

sort.Search は、Go言語の sort パッケージが提供する汎用的な二分探索関数です。この関数は、以下のシグネチャを持ちます。

func Search(n int, f func(int) bool) int
  • n: 探索対象の範囲の長さ（要素数）。探索は [0, n) の範囲で行われます。
  • f func(int) bool: 探索の基準となる述語関数（predicate function）です。この関数は、インデックス i を受け取り、f(i) が true を返すかどうかを判定します。Search 関数は、f(i) が true を返す最初のインデックス i を見つけます。
    • f は、あるインデックス k まで false を返し、それ以降は true を返すという性質（単調性）を持つ必要があります。
    • もし f がすべての i に対して false を返す場合、Search は n を返します。
    • もし f がすべての i に対して true を返す場合、Search は 0 を返します。

この関数の特徴は、特定の値を直接検索するのではなく、「ある条件を満たす最初の要素」を検索する汎用的なメカニズムを提供することです。これにより、ソートされたスライス内の特定の値の検索だけでなく、条件を満たす範囲の開始位置を見つけるなど、より複雑な検索ロジックにも対応できます。

sort.SearchInts, sort.SearchFloat64s, sort.SearchStrings

これらは sort.Search の便利なラッパー関数で、それぞれ []int、[]float64、[]string 型のスライスに対して、特定の値を検索するために特化されています。これらの関数は内部で sort.Search を呼び出し、述語関数 f を適切に定義することで、ユーザーが直接 f を書く手間を省いています。

例: SearchInts(a []int, x int) は、ソートされた a の中で x を検索します。

二分探索における「見つからなかった場合」の戻り値

二分探索アルゴリズムにおいて、探索対象の要素が見つからなかった場合の戻り値にはいくつかの慣習があります。

  1. -1 を返す: 多くの言語やライブラリ（例: Javaの Arrays.binarySearch、C++の std::binary_search はブール値を返すため直接比較できないが、std::lower_bound などはイテレータを返す）で採用されている一般的な慣習です。これは「見つからなかった」ことを明確に示します。
  2. 挿入位置を返す: Goの sort.Search が採用している方式です。要素が見つからなかった場合、その要素をソート順を保って挿入するべきインデックスを返します。このインデックスは、スライスの長さ n になることもあります。この方式は、要素の存在確認だけでなく、新しい要素を効率的に挿入する際にも役立ちます。

このコミットは、Goの sort パッケージが後者の「挿入位置を返す」方式を採用していることを、より明確にドキュメント化することを目的としています。

技術的詳細

このコミットの技術的詳細は、主にコメントの文言の変更に集約されます。しかし、その変更が持つ意味は、Go言語のAPI設計思想と、二分探索関数の利用パターンに深く関連しています。

Search 関数のコメント修正

元のコメントでは、Search が n を返すことを「"not found" return value」と説明し、strings.Index の -1 と比較していました。修正後のコメントでは、この部分がより簡潔に「(Note that the "not found" return value is not -1 as in, for instance, strings.Index).」と変更されています。これは、n が単なる「見つからなかった」以上の意味を持つことを示唆しつつ、-1 とは異なることを強調しています。

ラッパー関数（SearchInts, SearchFloat64s, SearchStrings）のコメント修正

これらのラッパー関数のコメントは、より具体的な変更が加えられています。元のコメントでは、要素が見つからなかった場合に len(a) を返すことを「x is not present」と説明していました。修正後は、この説明が「The return value is the index to insert x if x is not present (it could be len(a)).」と変更されています。

この変更は非常に重要です。

  • 「挿入位置」の明確化: len(a) が単に「見つからなかった」ことを意味するだけでなく、「もし x が存在しない場合、x をソート順を保って挿入するべきインデックスである」という、より実用的な意味合いを持つことを明確にしています。
  • 利用パターンの示唆: このコメントにより、開発者は Search 関数群を単なる存在確認だけでなく、新しい要素をソートされたスライスに効率的に挿入する際の補助としても利用できることを理解しやすくなります。例えば、i := sort.SearchInts(a, x) の後、if i < len(a) && a[i] == x で要素の存在を確認し、else ブロックで i を挿入位置として利用するといったパターンが考えられます。

このコメントの修正は、APIの振る舞いを正確に反映し、開発者が関数をより効果的に利用するための重要なドキュメント改善と言えます。

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

diff --git a/src/pkg/sort/search.go b/src/pkg/sort/search.go
index 1eb22fabeb..8a2c1c33b1 100644
--- a/src/pkg/sort/search.go
+++ b/src/pkg/sort/search.go
@@ -12,8 +12,8 @@ package sort
 // f is false for some (possibly empty) prefix of the input range [0, n)
 // and then true for the (possibly empty) remainder; Search returns
 // the first true index.  If there is no such index, Search returns n.
-// (Note that the "not found" return value is n, the length of the input,
-// not -1 as in, for instance, strings.Index).
+// (Note that the "not found" return value is not -1 as in, for instance,
+// strings.Index).
 // Search calls f(i) only for i in the range [0, n).
 //
 // A common use of Search is to find the index i for a value x in
@@ -76,7 +76,8 @@ func Search(n int, f func(int) bool) int {
 // Convenience wrappers for common cases.
 
 // SearchInts searches for x in a sorted slice of ints and returns the index
-// as specified by Search. The return value is len(a) if x is not present.
+// as specified by Search. The return value is the index to insert x if x is
+// not present (it could be len(a)).
 // The slice must be sorted in ascending order.
 //
 func SearchInts(a []int, x int) int {
@@ -84,7 +85,8 @@ func SearchInts(a []int, x int) int {
 }
 
 // SearchFloat64s searches for x in a sorted slice of float64s and returns the index
-// as specified by Search.  The return value is len(a) if x is not present.
+// as specified by Search.  The return value is the index to insert x if x is not
+// present (it could be len(a)).
 // The slice must be sorted in ascending order.
 //
 func SearchFloat64s(a []float64, x float64) int {
@@ -92,7 +94,8 @@ func SearchFloat64s(a []float64, x float64) int {
 }
 
 // SearchStrings searches for x in a sorted slice of strings and returns the index
-// as specified by Search.  The return value is len(a) if x is not present.
+// as specified by Search.  The return value is the index to insert x if x is not
+// present (it could be len(a)).
 // The slice must be sorted in ascending order.
 //
 func SearchStrings(a []string, x string) int {

コアとなるコードの解説

このコミットでは、src/pkg/sort/search.go ファイル内の以下のコメントが変更されています。

  1. Search 関数のコメント:

    • 変更前: // (Note that the "not found" return value is n, the length of the input, // not -1 as in, for instance, strings.Index).
    • 変更後: // (Note that the "not found" return value is not -1 as in, for instance, // strings.Index).
    • 解説: Search 関数が n を返すこと自体は変わっていませんが、その n が「入力の長さ」であるという冗長な説明が削除され、単に -1 ではないことを強調する形に簡潔化されました。これにより、n が持つ「挿入位置」というより深い意味合いが、他のラッパー関数のコメントと合わせてより明確に伝わるようになります。

  2. SearchInts, SearchFloat64s, SearchStrings 関数のコメント:

    • 変更前（例: SearchInts）: // The return value is len(a) if x is not present.
    • 変更後（例: SearchInts）: // The return value is the index to insert x if x is not present (it could be len(a)).
    • 解説: これらのラッパー関数において、要素 x が見つからなかった場合の戻り値 len(a) の意味が大幅に明確化されました。変更前は単に「x が存在しない場合 len(a) が返される」とだけ書かれていましたが、変更後は「x が存在しない場合、戻り値は x を挿入すべきインデックスである（それは len(a) である可能性もある）」と明記されています。これにより、開発者は Search 関数群の戻り値が単なる「見つからなかった」フラグではなく、新しい要素をソートされたスライスに挿入する際の具体的な位置情報として利用できることを明確に理解できます。

これらのコメント修正は、Goの sort パッケージの Search 関数群のAPIドキュメントの精度と有用性を向上させ、開発者がこれらの関数をより効果的かつ意図通りに利用できるようにするための重要な改善です。

関連リンク

参考にした情報源リンク

  • Go言語の sort パッケージ公式ドキュメント: https://pkg.go.dev/sort (一般的な sort パッケージの機能と Search 関数の説明について)