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

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

このコミットは、Go言語の sort パッケージにおける Search 関数およびそのラッパー関数（SearchInts, SearchFloat64s, SearchStrings）のドキュメンテーションを改善し、「要素が見つからなかった場合」の戻り値が len(input) であることをより明確にすることを目的としています。多くのプログラマが検索関数で「見つからない」場合に -1 を期待する傾向があるため、この明確化は混乱を避けるために重要です。

コミット

sort: make return value for 'not found' clearer in docs
It was well-defined but easy to miss that the return value for
"not found" is len(input) not -1 as many expect.

Fixes #4205.

R=golang-dev, dsymonds
CC=golang-dev
https://golang.org/cl/6820080

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

https://github.com/golang/go/commit/20548b153f05528c0c58347a817fb3a3eee6cd0c

元コミット内容

sort: make return value for 'not found' clearer in docs It was well-defined but easy to miss that the return value for "not found" is len(input) not -1 as many expect.

Fixes #4205.

R=golang-dev, dsymonds CC=golang-dev https://golang.org/cl/6820080

変更の背景

Go言語の sort パッケージに含まれる Search 関数は、ソートされたデータに対して二分探索を行うための汎用的な関数です。この関数は、特定の条件を満たす最初のインデックスを返します。もし条件を満たす要素が見つからない場合、この関数は入力の長さ（n または len(input)）を返すように設計されています。

しかし、多くのプログラミング言語やライブラリ（例えば、C++の std::string::find や Java の String.indexOf、Python の list.index が要素が見つからない場合に例外を発生させるか、C言語の strchr が NULL を返すなど）では、検索関数が要素を見つけられなかった場合に -1 を返すのが一般的です。この慣習との違いが、Goの sort.Search を利用する開発者にとって混乱の原因となっていました。

コミットメッセージにあるように、「見つからない」場合の戻り値は「明確に定義されていた」ものの、「見落としやすかった」ため、ドキュメンテーションを改善してこの点をより強調する必要がありました。これは、ユーザーが誤解なく関数を正しく使用できるようにするための、ユーザビリティとAPIの明確性に関する改善です。具体的には、Issue #4205 で報告された問題に対応しています。

前提知識の解説

二分探索は、ソートされた配列やリストから特定の要素のインデックスを効率的に見つけるための探索アルゴリズムです。探索範囲を半分に絞り込むことを繰り返すため、要素数 N に対して O(log N) の計算量で動作します。

Go言語の sort.Search 関数は、この二分探索の概念を抽象化したものです。これは、特定の述語関数 f(i) が false である範囲と true である範囲に分かれるような配列（または論理的な範囲）に対して、f(i) が true になる最初のインデックス i を見つけます。

sort.Search 関数の契約

sort.Search(n int, f func(int) bool) int は、以下の特性を持つ関数です。

  • n: 探索対象の論理的な範囲の長さ（0から n-1 までのインデックス）。
  • f: 述語関数。f(i) は、i がある閾値より小さい場合は false を返し、それより大きいか等しい場合は true を返すという性質（単調性）を持つ必要があります。
  • 戻り値: f(i) が true となる最小のインデックス i を返します。もしそのような i が存在しない場合（つまり、全ての i に対して f(i) が false を返す場合）、関数は n を返します。この n という戻り値は、探索範囲の「次の位置」を指し、要素が見つからなかったことを示すと同時に、新しい要素を挿入するべき位置としても解釈できます。

検索関数における「見つからない」場合の戻り値の慣習

  • -1: 多くの言語やライブラリ（例: C/C++の string::find、Javaの String.indexOf）では、要素が見つからなかった場合に無効なインデックスとして -1 を返します。これは、配列のインデックスが通常0以上であるため、明確に「見つからない」ことを示すことができます。
  • len(input) または n: Goの sort.Search のように、探索範囲の「次の位置」を返すことで、見つからなかったことを示すと同時に、その位置に要素を挿入すればソート順が保たれるという追加情報を提供します。これは、特に挿入操作と組み合わせる場合に便利です。
  • 例外/エラー: Pythonの list.index() のように、要素が見つからない場合に例外（ValueError）を発生させるものもあります。

このコミットは、Goの sort.Search が len(input) を返すという、一般的な慣習とは異なる点を明示することで、開発者の誤解を防ぐことを目的としています。

技術的詳細

sort.Search 関数は、Go言語の標準ライブラリ sort パッケージの中核をなす関数の一つです。この関数は、二分探索アルゴリズムを抽象化し、任意のソート済みデータ構造に対して適用できるように設計されています。その汎用性は、述語関数 f を引数として受け取ることで実現されています。

Search(n int, f func(int) bool) int のシグネチャは、以下の意味を持ちます。

  • n: 探索対象の要素数。インデックスは 0 から n-1 までです。
  • f func(int) bool: 述語関数。この関数は、インデックス i を受け取り、bool 値を返します。sort.Search が正しく機能するためには、f(i) が false となるインデックスの連続したプレフィックスがあり、その後に true となるインデックスの連続したサフィックスが続くという単調性（monotonicity）が保証されている必要があります。

