素数を求める
プログラミングElixir、第10章 p.105まで読んでそこまでの全ての演習問題を解きました。p.105の問題は素数を求める問題です。それぞれの言語で素数を求めるプログラムを書いてみると言語ごとの特徴が出てそれぞれ勉強になりますね。１つのプログラムでユニットテストも実行しました。
prime.exs
# prime.exs
_ = """
here document
here document
here document
"""
ExUnit.start()
defmodule MyUnitTest do
@upto 10000
use ExUnit.Case
test "prime test" do
defmodule Prime do
import Integer
def span(m,_) when not is_integer(m), do: raise "integer is required"
def span(_,n) when not is_integer(n), do: raise "integer is required"
def span(m,n) when m <= n, do: (m..n) |> Enum.to_list
def span(_,_), do: []
def is_prime?(n) when not is_integer(n), do: raise "integer is required"
def is_prime?(n) when n < 2, do: false
def is_prime?(2), do: true
def is_prime?(n) when is_even(n), do: false
def is_prime?(n) do
list = for i <- span(3,n-1), i*i <= n, is_odd(i), do: rem(n,i)
list |> Enum.map(&(&1 != 0)) |> Enum.all?
end
def primes(n) when n < 2, do: []
def primes(n), do: span(2,n) |> Enum.filter(&is_prime?/1)
def prime_count(n), do: primes(n) |> Enum.count()
end
assert Prime.is_prime?(2)
assert Prime.is_prime?(3)
assert not Prime.is_prime?(4)
assert Prime.is_prime?(5)
assert not Prime.is_prime?(6)
assert Prime.is_prime?(7)
assert not Prime.is_prime?(9)
assert [] |> Enum.all?
assert [true] |> Enum.all?
assert [true,true,true,false,true,true,false]
== [3,5,7,9,11,13,15] |> Enum.map(&Prime.is_prime?/1)
assert [2,3,4,5,6,7,8,9] == Prime.span(2,9)
assert [1,0] == for i <- Prime.span(2,3), do: rem(9,i)
assert [true,false] == [1,0] |> Enum.map(&(&1 != 0))
assert false == [1,0] |> Enum.map(&(&1 != 0)) |> Enum.all?
assert Prime.primes(10) == [2,3,5,7]
assert Prime.primes(100)
== [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]
assert Prime.prime_count(100) == 25
assert Prime.prime_count(1000) == 168
IO.puts "---- single ----"
# IO.inspect Prime.prime_count(10000)
IO.inspect :timer.tc(Prime, :prime_count, [10000])
Elixirは、Haskellと違って動的型付け言語なので、is_integerで与えられた引数が整数型か調べたりしています。
nが素数かどうか判定する関数ができたので、n個のプロセスを作って、それぞれ並行して素数を求めさせるようにします。
並行処理そのものは、n個のプロセスを起動したあとに、n個の結果を受信したあと、sortする、という工夫の余地がが多い処理になっています。
prime.exs続き
defmodule ConcurrentPrime do
def times(1,f), do: [f.()]
def times(n,f), do: [f.() | times(n-1,f)]
def times_with_index(1,f), do: [f.(1)]
def times_with_index(n,f), do: [f.(n) | times_with_index(n-1,f)]
defp chore(n) do
{ Prime.is_prime?(n), n }
end
defp spawn_child(parent) do
fn(n) ->
spawn fn -> send parent, chore(n) end
end
end
def concurrentPrimes(upto) do
parent = self()
_pids = times_with_index(upto, spawn_child(parent))
times(upto, fn ->
receive do
{:true, n } -> n
{_, _ } -> 0
end
end)
|> Enum.filter(&(&1 > 0)) |> Enum.sort
end
def primes(n), do: concurrentPrimes(n)
def prime_count(n), do: primes(n) |> Enum.count()
end
IO.puts "---- concurrent ----"
# IO.inspect ConcurrentPrime.prime_count(10000)
IO.inspect :timer.tc(ConcurrentPrime, :prime_count, [10000])
end
end
:timer.tc は実行結果を２つの要素が入ったタプルで返し、１つめの要素が実行時間、２つめが関数の戻り値です。
実行結果
$ elixir pp.exs
---- single ----
{2952219, 1229}
---- concurrent ----
{532454, 1229}
.
Finished in 4.8 seconds (0.08s on load, 4.7s on tests)
1 test, 0 failures
Randomized with seed 329355
８コアの全てが使われていて、だいたい５倍ぐらい速くなっています。
簡単に並行プログラミングできて、素敵な言語です。