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

このコミットは、Go言語の標準ライブラリsortパッケージに、複数のキー（フィールド）に基づいて構造体のスライスをプログラム的にソートする新しい例を追加するものです。これは、Goコミュニティで頻繁に提起される「複数の条件でソートする方法」という質問に対する具体的な解決策を提示することを目的としています。

コミット

• コミットハッシュ: 15f276bc53e39e87f69c925773221c6bc45791b2
• 作者: Rob Pike r@golang.org
• 日付: 2013年4月2日 火曜日 09:35:30 -0700

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

https://github.com/golang/go/commit/15f276bc53e39e87f69c925773221c6bc45791b2

元コミット内容

sort: new example: programmatic sort by multiple keys
Demonstrates one way to sort a slice of structs according
to different sort criteria, done in sequence.

One possible answer to a question that comes up often.

R=golang-dev, gri, bradfitz, adg, adg, rogpeppe
CC=golang-dev
https://golang.org/cl/8182044

変更の背景

Go言語において、カスタム型（特に構造体）のスライスをソートする際には、sort.Interfaceインターフェースを実装する必要があります。しかし、単一のキーではなく、複数のキー（例えば、まずユーザー名でソートし、次に言語でソートし、最後にコード行数でソートするなど）に基づいてソートしたいという要件は非常に一般的です。

これまでのGoのsortパッケージのドキュメントや例では、このような複雑な多重キーソートの具体的な実装パターンが明確に示されていませんでした。そのため、開発者コミュニティからは、この問題に対する効果的かつ慣用的な解決策を求める声が頻繁に上がっていました。

このコミットは、その「頻繁に提起される質問」に対する「一つの可能な回答」として、sortパッケージの新しい例（example_multi_test.go）を追加することで、多重キーソートの一般的なパターンと実装方法を公式にデモンストレーションすることを目的としています。これにより、Go開発者が同様のソート要件に直面した際に、この例を参考に効率的に実装できるようになります。

前提知識の解説

Go言語のソートインターフェース (sort.Interface)

Go言語でカスタムなデータ型をソートするには、sortパッケージが提供するsort.Interfaceインターフェースを実装する必要があります。このインターフェースは以下の3つのメソッドで構成されています。

1. Len() int: ソート対象の要素の数を返します。
2. Swap(i, j int): インデックスiとjの要素を入れ替えます。
3. Less(i, j int) bool: インデックスiの要素がインデックスjの要素よりも「小さい」（ソート順で前に来る）場合にtrueを返します。このメソッドがソートのロジックを定義する核心部分です。

sort.Sort()関数は、このsort.Interfaceを実装した任意の型を受け取り、クイックソートなどの効率的なアルゴリズムを使用してソートを実行します。

多重キーソート (Multi-key Sort)

多重キーソートとは、複数の基準（キー）に基づいてデータをソートするプロセスです。例えば、データベースのクエリでORDER BY column1 ASC, column2 DESCのように指定するのと同様に、まず第一のキーでソートし、第一のキーの値が同じ場合は第二のキーでソートし、といった具合に優先順位を付けてソートを行います。

Go言語でこれを実現する一般的なアプローチは、Lessメソッド内で複数の比較ロジックを連鎖させることです。もし最初の比較で順序が決定しない（つまり、両方の要素が最初のキーで等しい）場合、次のキーでの比較に進みます。これをすべてのキーについて繰り返します。

技術的詳細

このコミットで導入された多重キーソートのパターンは、関数型プログラミングの概念とGoのインターフェースを巧みに組み合わせています。

1. Change 構造体: ソート対象となるデータ構造です。user (文字列), language (文字列), lines (整数) の3つのフィールドを持ちます。

   type Change struct {
       user     string
       language string
       lines    int
   }
   

2. lessFunc 型: これは関数型であり、2つの*Changeポインタを受け取り、最初のChangeが2番目のChangeよりも「小さい」場合にtrueを返す関数を定義します。これは、特定のフィールドに基づく比較ロジックをカプセル化するためのものです。

   type lessFunc func(p1, p2 *Change) bool
   

3. multiSorter 構造体: sort.Interfaceを実装する主要な型です。

   • changes []Change: ソート対象のスライスを保持します。
   • less []lessFunc: 適用するlessFuncのリストを保持します。このリストの順序がソートの優先順位を決定します。

   type multiSorter struct {
       changes []Change
       less    []lessFunc
   }
   