Search 関数の内部では、二分探索が実行され、f(i) が true となる最小の i が探索されます。もし、0 から n-1 までのどのインデックス i に対しても f(i) が false を返す場合、これは探索対象の範囲内に条件を満たす要素が存在しないことを意味します。この場合、Search 関数は n を返します。この n という値は、有効なインデックスの範囲外であり、かつ、もし条件を満たす要素を挿入するとしたら、その要素が n 番目の位置（つまり、現在の配列の末尾）に来ることを示唆しています。

このコミットでは、この「見つからない場合の戻り値が n である」という重要な仕様が、ドキュメンテーション内でより明確に強調されています。特に、他の言語で一般的な -1 ではないことを明記することで、開発者が混乱する可能性を減らしています。

変更は主に以下の3つの箇所で行われています。

  1. sort.Search 関数のドキュメンテーション: Search 関数のコメントに、n が「見つからない」場合の戻り値であり、strings.Index のような -1 ではないことが追記されました。これにより、関数の基本的な動作原理と、一般的な慣習との違いが明確になります。

  2. SearchInts 関数のドキュメンテーション: SearchInts は Search のラッパー関数であり、int スライスに対する探索を簡略化します。この関数のコメントにも、「x が存在しない場合、戻り値は len(a) である」という記述が追加されました。これは、Search の挙動がラッパー関数にも適用されることを明示しています。

  3. SearchFloat64s 関数のドキュメンテーション: SearchFloat64s も同様に float64 スライスに対するラッパー関数です。ここにも、「x が存在しない場合、戻り値は len(a) である」という記述が追加されました。

  4. SearchStrings 関数のドキュメンテーション: SearchStrings も同様に string スライスに対するラッパー関数です。ここにも、「x が存在しない場合、戻り値は len(a) である」という記述が追加されました。

これらの変更は、コードの動作自体を変更するものではなく、APIのドキュメンテーションを改善し、開発者がより正確に関数の挙動を理解できるようにするためのものです。これにより、誤用やバグの発生を未然に防ぐことが期待されます。

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

--- a/src/pkg/sort/search.go
+++ b/src/pkg/sort/search.go
@@ -12,6 +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).
 // 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
@@ -74,21 +76,24 @@ 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 slice must be sorted in ascending order.\n+// as specified by Search. The return value is len(a) if x is not present.
+// The slice must be sorted in ascending order.
 //
 func SearchInts(a []int, x int) int {
 	return Search(len(a), func(i int) bool { return a[i] >= x })
 }
 
 // SearchFloat64s searches for x in a sorted slice of float64s and returns the index
-// as specified by Search. The slice must be sorted in ascending order.\n+// as specified by Search.  The return value is len(a) if x is not present.
+// The slice must be sorted in ascending order.
 //
 func SearchFloat64s(a []float64, x float64) int {
 	return Search(len(a), func(i int) bool { return a[i] >= x })
 }
 
 // SearchStrings searches for x in a sorted slice of strings and returns the index
-// as specified by Search. The slice must be sorted in ascending order.\n+// as specified by Search.  The return value is len(a) if x is not present.
+// The slice must be sorted in ascending order.
 //
 func SearchStrings(a []string, x string) int {
 	return Search(len(a), func(i int) bool { return a[i] >= x })
 }

コアとなるコードの解説

このコミットによるコードの変更は、Goの sort パッケージ内の search.go ファイルにおけるドキュメンテーションコメントの追加と修正に限定されています。実際の関数のロジックや動作には一切変更がありません。

  1. Search 関数のコメント (src/pkg/sort/search.go の 12行目付近): 元のコメントでは、「条件を満たすインデックスがない場合、Search は n を返す」と記述されていました。この変更では、その行の直後に新しい行が追加され、n が「見つからない」場合の戻り値であり、strings.Index のような他の言語やGoの他の関数で一般的な -1 ではないことが明示されています。

    // (Note that the "not found" return value is n, the length of the input,
// not -1 as in, for instance, strings.Index).

    この追加により、開発者が Search 関数の戻り値を誤解する可能性が大幅に減少します。

  2. SearchInts, SearchFloat64s, SearchStrings 関数のコメント (src/pkg/sort/search.go の 76, 83, 90行目付近): これらの関数は、それぞれ int, float64, string のスライスに対して Search 関数を適用するための便利なラッパーです。元のコメントでは、「Search で指定されたインデックスを返す」とだけ書かれていました。 変更後、各関数のコメントに以下の記述が追加されました。

    // The return value is len(a) if x is not present.

    これは、Search 関数の「見つからない場合の戻り値が n（ここでは len(a) に相当）である」という挙動が、これらのラッパー関数にも適用されることを明確に示しています。これにより、これらの特定の型に対する探索を行う開発者も、戻り値の挙動について迷うことがなくなります。

これらの変更は、コードの可読性とAPIの理解度を向上させるための純粋なドキュメンテーションの改善であり、Goの標準ライブラリの品質向上に貢献しています。

関連リンク

参考にした情報源リンク