これ、流石にほっとけないので400倍くらい速くしてみましたが、眠くてお手上げなので私ができたところまで解説。きっと親切な人がまさかりがてらもっと保守性が高くて速いコードを教えてくれるはず。
問題の内容
Goで2つのSlice(A、B)のうち、Aにだけ存在し、Bには存在しない値を持ったSliceを生成する
大分曖昧ですが、詳細は元記事を。元記事のコードは二重ループを使う典型的な遅くなるやつだったので改造に取りかかる。
基本的には、元記事のコードと同じ要件を満たすようにする。
ただし、元記事には書いてない条件として、配列はソートされた状態で出力するものとする。
結果
BenchmarkQiita-4 1 2127655888 ns/op 2303264 B/op 28 allocs/op
BenchmarkMine0-4 200 6466429 ns/op 524352 B/op 3 allocs/op
BenchmarkMine1-4 100 18598037 ns/op 8514379 B/op 2432 allocs/op
400倍くらい速くなりました。配列長くすればもっと（相対的に）速くなります。ループもメモリ消費も実装0ベースで考えていけば良さそう。
私の実装0
func checkDup(sliceA, sliceB []int) []int {
s := make([]int, 0, len(sliceA))
sort.Ints(sliceA)
sort.Ints(sliceB)
for i, j := 0, 0; i < len(sliceA) && j < len(sliceB); {
if sliceA[i] == sliceB[j] {
i++
} else if sliceA[i] < sliceB[j] {
s = append(s, sliceA[i])
i++
} else {
if j == len(sliceB)-1 {
s = append(s, sliceA[i:len(sliceA)]...)
}
j++
}
}
return s
}
汚いコードだな…。保守性低そうですが、私が書いた中ではこれが一番速くてメモリ使いませんでした。ソートして合計一週ずつするだけの非常にシンプルな考え方。
工夫のしどころはまだまだありそうですが、眠いのでこんなもので。
私の実装1（map利用、遅め）
func checkDup1(sliceA, sliceB []int) []int {
s := make([]int, 0, len(sliceA))
m := make(map[int]int, len(sliceA))
for _, n := range sliceA {
m[n] += 1
}
for _, n := range sliceB {
m[n] -= 1
}
for n, count := range m {
if count > 0 {
for i := 0; i < count; i++ {
s = append(s, n)
}
}
}
sort.Ints(s)
return s
}
map作ってみたけど流石にソート済みには勝てなかったよ…
テストコード
func makeSlices() [][]int {
l := 65536
s := make([][]int, 2, 2)
s[0] = make([]int, 0, l)
s[1] = make([]int, 0, l)
for i := 0; i < l; i++ {
s[0] = append(s[0], i*3)
s[1] = append(s[1], i*5)
}
return s
}
var cases = makeSlices()
とりあえずこんなので生成してます。
これもなんかもう少し速いやり方あった気がする…
まとめ
二重ループに気をつけよう