素数

elixirで素数判定 (14 Oct 2013 | Tags: elixirで素数判定

Oct 14, 2013

elixirで素数判定

programing elixir 素数

概要

前回Scalaで実装したものと同じく、1<= X <=10^9 の範囲の自然数Xを渡されたとき、Xが素数か否かを判定します。

こちらも同様に判定には、試し割り法を使いました。

コード

↓のようになりました

解説

def isPrimeがメイン関数です。

与えられた数値numが、1 or 偶数ならfalseを返す。
↑以外の場合、3から数値numの平方根までのリストを生成して、sieveをコールする。

前回Scalaでは試し割りをループで実行しましたが、elixirでは再帰で実行しています。

というか、elixirではErlangと同じく条件ループがもとからありません。

同じようにリストの生成も、Scalaでは (x to y)の形式で行えましたが、elixirでは def makeListを再帰して生成しています。 Scalaと同じようにリストを生成するような便利な関数があるのかもしれませんが、見つけられなかったので。。

def seiveのコールでは、第１引数のリストが空でない場合、def seive(［h｜t］, num)、第１引数のリストが空の場合、def seive(［］, _)にマッチします。

def seive([h｜t], num) では、

リストの先頭の値hで数値numで割り切れる場合、素数ではないのでfalseを返し、
割り切れない場合、先頭以外のリストtと数値numを再度seiveに渡します。

最終的に、リスト末尾まで試し割りし、割り切れなかった場合、def seive(［］, _)にマッチし、trueが帰ります。

Scalaで書いたものと比較して、関数が増えていますが、中の処理自体はよりさっぱりした感じになりました。まだelixir慣れしていないので、もっと良い書き方ができるのだろうとは思いますが、今回はこんなところで。

Link

Latest post:

Recent Books:

)

Scalaで素数判定【追記アリ】 (09 Oct 2013 | Tags: Scalaで素数判定【追記アリ】

Oct 9, 2013

Scalaで素数判定【追記アリ】

programing Scala 素数

概要

今回は、1<= X <=10^9 の範囲の自然数Xを渡されたとき、Xが素数か否かを判定します。

判定には、試し割り法を使いました。

コード

↓のようになりました

解説

処理のおおまかな流れは以下のような感じ

対象の数字Xを受け取る
Xが１か偶数だったら、素数ではない
3からXの平方根までのリストを作る
リストから偶数を除去
リストの先頭から順に、Xがその数で割り切れるかどうかを調べる
割り切れたら、素数ではない
割り切れずに、リストの末尾まで到達したら、素数
結果を表示

(x to y).filter().foreach() の形式で書きたかったのでこんな設計になりました。なんとなくScalaっぽくてこの書き方が好きなので

foreachの中の処理で割り切れた場合、明示的なreturnでループを抜けています

対象の数が大きくなると生成されるリストも大きくなり、ループが長くなるので filterの条件を増やして(ex. 3, 5, 7, 11,,,)リストが短くなるようにしてみたりもしたんですが、早くなりませんでした、というか若干遅くなった。。。

filterを追加することでループの回数を減らすことの損益分岐点は、思ったより低かったようです。無念

追記

@gakuzzzzさんにコメントいただき、コードを改良しました。

@modal_soul (3L to sqrt(num).toLong by 2) とかすると filter が必要なくなって速くなりそうですね。
— がくぞ (@gakuzzzz) October 9, 2013

コード・その２

(x to y by 2)とすることで、2刻みでリストを生成するので、最初に生成されるリストが短くできる&filterが省略できるわけですね。

Before:140ms, After:130ms だいたい10msほど速くなりました。

コード・その３

returnを使うと例外で遅くなるのでは？という話もあったので、forallを使うパターンも試してみました。結果は↑とほぼ同じ結果になりました。 forallがbooleanを返すので、returnのためのtrue/falseがなくなったので、コードはだいぶ綺麗になった気がします。

Link

Latest post:

Recent Books:

)