キカガク流アルゴリズム論をGoで書く 素数判定

やったこと

半年以上前に受講したudemyの講座をGo言語でやってみる。

【キカガク流】プログラミング力向上のためのPythonで学ぶアルゴリズム論（前編）
https://www.udemy.com/course/algorithm1/

この講座の学び

• いきなり書き始めないで、言葉で処理を組み立てる。
• はじめは最小の範囲で組み立てる。
• とりあえず動くコードを書く。
• そこからリファクタリングし、より品質を上げる。(今回はスピードの向上)

お題：素数判定

• 受け取った値までのすべての素数を表示するプログラムを作成する。
• 以下のような結果を期待する。

> go build main.go
> ./main
100   <-入力
1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97  <-出力

1回目

とりあえず動くところまで作ってみる。

処理の順序

i = 判定される数字
s = 判定するために割る数字
1. 2から判定したい数を繰り返しiに格納
2. [1 < s < i] の間でi÷sをして割り切れなければ素数を出力
3. [1 < s < i] の間でi÷sをして割り切れれば素数でないためループから抜ける

コード

簡易的に処理にかかった時間も計測しました。
何とか期待の結果が得られるよう完成

func main() {
    //1. 入力から素数判定したい数を受け取る
    var n int
    fmt.Scan(&n)

    // 時間の計測開始
    start := time.Now()
    // 1だけ出力しておく
    fmt.Print("1 ")

    for i := 2; i <= n; i++ {
        //2. 素数かどうかを判定する
        for s := 2; 0 == 0; s++ {
            //3. 素数であれば出力する
            if  i == s {
                fmt.Printf("%d ", i)
                break
            } else if i % s == 0 {
                break
            }
        }
    }
    // 時間の計測終了
    end := time.Now()
    fmt.Printf("\n%f秒\n",(end.Sub(start)).Seconds())
}

出力した値	かかった時間(秒)
10	0.000154
100	0.000201
1000	0.000517
10000	0.021293
100000	1.594362
1000000	130.868357

2回目（速度改善の講座を受講後）

毎度入力待ちになって値を入力するのが面倒なので、引数で素数判定する値を渡すよう修正。
すでに持っている素数から割る値を取り出すことで、効率よく計算できるよう修正。

処理の順序

素数か判定する数の上限値 ＝　n
素数か判定される数字　＝　i

• nを引数で受け取る
• 素数を格納するスライスを定義する。この時スライスの中身で割れたら素数と判定するため先に2を入れておく。
• 3 > i > n の数字をiに格納する。
  
  • falgをtrueで初期化する。
  • iをスライスの中身で繰り返し割り算する
    • 割り切れたらflagをfalseにしてループを抜ける
  • すべて割り切れなければ、素数のスライスに追加する。
    
• スライスの中身を出力する

コード

1回目は逐一素数と判定したものを出力していたが、素数を格納するためのスライスを作成。
また素数判定の結果をflagに格納することで分かりやすくなりました。

func main() {
    //引数で受け取る(デフォルトで100までの素数を出力)
    var n = flag.Int("num", 100, "")
    flag.Parse()
    //素数を格納するスライスを定義する。この時スライスの中身で割れたら素数と判定するため先に2を入れておく。
    result := []int{2}
    // 時間の計測開始
    start := time.Now()
    //3 > i > n の数字をiに格納する
    for i := 3; i <= *n; i++ {
        //falgをtrueで初期化する
        flag := true
        //iをスライスの中身で繰り返し割り算する
        for _, v := range result {
            //割り切れたらflagをfalseにしてループを抜ける
            if  i % v == 0 {
                flag = false
                break
            }
        }
        //すべて割り切れなければ、素数のスライスに追加する。
        if flag == true {
            result = append(result, i)
        }
    }

    //1を一番最初に追加する
    app := []int{1}
    result = append(app, result...)
    //スライスの中身を出力する
    for _, v := range result {
        fmt.Printf("%d ", v)
    }

    // 時間の計測終了
    end := time.Now()
    fmt.Printf("\n%f秒\n",(end.Sub(start)).Seconds())
}

出力した値	かかった時間(秒)
10	0.000365
100	0.000913
1000	0.004652
10000	0.016664
100000	0.369312
1000000	15.488318

3回目（さらに改善）

2回目は素数を割り出すために計算する回数を減らすことで速度向上できました。素数の求め方で検索すると、「判定したい数の平方根以下の数から調べればよい。」とあるため、もっと早くできそうです。

処理の順序

素数か判定する数の上限値 ＝　n
素数か判定される数字　＝　i

• nを引数で受け取る
• 素数を格納するスライスを定義する。この時スライスの中身で割れたら素数と判定するため先に2を入れておく。
• 3 > i > n の数字をiに格納する。
  
  • falgをtrueで初期化する。
  • iをスライスの中身で繰り返し割り算する
    • 割り切れたらflagをfalseにしてループを抜ける
    • 割る数が割られる数の平方根より大きくなったらtrueのままループを抜ける
  • すべて割り切れなければ、素数のスライスに追加する。
    
• スライスの中身を出力する

