🙄

Goで競プロのグラフの問題を解くときは、Vectorを使った方がよいっぽい

2025/01/27に公開

結論

グラフの問題をいくつかのデータ構造を使って解いてみたが、gostl vectorが一番早かった。

内容

以下の問題をgostlのsetで解いてみたら、LTEした。
※gostl導入前は、map[int]boolを使っていたのでその名残+gostlの使い方の練習もかねて

A62 - Depth First Search

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