メインコンテンツへスキップ

Go Proposal Weekly Digest

Go言語のproposal更新を毎週お届け

#60630accepted

golang.org/x/exp/collection/sorted: add Map/Set based on key order

ステータス変更: likely_accept accepted

要約

AIによる要約であり、誤りを含む場合があります。

概要

キーの順序（比較関数）に基づくジェネリックな順序付きコンテナ sorted.Map と sorted.Set を、実験的パッケージ golang.org/x/exp/collection/sorted に追加する提案です。Java の TreeMap、C++ の std::map、Rust の BTreeMap に相当する機能です。

ステータス変更

likely_accept → accepted
10月29日に likely accept となった時点で、@aclements は「Span の考え方は気に入った」と評価していました。一方で「Map/Set 全体を表す Span を取得する手段がない」という指摘もありました。この指摘を受け、範囲の上限・下限を持たない Span を返す Map.Span() と Set.Span() が追加されました。最終コメント期間には「Span を作ったあとにマップへ要素を追加すると、その要素は Span から見えるのか」という疑問も出ました。しかし @aclements 自身が「API を作り直すほどの問題ではなく、ドキュメントに一文足せば十分」と判断しました。コンセンサスは変わらず、11月12日に承認されました。

技術的背景

現状の問題点

Go には組み込みの map がありますが、キーの順番は保証されません。キー順に走査したい、範囲を指定して検索したい、最小値・最大値をすばやく取り出したいといった用途に使える標準のコンテナはありません。そのため、GitHub 上には TreeMap や OrderedMap の自前実装が数千件もあります。github.com/google/btree は広く使われていますが、API が扱いにくく、範囲をまとめて削除する機能がありません。また、走査中にコンテナを変更した場合の動作も、コストの高い Clone を使わない限り保証されません。

提案された解決策

  • NewMap[K, V any](cmp func(K, K) int) *Map[K, V] と NewSet[T any](cmp func(T, T) int) *Set[T] で生成します。ゼロ値と nil は無効で、コピーには Clone を使います。
  • Map の基本操作は Get/Lookup/Set/Delete/DeleteFunc/Contains/Len/Clear/Clone/String です。
  • 順序に関わる操作として All/Keys/Values/Backward（いずれも iter.Seq 系のイテレータ）、Min/Max、Index/Nth（キーの位置とインデックスの相互変換）があります。
  • Span（範囲ビュー）: Above（下限、境界を含まない）、From（下限、含む）、Below（上限、含まない）、To（上限、含む）で MapSpan/SetSpan を作れます。Span は元のマップへの参照を持つビューで、All、Len、Clear（範囲内の要素をまとめて削除）、Clone などをその範囲に対して実行できます。
  • Set は上記に加えて Union/Intersection/Difference/SymmetricDifference と、それらの破壊的版（UnionWith など）、Equal、Intersects を持ちます。
  • 走査中に変更しても安全です。「次に返すキーは、直前に返したキーの後続（successor）である」という動作が保証されています。

これによって何ができるようになるか

  • 時系列データの範囲検索: タイムスタンプをキーにして、m.From(t1).Below(t2).All() で指定した期間のデータだけを走査できます。
  • リーダーボードや順位の計算: Index と Nth で、ある要素が何番目かを取得したり、N 番目の要素を取り出したりできます。
  • 期限切れエントリの一括削除: m.Below(now).Clear() で、期限切れの要素を範囲指定でまとめて削除できます。
  • スケジューラや優先度の管理: Min/Max で次に処理する要素を取得しつつ、キーで要素を更新・削除することもできます。

コード例

// Before: 組み込み map + 毎回ソート（O(n log n)）
m := map[int]string{}
keys := slices.Sorted(maps.Keys(m))
for _, k := range keys {
    if k >= 10 && k < 20 {
        fmt.Println(k, m[k])
    }
}
// After: sorted.Map と Span
m := sorted.NewMap[int, string](cmp.Compare[int])
m.Set(15, "a")
m.Set(30, "b")
for k, v := range m.From(10).Below(20).All() {
    fmt.Println(k, v) // 15 a
}
m.Below(20).Clear()        // 20未満をまとめて削除
k, v, ok := m.Min()        // 最小のキーと値
s := sorted.NewSet(strings.Compare)
s.Insert("go")
fmt.Println(s.Index("go")) // 0

議論のハイライト

  • cmp.Ordered 専用型の削除: 当初は、cmp.Ordered を満たすキー専用で高速化した OMap 型も検討されました。しかし API が二重になるため除外されました。将来、コンパイラの改善や型パラメータに対する型スイッチ（#45380）が実現すれば、Map の特殊ケースとして高速化できる可能性があるとされています。
  • 名前と置き場所の変遷: パッケージは container/tree、container/ordered、x/exp/container/maps.Sorted と変わり、最終的に x/exp/collection/sorted になりました。範囲型の名前は、range と紛らわしいという理由で Range から MapSpan に変更されました。
  • Set の復活: Set は「API が倍になる」という理由で一度削除されました。その後、ハッシュマップの提案（#69559）との対称性を考えて、再び追加されました。
  • Span の動作: Span の上限・下限は作成時に固定され、元のマップへの変更は Span からも見えます。@jba は Rust のように範囲を表す型を分ける案（m.AllSpan(sorted.From(3).To(10))）も示しました。しかし、ほとんどの用途は m.From(3).To(10).All() のような一時的な使い方なので、使い勝手を優先して今の形のままとし、動作はドキュメントで明記することになりました。
  • 実装: リファレンス実装には github.com/jba/omap が使われ、treap（二分探索木とヒープを組み合わせた木構造）による実装の CL も出ています。

関連リンク