【Go】for文を速くする(配列内の重複チェック)

10万件の配列の中に同じ文字列が入っていないかチェックする処理を作成しました。
シンプルに考えると次のようにfor文を書くことになると思います。

array = append(array, "abcdefghi1", "abcdefghi2", <以下10万件>)

//リストの重複チェック
for i := 0; i < len(array); i++ {
    for j := i + 1; j < len(array); j++ {
        if array[i] == array[j] {
            fmt.Printf("%vは重複\n", array[i])
        }
    }
}

このコードをテストしてみると30秒近く掛かってしまいます。

package main

import (
    "crypto/rand"
    "fmt"
    "time"
)

func main() {

    array := []string{}

    // チェック対象のリスト(10万)を生成
    array = append(array, "abcdefghij")
    array = append(array, "abcdefghij")
    for i := 0; i < 99998; i++ {
        // ランダムな文字列を生成(関数の内容は後述)
        random, _ := MakeRandomStr(10)
        array = append(array, random)
    }

    // 重複チェックの開始時間を取得
    startTime := time.Now()

    //配列の重複チェック
    for i := 0; i < len(array); i++ {
        for j := i + 1; j < len(array); j++ {
            if array[i] == array[j] {
                fmt.Printf("%vは重複\n", array[i])
            }
        }
    }

    // 重複チェックに掛かった時間を出力
    fmt.Printf("経過: %vs\n", time.Since(startTime).Seconds())
}

func MakeRandomStr(digit uint32) (string, string) {
    const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

    // 乱数を生成
    b := make([]byte, digit)
    if _, err := rand.Read(b); err != nil {
        return "", fmt.Sprintln("unexpected error...")
    }

    // letters からランダムに取り出して文字列を生成
    var result string
    for _, v := range b {
        // index が letters の長さに収まるように調整
        result += string(letters[int(v)%len(letters)])
    }
    return result, ""
}

// 実行結果
abcdefghijは重複
経過: 29.463416797s

これを今回、3000倍速くしてみたいと思います。

処理速度を早くする

前回の処理だと(100,000/2) * (100,000 +1 ) =50億 ループする計算になります。
※1からnまでの和を求める公式

今回はそれを10万ループにまで抑えます。

そのためには次のように実装を行います。

array = append(array, "abcdefghi1", "abcdefghi2",  <以下10万件>)

testMap := make(map[string]string, len(array))

for i := 0; i < len(array); i++ {
    if testMap[array[i]] == "" {
        testMap[array[i]] = strconv.Itoa(i)
    } else {
        fmt.Printf("%vは重複\n", array[i])
    }
}

処理内容としては、配列の内容を新しく作ったMapのキーに格納していき、同じキーを格納しようとしたらエラーを出すようにします。

こうすることで、ループ回数を配列の長さと同じ10万ループに抑えることができます。

では、実際に処理を実行してみます。

package main

import (
    "crypto/rand"
    "fmt"
    "strconv"
    "time"
)

func main() {

    array := []string{}

    // チェック対象のリスト(10万)を生成
    array = append(array, "abcdefghij")
    array = append(array, "abcdefghij")
    for i := 0; i < 99998; i++ {
        // ランダムな文字列を生成(関数の内容は後述)
        random, _ := MakeRandomStr(10)
        array = append(array, random)
    }

    // 重複チェックの開始時間を取得
    startTime := time.Now()

    //配列の重複チェック
    testMap := make(map[string]string, len(array))

    for i := 0; i < len(array); i++ {
        if testMap[array[i]] == "" {
            testMap[array[i]] = strconv.Itoa(i)
        } else {
            fmt.Printf("%vは重複\n", array[i])
        }
    }

    // 重複チェックに掛かった時間を出力
    fmt.Printf("経過: %vs\n", time.Since(startTime).Seconds())
}
func MakeRandomStr(digit uint32) (string, string) {
    const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

    // 乱数を生成
    b := make([]byte, digit)
    if _, err := rand.Read(b); err != nil {
        return "", fmt.Sprintln("unexpected error...")
    }

    // letters からランダムに取り出して文字列を生成
    var result string
    for _, v := range b {
        // index が letters の長さに収まるように調整
        result += string(letters[int(v)%len(letters)])
    }
    return result, ""
}

// 実行結果
abcdefghijは重複
経過: 0.017957268s

これで約3000倍処理速度が向上しました。