Elixir
エラトステネスの篩

Elixirでエラトステネスの篩を実装してみた

More than 1 year has passed since last update.

先日参加させていただいた勉強会 Go&Elixirでつくる分散アプリケーション にて

エラトステネスの篩というアルゴリズムをGo言語で実装した例を紹介していました。

(実はその勉強会で初めてこのアルゴリズムを知りました ^^;)

エラトステネスの篩はある指定された整数以下の素数を見つけるためのアルゴリズムとなります。

詳細はWikipediaをご参照ください

勉強会での例ではGoのチャンネルを使って実装されていたので、

Elixirでは子プロセスを生成し、そちらで値のフィルタリングをしていくという

方法で実装みたいと思います。


実装


erastosthenes.exs

defmodule Erastosthenes do

def sieve(prime, next, last?) do
receive do
n when rem(n, prime) == 0 ->
sieve(prime, next, last?)
n ->
send next, n
next = if last? do
# 自身が最後の篩だったら次の篩を生成する
{pid, _} = spawn_monitor Erastosthenes, :sieve, [n, next, true]
pid
else
next
end
sieve(prime, next, false)
end
end

def output do
receive do
n ->
IO.puts "#{n} is prime."
output()
end
end
end

opid = spawn Erastosthenes, :output, []
{spid, _} = spawn_monitor Erastosthenes, :sieve, [2, opid, true]

2..100
|> Stream.map(&(send spid, &1))
|> Enum.to_list


それぞれの篩は以下の値を保持するようにしています

- 素数

- 次の篩、もしくは出力用プロセスのpid

- 自身が最後の篩かどうか

sieve を子プロセスとしてどんどん生成いき、

大元から渡された値を篩にかけていきます。

渡された値が自身の素数で割り切れなかったら次の素数の篩に送ります。

もし自身が最後の篩の場合、割り切れなかった値は

素数なので次の素数の篩を生成しています。

実行結果がこちら

$ iex

iex(1)> c"erastosthenes.exs"
3 is prime.
5 is prime.
7 is prime.
11 is prime.
13 is prime.
17 is prime.
19 is prime.
23 is prime.
29 is prime.
31 is prime.
37 is prime.
41 is prime.
[Erastosthenes]
43 is prime.
47 is prime.
53 is prime.
59 is prime.
61 is prime.
67 is prime.
71 is prime.
73 is prime.
79 is prime.
83 is prime.
89 is prime.
97 is prime.

親プロセスでreceiveしていないため、iexで実行しないと

全部出力するまえに実行が終了してしまうのでわざわざiexで実行しています :sweat:

また最初の素数である2だけは最初に篩を作ってあげる必要があるので、

出力に表示されていないです :sweat: :sweat:


まとめ的な何か

今回は生spawnを使って書いてみましたが、

sieve関数で状態を保持する必要があるのでAgentを使ったほうがよかったかなと

思っています。

また出力のとこも微妙になってしまったのがなんとも残念です。

(Elixir力が足りない。。。)

何かご指摘等いただけますと嬉しいです。