2026/02/23 4:19
**ブラック―ホワイト配列** *高速で順序付けられ、O(log N) のメモリ割り当てに基づく*
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
改良された概要
BWArr は、Go 用の軽量で配列ベースのデータ構造であり、既存の BTree ライブラリを置き換えることができ、要素ごとの余分なオーバーヘッドなしに multiset のサポートを追加します。挿入・削除・検索に対して平均的 (O(\log N)) の性能を提供しつつ、要素を連続したメモリ領域に格納するため、キャッシュローカリティが優れ、ポインタ中心のツリーと比べてメモリ使用量が削減されます。ベンチマークでは、挿入・取得・反復速度で Google の BTree 実装と同等またはそれを上回ることが示されています。BWArr は
およびgithub.com/google/btreeに対するドロップイン代替品で、Go 1.22+ が必要であり、github.com/petar/GoLLRBでインストールできます。go get github.com/dronnix/bwarr
性能のニュアンス：非常に小さなコレクションでは Search()/Delete() が最大で (O((\log N)^2)) になる場合があります。長い削除系列では Max()/Min() や反復が (O(N/4)) に達することがあります（ただし平均的には (O(\log N)) のままです）。1 回あたりの挿入操作は (O(N)) まで悪化し、レイテンシスパイクを引き起こす可能性があります。
今後の更新では、その配列ベースであることを活かしてバッチ操作の高速化を目指します。BWArr を採用することで、Go 開発者は従来の BTree ライブラリに依存していたアプリケーションで、メモリ消費量の削減、CPU キャッシュ使用率の向上、およびスケーラビリティの改善を実現できます。
本文
何でしょうか？
Black‑White Array（略称 BWArr）は、O(log N) のメモリ割り当てで高速に動作する順序付きデータ構造です。配列をベースにしており、挿入・削除・検索が O(log N) アマルガメイト（摂算）で実行できます。
データ構造
Black‑White Array のアイディアは、Professor Z. George Mou によって発明され、Black‑White Array: A New Data Structure for Dynamic Data Sets で公開されました。
このリポジトリには最初の公開実装が収録されています。
主な特徴
- 挿入時に O(log N) のメモリ割り当て – GC（ガーベジコレクション）への負荷を抑制。
- 高速な挿入、削除、検索操作 (O(log N) 摂算)。
- 配列ベースでポインタ不要 → CPU フレンドリー：キャッシュローカリティ / 連続メモリアクセスなどが有効化。
- 重複要素をネイティブにサポート（マルチセット挙動） – 値を構造体で包む必要はない。
やgithub.com/google/btree
の Drop‑in 置き換え候補。github.com/petar/GoLLRB- メモリオーバーヘッドが低い – 要素ごとにポインタを持たず、コンパクトな表現。
- バッチ操作向け：内部で配列を使用しているため、大量挿入・削除の効率化（開発中）。
- シリアライズしやすい（開発中）。
トレードオフ
- 1 回の N ごとの挿入 が O(N) になる場合がありますが、摂算は O(log N) のままです。
リアルタイムシステムでは数百万要素を扱うと遅延スパイクが発生する可能性があります（非同期 / バックグラウンド挿入で緩和）。 - 要素数が少ない場合、Search()/Delete() が O((log N)²) になることがあります。
ざっくり言えば、50 % の要素は O(log N)、75 % は O(2 log N)、87.5 % は O(3 log N) など。 - 長い連続削除を行うと Max()/Min() が O(N/4) を要する場合がありますが、摂算は O(log N) のままです。
- 大量削除時にイテレーションステップが O(N/4) になることがあります。
摂算上は各要素ごとに O(log N) を保ちます。
ベンチマーク
ベンチマークでは BWArr と Google BTree を比較しています。
| テスト | 内容 |
|---|---|
| Insert | N 個のユニークなランダム |
| Get | 事前に埋め込まれたデータ構造から N 個の値をキーで検索する時間。 |
| Iterate | 並べ替え済みと未並べ替え状態で全 N 要素を走査する時間。 |
詳細やアーキテクチャ別のベンチマークは
bwarr-benchインストール
Go 1.22 以降が必要です。
go get github.com/dronnix/bwarr
インポート：
import "github.com/dronnix/bwarr"
使用例
基本例
package main import ( "fmt" "github.com/dronnix/bwarr" ) func main() { // 整数比較関数を指定して BWArr を作成。 // 2 番目の引数 (10) は初期容量ヒントです。 bwa := bwarr.New(func(a, b int64) int { return int(a - b) }, 10) // 要素挿入 bwa.Insert(42) bwa.Insert(17) bwa.Insert(99) bwa.Insert(23) bwa.Insert(8) fmt.Printf("Length: %d\n", bwa.Len()) // 出力: Length: 5 // 要素取得 val, found := bwa.Get(42) if found { fmt.Printf("Found: %d\n", val) // 出力: Found: 42 } // 要素削除 deleted, found := bwa.Delete(17) if found { fmt.Printf("Deleted: %d\n", deleted) // 出力: Deleted: 17 } // 昇順でイテレーション fmt.Println("Elements in sorted order:") bwa.Ascend(func(item int64) bool { fmt.Printf(" %d\n", item) return true // 途中で停止したい場合は false を返す }) }
出力
Length: 5 Found: 42 Deleted: 17 Elements in sorted order: 8 23 42 99