func main() {
    //引数で受け取る(デフォルトで100までの素数を出力)
    var n = flag.Int("num", 100, "")
    flag.Parse()
    //素数を格納するスライスを定義する。この時スライスの中身で割れたら素数と判定するため先に2を入れておく。
    result := []int{2}
    // 時間の計測開始
    start := time.Now()
    //3 > i > n の数字をiに格納する。 
    for i := 3; i <= *n; i++ {
        //falgをtrueで初期化する。
        flag := true
        //iをスライスの中身で繰り返し割り算する
        for _, v := range result {
            //vの2乗がiを上回ったらループを抜ける
            if v * v > i {                         //この行を追記
                break                              //この行を追記
            }                                      //この行を追記
            //割り切れたらflagをfalseにしてループを抜ける
            if  i % v == 0 {
                flag = false
                break
            }
        }
        //すべて割り切れなければ、素数のスライスに追加する。
        if flag == true {
            result = append(result, i)
        }
    }

    //1を一番最初に追加する
    app := []int{1}
    result = append(app, result...)
    //スライスの中身を出力する
    for _, v := range result {
        fmt.Printf("%d ", v)
    }

    // 時間の計測終了
    end := time.Now()
    fmt.Printf("\n%f秒\n",(end.Sub(start)).Seconds())
}

出力した値	かかった時間(秒)
10	0.000265
100	0.000470
1000	0.002642
10000	0.006644
100000	0.053357
1000000	0.482029

4回目おまけ(並行処理)

折角Go言語なので勉強がてら、並行処理をして高速化を図ろうとしましたが、持っている素数で割るということができなくなり逆に遅くなりました。4つの処理に分けましたが、もっと処理数を増やせば早くなるかもしれません。

func main() {
    //引数で受け取る(デフォルトで100までの素数を出力)
    var n = flag.Int("num", 100, "")
    flag.Parse()
    //処理の時間をなるべく均等になるように分配(ただし100より小さい数は正確に求められない)
    quarter := *n / 100
    minnum1, maxnum1 := 3, quarter*38
    minnum2, maxnum2 := quarter*38, quarter*62
    minnum3, maxnum3 := quarter*62, quarter*82
    minnum4, maxnum4 := quarter*82, *n+1
    var result1, result2, result3, result4 []int
    ch1, ch2, ch3, ch4 := make(chan bool), make(chan bool), make(chan bool), make(chan bool)
    // 時間の計測開始
    start := time.Now()

    //素数判定
    go func() {
        result1 = primeNumber(result1, minnum1, maxnum1)
        ch1 <- true
    }()
    go func() {
        result2 = primeNumber(result2, minnum2, maxnum2)
        ch2 <- true
    }()
    go func() {
        result3 = primeNumber(result3, minnum3, maxnum3)
        ch3 <- true
    }()
    go func() {
        result4 = primeNumber(result4, minnum4, maxnum4)
        ch4 <- true
    }()

    <-ch1
    <-ch2
    <-ch3
    <-ch4

    //1を一番最初に追加する
    app := []int{1, 2}
    result1 = append(app, result1...)
    //スライスの中身を出力する
    for _, v := range result1 {
        fmt.Printf("%d ", v)
    }
    for _, v := range result2 {
        fmt.Printf("%d ", v)
    }
    for _, v := range result3 {
        fmt.Printf("%d ", v)
    }
    for _, v := range result4 {
        fmt.Printf("%d ", v)
    }
    // 時間の計測終了
    end := time.Now()
    fmt.Printf("\n%f秒\n", (end.Sub(start)).Seconds())
}

func primeNumber(result []int, minnum int, maxnum int) []int {
    //minnum > i > maxnum の数字をiに格納する。
    for i := minnum; i < maxnum; i++ {
        //falgをtrueで初期化する。
        flag := true
        //iをスライスの中身で繰り返し割り算する
        for v := 2; ; v++ {
            //vの2乗がiを上回ったらループを抜ける
            if v*v > i { //この行を追記
                break //この行を追記
            } //この行を追記
            //割り切れたらflagをfalseにしてループを抜ける
            if i%v == 0 {
                flag = false
                break
            }
        }
        //すべて割り切れなければ、素数のスライスに追加する。
        if flag == true {
            result = append(result, i)
        }
    }
    return result
}

まとめ

1回目:すべての値で割って判定
2回目:求めた素数で割って判定
3回目:平方根以下の求めた素数で判定
4回目:並行処理で平方根以下の全ての数で素数判定

出力した値	1回目(秒)	2回目(秒)	3回目(秒)	4回目(秒)
10	0.000154	0.000365	0.000265	判定不能
10^3	0.000517	0.004652	0.002642	0.002725
10^4	0.021293	0.016664	0.006644	0.007438
10^5	1.594362	0.369312	0.053357	0.055468
10^6	130.868357	15.488318	0.482029	0.502561
10^7	測定不能	785.677291	4.943015	5.682649
10^8	測定不能	測定不能	63.365127	91.279915

今回udemyの速度改善の講座では2回目の改善のところまでの解説がありましたが、自分調べて改善していくとより高速にできました。Go言語なので並行処理でやってみましたが、最適なアルゴリズムが利用できず遅い上に効率も圧倒的に悪いという結果になってしまいました。また3回目のコードではなんとかO(n)に近づけることができました。

感想

私自身、絶賛勉強中のプログラミング初心者ですが、アルゴリズムの入門としてピッタリの内容だと思いました。また講座の中で常々行われている言語化という行為は、プログラミングで実現したいことと、プログラムをつなぐ大事なプロセスと感じ個人的に良い学びになりました。

参考

golangでかかった処理時間を計算するには？
【Go】基本文法④(配列・スライス)
Go言語(golang) flagパッケージでコマンドライン引数をパース
Go言語で二つのスライスを安全に結合する
Go言語 型変換 int ⇔ float64 #05
【Go】基本文法⑦(並行処理)