sliceの重複チェックを高速化

sliceの重複チェックはmapを使うと高速に動作させることができます。

// 重複した要素を削除して返却
func removeDuplicate1(args []string) []string {
	results := make([]string, 0, len(args))
	encountered := map[string]bool{}
	for i := 0; i < len(args); i++ {
		if !encountered[args[i]] {
			encountered[args[i]] = true
			results = append(results, args[i])
		}
	}
	return results
}

以下のようにfor文を２重ループさせる方法だと最大でデータ数-1の階乗分の比較処理が行われるため、データ数が増えるにつれ指数関数的に処理時間が増えてしまいます。

// 重複した要素を削除して返却
func removeDuplicate2(args []string) []string {
	results := make([]string, 0, len(args))
	for i := 0; i < len(args); i++ {
		dup := false
		for j := 0; j < len(results); j++ {
			if args[i] == results[j] {
				dup = true
				break
			}
		}
		if !dup {
			results = append(results, args[i])
		}
	}
	return results
}

ベンチマーク結果

func BenchmarkRemoveDuplicate1(b *testing.B) {
	data := make([]string, 0, 100000)
	for i := 0; i < 100000; i++ {
		data = append(data, fmt.Sprintf("test-%08d", i%99000))
	}

	as := assert.New(b)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		result := removeDuplicate1(data)
		as.Len(result, 99000)
	}
}

func BenchmarkRemoveDuplicate2(b *testing.B) {
	data := make([]string, 0, 100000)
	for i := 0; i < 100000; i++ {
		data = append(data, fmt.Sprintf("test-%08d", i%99000))
	}

	as := assert.New(b)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		result := removeDuplicate2(data)
		as.Len(result, 99000)
	}
}

$ go test -bench .
PASS
BenchmarkRemoveDuplicate1-4	      50	   31949991 ns/op
BenchmarkRemoveDuplicate2-4	      1		44521444122 ns/op

10万件のデータでかなり速度に違いが出ています。

おまけ(応用)

SQLのDISTINCTは重複を削除する際に内部的にソートが行われるため負荷の高い処理となります。
SQL側で重複削除する方法がDISTINCT以外にない場合は、SQL側で行わずに呼び出し側で重複削除した方が高速化する場合があります。

func SelectXxxx(db *sql.DB) ([]string, error) {
	query := "SELECT xxxx FROM table"
	values := []interface{}{}
	encountered := map[string]bool{}

	rows, err := db.Query(query, nil)
	if err != nil {
		return nil, err
	}
	defer rows.Close()

	xxxx := []string{}
	var x string
	for rows.Next() {
		err := rows.Scan(
			&x,
		)
		if err != nil {
			return xxxx, err
		}
		if !encountered[x] {
			encountered[x] = true
			xxxx = append(xxxx, x)
		}
	}
	return xxxx, rows.Err()
}

またslice同士の重複チェックを行う時も2つのsliceを２重ループさせるより片方のsliceを一旦mapにしてから重複チェックした方が早くなります。

// targetに含まれる要素を削除して返却
func removeTargetIncluded(args []string, target []string) []string {
	results := make([]string, 0, len(args))
	targetMap := map[string]bool{}
	for i := 0; i < len(target); i++ {
		targetMap[target[i]] = true
	}
	for i := 0; i < len(args); i++ {
		if !targetMap[args[i]] {
			results = append(results, args[i])
		}
	}
	return results
}

参考