お題
要素をリストに、追加したり、特定の要素を削除したり、要素一覧を取得することを考えましょう。なお順番は不問とします。
もし例えばリストとして slice を用いると、追加や要素一覧を取得することは O(1) できますが、slice の中の特定の値を削除することは O(N) かかり遅いです。
リストとして map を用いると、要素の追加・削除は O(1) ででき、要素一覧も取得できます。
m := map[int64]struct{}{}
// 要素の追加
m[100] = struct{}{}
m[101] = struct{}{}
// 要素の削除
delete(m, 100)
// 要素一覧の取得
for item, _ := range m {
fmt.Print(item)
}
// Output: 100
このように map をデータ構造に用いると、計算量の点でも O(1) で良さそうですが、これを更に高速化できないでしょうか。というのが本記事のお題です。
特に、追加・削除は多少遅くても、要素一覧の取得だけは高速化したいというユースケースを考えましょう。これは例えば経路探索で用いるグラフのデータ構造などが該当します。(要素の追加・削除はグラフの初期化で最初に一度だけ行うが、経路探索のレスポンスには、要素一覧の取得のみしか行わない。)
実装したい機能の interface を書くと以下の通りです。
// ItemIterator allows callers of All() to iterate items.
// When this function returns false, iteration will stop and
// the associated All() function will immediately return.
type Iterator func(item int64) bool
type Interface interface {
// All iterate all items in the set
All(Iterator)
// Delete delete item from the set
Delete(item int64)
// Append append item to the set
Append(item int64)
}
ここで要素一覧の取得をする All() について補足します。返り値に []int64 を返しても良いのですが、不要なsliceのメモリアロケートを避けるために、内部イテレーターパターンを採用しています。(ちなみにPythonだとyield文で同等のことが簡単にできます。) Go におけるイテレーターについては Iterators in Go
の記事が詳しいです。
map による実装(サンプル)
データ構造として map を採用し、先程あげた目標の interface を満たす実装をすると以下のようになります。
本記事ではこれを超えるパフォーマンスを実現することが目標になります。
要素の削除には build-in 関数の delete 、要素一覧の取得には range を用いており、特筆すべきことはありません。
type SetMap struct {
items map[int64]struct{}
}
func NewSetMap(c int) *SetMap {
return &SetMap{
items: make(map[int64]struct{}, c),
}
}
func (s *SetMap) All(fn Iterator) {
for item, _ := range s.items {
if !fn(item) {
break
}
}
}
func (s *SetMap) Delete(item int64) {
delete(s.items, item)
}
func (s *SetMap) Append(item int64) {
s.items[item] = struct{}{}
}
提案する slice を用いた実装
大まかな方針
先にあげた map による実装より、要素一覧の取得が高速な実装をするにはどうすればよいでしょうか?
結論から述べると、map に対する range が遅いので、 要素一覧の取得 All() 中では極力 map にアクセスしないアプローチが有効です。
なぜ map の range が遅いか
なぜ map に対する range は遅いのかは、mapの構造を理解する必要があります。go の map はただのハッシュテーブルでできています。1
map の key, value は 8個ずつ Bucket に byte の array に pack され保存されます。また、Bucket 自体がリンクドリストのように、別の Bucket への参照を持ちうります。このような構造なので、key, value を range で取り出すのは、slice へのiteration 比べ、だいぶオーバーヘッドが大きそうに思われます。
なお、map の内部アーキテクチャの概要に関しては、Macro View of Map Internals In Go
の記事が詳しいです。2013年の記事ですが、2019年現在筆者が mapのソースコードを読んだところ、大きな違いはないように思われます。
提案するデータ構造
今回は要素一覧の取得だけ高速化したいので、 All 中では slice へのアクセスだけで済むようにしましょう。要素をいれる slice items []int64 と、削除フラグを持つslice deleted []bool を用いています。
type Set struct {
deleted []bool
items []int64
}
func (s *Set) All(fn Iterator) {
for i, item := range s.items {
if s.deleted[i] {
continue
}
if !fn(item) {
break
}
}
}
これだと、特定の要素の削除が効率的に( = O(1)で)行なえません。削除用のindex indexOf を map で持っておくことにしましょう。
type Set struct {
deleted []bool
items []int64
indexOf map[int64]int
}
func (s *Set) Delete(item int64) {
s.deleted[s.indexOf[item]] = true
}
要素の追加時にはこのindexの更新も行いましょう。
func (s *Set) Append(item int64) {
_, ok := s.indexOf[item]
if ok {
panic("duplicate item")
}
s.indexOf[item] = len(s.items)
s.items = append(s.items, item)
s.deleted = append(s.deleted, false)
}
限界
- 本記事中では検証していませんが、削除が多くなるユースケースの場合、イテレーションに無駄な演算が多くなりパフォーマンスが悪化する可能性があります。その場合、双方向リストの導入などが有効な可能性があります。
ベンチマーク
map を用いたサンプル実装と、slice を用いた提案する手法でベンチマークを取ります。
n=1000, 100万として、n回のAppend/All/Deleteにかかる時間を比較します。
実際のベンチマークのソースコードはこちらで確認できます。
https://github.com/avvmoto/go-set/blob/master/set_test.go#L60
$ go test -bench . -benchmem
goos: darwin
goarch: amd64
pkg: set
BenchmarkSet/1000/Set/Append-8 1000000000 0.000057 ns/op 0 B/op 0 allocs/op
BenchmarkSet/1000/Set/Delete-8 1000000000 0.000029 ns/op 0 B/op 0 allocs/op
BenchmarkSet/1000/Set/All-8 1000000000 0.000004 ns/op 0 B/op 0 allocs/op
BenchmarkSet/1000/SetMap/Append-8 1000000000 0.000036 ns/op 0 B/op 0 allocs/op
BenchmarkSet/1000/SetMap/Delete-8 1000000000 0.000037 ns/op 0 B/op 0 allocs/op
BenchmarkSet/1000/SetMap/All-8 1000000000 0.000024 ns/op 0 B/op 0 allocs/op
BenchmarkSet/1000000/Set/Append-8 1000000000 0.151 ns/op 0 B/op 0 allocs/op
BenchmarkSet/1000000/Set/Delete-8 1000000000 0.126 ns/op 0 B/op 0 allocs/op
BenchmarkSet/1000000/Set/All-8 1000000000 0.00318 ns/op 0 B/op 0 allocs/op
BenchmarkSet/1000000/SetMap/Append-8 1000000000 0.0987 ns/op 0 B/op 0 allocs/op
BenchmarkSet/1000000/SetMap/Delete-8 1000000000 0.0853 ns/op 0 B/op 0 allocs/op
BenchmarkSet/1000000/SetMap/All-8 1000000000 0.0166 ns/op 0 B/op 0 allocs/op
PASS
ok set 10.057s
リストのサイズによらず、要素一覧の取得が約5倍高速化しました!
ただ、要素の追加・削除は約1.5倍時間がかかるようになりました。
本データ構造を用いるかどうかはユースケース次第でしょう。要素一覧の取得の速度が重要な場合には選択肢となります。
まとめ
とにかく要素一覧の取得が高速な、削除可能であるリスト構造を実装しました。
シンプルに map で実装するよりも、要素一覧の取得が約5倍高速なデータ構造を提案しました。
代わりにトレードオフとして、削除してもメモリ使用量が減らない問題があるのと、要素の追加・削除は約1.5倍時間がかかるようになる問題が出ました。
ユースケースとしては、現在筆者が取り組んでいる経路探索で用いるグラフのデータ構造などが挙げられます。
本記事中のコードはオープンソースとして公開したのでどうぞご利用ください。
avvmoto/go-set
最後に
より効率的な方法があればぜひご連絡ください。謹んで記事を訂正いたします。
またすでにこのデータ構造に名前がついてたら教えて下さい。