4. OrderedBy 関数: 可変長引数としてlessFuncのリストを受け取り、multiSorterのインスタンスを初期化して返します。これにより、ソートの基準となる比較関数のリストを簡単に指定できます。

   func OrderedBy(less ...lessFunc) *multiSorter {
       return &multiSorter{
           changes: changes, // グローバル変数 changes を参照
           less:    less,
       }
   }
   

   注: この例ではchangesというグローバル変数を直接参照していますが、実際のアプリケーションではOrderedBy関数がソート対象のスライスも引数として受け取るように設計するのがより汎用的です。

5. multiSorter の Less メソッド: これが多重キーソートの核心的なロジックです。

   • ms.lessスライスに格納されたlessFuncを順番にループします。
   • 各lessFuncを適用し、pがqより小さいか (less(p, q)がtrue)、またはqがpより小さいか (less(q, p)がtrue) を確認します。
   • もし順序が決定した場合（どちらかがtrueを返した場合）、その結果を即座に返します。
   • もし両方のless呼び出しがfalseを返した場合（つまり、現在のキーにおいてpとqが等しい場合）、次のlessFuncに進み、次のキーでの比較を試みます。
   • 最後のlessFuncまで到達し、それでも順序が決定しなかった場合は、最後のlessFuncの結果をそのまま返します。

   このロジックにより、指定されたlessFuncのリストの優先順位に従って、要素が比較され、ソート順が決定されます。

   func (ms *multiSorter) Less(i, j int) bool {
       p, q := &ms.changes[i], &ms.changes[j]
       // 最後の比較関数を除くすべての比較関数を試す
       var k int
       for k = 0; k < len(ms.less)-1; k++ {
           less := ms.less[k]
           switch {
           case less(p, q):
               // p < q なので、順序が決定した
               return true
           case less(q, p):
               // p > q なので、順序が決定した
               return false
           }
           // p == q なので、次の比較関数を試す
       }
       // すべての比較関数が「等しい」と判断した場合、最後の比較関数の結果を返す
       return ms.less[k](p, q)
   }
   

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

このコミットでは、以下の新しいファイルが追加されました。

• src/pkg/sort/example_multi_test.go

このファイルには、Change構造体、lessFunc型、multiSorter構造体、OrderedBy関数、そしてそれらを使用した多重キーソートの具体的な使用例を示すExample_sortMultiKeys関数が含まれています。

コアとなるコードの解説

src/pkg/sort/example_multi_test.goファイルは、多重キーソートの概念を非常に明確に示しています。

1. Change構造体とサンプルデータ: Change構造体は、ユーザー、言語、行数を記録する変更履歴を表します。changesというグローバル変数に、このChange構造体のスライスとしてサンプルデータが定義されています。

2. 比較関数の定義 (lessFuncのクロージャ): Example_sortMultiKeys関数内で、lessFunc型のクロージャが複数定義されています。これらは、Change構造体の特定のフィールドに基づいて比較を行うためのものです。

   • user: ユーザー名で昇順ソート
   • language: 言語で昇順ソート
   • increasingLines: 行数で昇順ソート
   • decreasingLines: 行数で降順ソート（c1.lines > c2.linesとすることで降順を実現）

   これらのクロージャは、multiSorterのlessスライスに渡され、ソートの基準として使用されます。

3. ソートの実行例: Example_sortMultiKeys関数は、OrderedBy関数とSortメソッドを組み合わせて、様々な多重キーソートのシナリオをデモンストレーションしています。

   • OrderedBy(user).Sort(changes): ユーザー名のみでソート。
   • sort.Sort(OrderedBy(user, increasingLines)): sort.Sort関数に直接multiSorterを渡す例。ユーザー名でソートし、ユーザー名が同じ場合は行数で昇順ソート。
   • OrderedBy(user, decreasingLines).Sort(changes): ユーザー名でソートし、ユーザー名が同じ場合は行数で降順ソート。
   • OrderedBy(language, increasingLines).Sort(changes): 言語でソートし、言語が同じ場合は行数で昇順ソート。
   • OrderedBy(language, increasingLines, user).Sort(changes): 言語、行数（昇順）、ユーザー名の順でソート。

   これらの例は、lessFuncのリストをOrderedByに渡すだけで、任意の数のキーと任意の優先順位でソートロジックを柔軟に構築できることを示しています。

このパターンは、Go言語で複雑なソート要件を持つアプリケーションを開発する際に非常に役立つ、慣用的で再利用可能なソリューションを提供します。

関連リンク

• Go CL 8182044: https://golang.org/cl/8182044

参考にした情報源リンク

• Go言語 sort パッケージ公式ドキュメント: https://pkg.go.dev/sort
• Go言語におけるカスタムソートの概念（一般的な情報源）
• 多重キーソートのアルゴリズムと実装パターン（一般的な情報源）