go言語で書いた (gist)。集合の要素は前もってソートしておいて、比較回数を減らしている。

package main

import (
    "fmt"
    "sort"
    "strconv"
)

func CountDuplicateElem(x, y []string) int {
    i := 0
    j := 0
    num_match := 0
    num_cmp := 0
    for {
        if i >= len(x){
            break
        }
        for {
            num_cmp += 1
            if j >= len(y) { // 位置jがyの長さを超えたら終了
                break
            }
            if x[i] < y[j] { // 辞書順でx[i]がy[j]よりも小さければ終了
                break // ソートされていればjより大きな位置の文字で一致することは無い
            }
            if x[i] == y[j] {
                num_match += 1
                j += 1
                break
            }
            j += 1
        }
        i += 1
    }
    return num_match
}
func NaiveCount(x, y []string) int {
    num_match := 0
    for i := 0; i<len(x);i++{
            for j := 0; j<len(y);j++{
                    if x[i] == y[j] {
                            num_match += 1
                    }
            }
    }
    return num_match
}
func main() {
    k := []string{}
    l := []string{}
    for i:=0; i<100000; i++{
            k = append(k, strconv.Itoa(i))
            l = append(l, strconv.Itoa(i - 1))
    }
    cnt_match := CountDuplicateElem(k, l)
    cnt_match := NaiveCount(k, l)
    fmt.Println(cnt_match)
}

数を多めにしてナイーブな方法と比較してみる。 それぞれの要素をfor文で回すとてもナイーブな方法:

time go run countelem.go
99999
go run countelem.go  119.16s user 0.88s system 99% cpu 2:00.95 total

今回書いた方法:

time go run countelem.go
99999
go run countelem.go  0.20s user 0.08s system 57% cpu 0.494 total

各要素をfor文で回すとてもナイーブな手法よりは速い（当たり前か）。


関連記事





最近の記事