Goで競プロのグラフの問題を解くときは、Vectorを使った方がよいっぽい
結論
グラフの問題をいくつかのデータ構造を使って解いてみたが、gostl vectorが一番早かった。
内容
以下の問題をgostlのsetで解いてみたら、LTEした。
※gostl導入前は、map[int]boolを使っていたのでその名残+gostlの使い方の練習もかねて
gostlのsetが遅いのか…。
と思い、sliceをapendする方法に変えてみたら、もっと遅かった。
※先に連続領域を確保する方法でやったら、MLEもした
Go標準のmapを使う方法と、gostlのvectorを使う方法ではACしたが、vectorの方が圧倒的に早かった。
方法 | 実行時間 |
---|---|
gostl set | 1107 ms |
slice | 1253 ms |
gostl vector | 119 ms |
map | 921 ms |
列挙にそれほどの速度差があるとも思えないので、要素の追加にかかるコストの差だと考えられる。
となると、グラフの問題は全般的にgostl vectorを使った方がよいと考えられる。
TLEしなければ気にすることもなかったのでTLEしてよかったとも思える。
func solveBase(n, m int, abs [][]int) bool {
ss := make([]*vector.Vector[int], n+1)
for i := range ss {
ss[i] = vector.New[int]()
}
for _, ab := range abs {
a := ab[0]
b := ab[1]
ss[a].PushBack(b)
ss[b].PushBack(a)
}
vs := make([]bool, n+1)
s := stack.New[int]()
s.Push(1)
for !s.Empty() {
p := s.Pop()
vs[p] = true
for iter := ss[p].Begin(); iter.IsValid(); iter.Next() {
if !vs[iter.Value()] {
s.Push(iter.Value())
}
}
}
b := true
for _, i := range rangeIndex(1, n) {
b = b && vs[i]
}
return b
}
追記
gostlのvector内部のデータモデルは、単純なsliceであった。
つまり、
と思い、sliceをapendする方法に変えてみたら、もっと遅かった。
※先に連続領域を確保する方法でやったら、MLEもした
は、完全な間違いでした。申し訳ありません。
理論的に考えて、sliceをapendする方法は、vectorと同じかほんの僅かに早い、という結果になるはず。
ss[i] = vector.New[int]()
のところをsliceの時には、
ss[i] = make([]int, 0, n)
としており、nが非常に大きい場合に、n回大きな連続領域を確保しに行ってしまい、それが遅かったし、無駄なメモリを抱えることになり、MLEにつながったということのようです。
ほぼ確実にほぼ使い切るようなケースでない限り、キャパシティは設定しない方が無難かもしれません(つまり、設定しておいた方が実行速度が速くなるという確信がある時)。
ただし、ランダムに値を書き換えたい場合以外ではsliceよりもgostl vectorの方が扱いやすいと感じているので、「基本的にはgostl vectorを使う」という方針で問題ないとは思います。
// 例えば、これが
slice[x] += 5
// こうなってしまうので…
vec.SetAt(x, vec.At(x)+5)
Discussion