Nimでエラトステネスの篩をふるってみた

11768 ワード
エラトステネスの篩 Nim Nim テキストリンク

寒くなってきた今日この頃・・・みなさん、素数 数えてますか！？

おそらくほとんどの人はパニックになったときに素数を数えて落ち着こうとするでしょう。

でも、こんな経験ありませんか？

「落ち着け……心を平静にして、考えるんだ……こんな時どうするべきか落ち着くんだ……『素数』を数えて落ち着くんだ……『素数』は1と自分の数、でしか割ることのできない孤独な数字……わたしに勇気を与えてくれる。。。2・・・3・・・5・・・7・・・ 9・・・ん？9って素数？次11か？てか17ってぶっちゃけ6あたりで割れるんじゃね？」

はい、そんなあなたにお役立ちの1品をご紹介します。

その名も『エラトステネスの篩』！

エラトステネスの篩とは

エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。
出典: 　エラトステネスの篩 - フリー百科事典『ウィキペディア（Wikipedia）』

以下のような手順で素数を見つけることができます。

  1. 1を除く自然数を並べる

  2. 2 の倍数の塗りつぶす

  3. 塗りつぶされていない、次の小さい数字を見つけて、その倍数を塗り潰す。ここでは 3

  4. 以後同じ様に 5 7 ... の倍数も塗りつぶしていきます (4 6 など は塗りつぶされているので飛ばす)

  5. 塗りつぶされずに残った数字が、 1と自分の数、でしか割ることのできない孤独な数字 つまり『素数』になるんだよぉぉぉぉぉ！

はい、ここまで来たら画像の塗りつぶしミスに気づくぐらい落ち着いたと思います
(途中で 39 塗りつぶし忘れてました 😇)

見つけた数字が篩になっていくイメージですね！

ではこれを Nim で実装してみたいと思います

Nim とは

始まる前から先手/後手どちらが勝つか決まっているクソゲー・・・ではなく
「効率的で表現豊かで優雅」であるように設計されているプログラミング言語になります

特徴

  • 型推論がある静的な型付け
  • C言語の処理スピード向上＆メモリの効率性アップ
  • Python・Rubyのような構文
  • 強いメタプログラミング
  • 多言語に対応している
  • GC(ガベージコレクション)の性能が高い

出典: Nimの特徴や使い方をわかりやすく解説！Nimを学ぶメリットと多言語との連携方法は？Rustとの違いも比較してご紹介。

はい、とても良さそうな感じがしますね

他詳しく知りたい方は以下の記事あたりがおすすめです
Nim Programming Language
Nimを知ってほしい - Qiita

インストール

この記事を書いている段階でNimのことはNimって名前しか知りません。
つまりは今が一番楽しい状態ってことですね！

まずはとりまかけつけ一杯します 

$ brew install nim
hello.nim
stdout.write "Hello, Nim👑"
terminal
# nim c でコンパイル
$ nim c hello.nim
...(省略)...
$ ./hello
Hello, Nim👑

# -rをつけるとコンパイル&実行
$ nim c -r hello.nim
...(省略)...
Hello, Nim👑

エラトステネスの篩を書いてみた

Nim を完全理解したので、さっそく『素数』を数えるんだよぉぉぉぉぉぉぉぉ！

sieve_of_eratosthenes.nim
var n = 1000

var primes: seq[int]
primes = @[]
var x = newSeq[int](n + 1)
for i in countup(2, n):
  if x[i] == 0:
    # 0だった場合はまだ素数
    primes.add(i)

    # i の倍数を埋める
    for j in countup(i, n, i):
      x[j] = i

stdout.write primes

はい、なんかあっさり書けちゃいました

var primes: seq[int] は可変長列の配列(シーケンス型)を表しています。
Nimは arrayもあるのですが、こちらはコンパイルの時点で配列サイズを指定してあげないとだめなようです。

var primes: seq[int]だけでは宣言だけなので、 primes = @[] で初期化してあげています。
@[]を使うことでヒープ領域にオブジェクトを作成するため、諸々都合がいいようです。

var x = newSeq[int](n+1)こちらもシーケンスを作成しています。
var primes と違ってこちらは配列サイズを指定しています。
各配列の要素は 0 で初期化されていました。

for if あたりは Python と似たようなノリですね。

特に実行などでつまづくこともなく、あっさり書けたのでびっくりです

proc sieve_of_eratothenes(n: int): seq[int] =
  var primes: seq[int]
  primes = @[]
  var x = newSeq[int](n + 1)
  for i in countup(2, n):
    if x[i] == 0:
      # 0だった場合はまだ未探索
      primes.add(i)

      # i の倍数を埋める
      for j in countup(i, n, i):
        x[j] = i

  primes

var n = 1000
stdout.write sieve_of_eratothenes(n)

せっかくなので、関数にしたバージョン
Nimでは基本的にプロシージャと呼ぶのかな・・・？

パフォーマンスはこちら
n = 10^6 を指定しています。

terminal
#Nim
$ time ./sieve_of_eratosthenes
78498
________________________________________________________
Executed in   38.62 millis    fish           external
   usr time   28.99 millis  149.00 micros   28.84 millis
   sys time    6.76 millis  858.00 micros    5.90 millis

#Python
$ time python sieve_of_eratosthenes.py
78498
________________________________________________________
Executed in  566.53 millis    fish           external
   usr time  489.83 millis  113.00 micros  489.72 millis
   sys time   43.51 millis  629.00 micros   42.88 millis

さすがに爆速ですね
Elixirとは泣きそうになるので比較しません

まとめ

至高の言語と名高いNim
業務では使うことはないと思いますが、WEBサーバなども構築できるみたいです。
Python, Rubyのような自由な文法を持ちつつ、高いパフォーマンスを誇るなんて、グレートですよこいつはァ

この冬Nim & アルゴリズムで遊んでみてはいかがでしょうか！！