golangで配列の要素をフィルターしたいです

Question

#ヤリタイコト
golangで

src := [...]int{1, 2, 3, 4, 5}

filter := [...]int{3, 5}

この二つの配列の被っている要素だけを抜き出して配列にしたいです。(数学で言うsrc ∩ filter)
一番ハイパフォーマンスな方法を教えてください

Comments

[ozwk]

{1,1,2}と{1}のとき結果はどうしたいですか?{1,1} or {1}?

[退会済みユーザー]

重複した場合は{1}としていただきたいです

Answer 1

書いてて飽きてきてしまったのでこれが最速かどうかは分かりませんが、ベンチマークコードも載せておきます。

package common

import (
	"reflect"
	"sort"
	"testing"
)

func makeCommon(lhs, rhs []int) []int {
	// 出現回数
	m := map[int]int{}

	// 存在しない時だけ1にする
	// LHS で2回発生しても1
	for _, v := range lhs {
		if _, ok := m[v]; !ok {
			m[v] = 1
		}
	}

	// 存在する時だけ2にする
	for _, v := range rhs {
		if _, ok := m[v]; ok {
			m[v] = 2
		}
	}
	ret := []int{}
	for i := range m {
		if m[i] > 1 {
			ret = append(ret, i)
		}
	}
	sort.Ints(ret)
	return ret
}

func TestMakeCommon(t *testing.T) {
	tests := []struct {
		lhs  []int
		rhs  []int
		want []int
	}{
		{lhs: []int{1, 2, 3, 4, 5}, rhs: []int{3, 5}, want: []int{3, 5}},
		{lhs: []int{1, 2, 2, 3, 4, 5}, rhs: []int{3, 5}, want: []int{3, 5}},
		{lhs: []int{1, 2, 3, 3, 4, 5}, rhs: []int{3, 5}, want: []int{3, 5}},
		{lhs: []int{1, 1, 1}, rhs: []int{1, 1}, want: []int{1}},
		{lhs: []int{1, 2, 4, 5}, rhs: []int{3, 5}, want: []int{5}},
		{lhs: []int{1, 2, 4}, rhs: []int{3, 5}, want: []int{}},
		{lhs: []int{}, rhs: []int{3, 5}, want: []int{}},
		{lhs: []int{1, 2}, rhs: []int{}, want: []int{}},
		{lhs: []int{}, rhs: []int{}, want: []int{}},
	}

	for _, tt := range tests {
		got := makeCommon(tt.lhs, tt.rhs)
		if !reflect.DeepEqual(got, tt.want) {
			t.Fatalf("want %v but got %v", tt.want, got)
		}
	}
}

func BenchmarkMakeCommon(b *testing.B) {
	lhs := make([]int, b.N)
	rhs := make([]int, b.N/2)
	for i := 0; i < b.N; i++ {
		lhs[i] = i * 2
	}
	for i := 0; i < b.N/2; i++ {
		rhs[i] = i * 3
	}
	b.ResetTimer()
	makeCommon(lhs, rhs)
}

common_test.go などに保存して

$ go test -bench .
goos: windows
goarch: amd64
BenchmarkMakeCommon-4            5000000               396 ns/op
PASS
ok      _/C_/dev/go-sandbox/dup 2.482s

で実行して下さい。