[Elixir] 並行して素数を求める

## 素数を求める

プログラミングElixir、第10章 p.105まで読んでそこまでの全ての演習問題を解きました。p.105の問題は素数を求める問題です。それぞれの言語で素数を求めるプログラムを書いてみると言語ごとの特徴が出てそれぞれ勉強になりますね。１つのプログラムでユニットテストも実行しました。

```elixir: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する、という工夫の余地がが多い処理になっています。

```elixir: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:
$ 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
```
８コアの全てが使われていて、だいたい５倍ぐらい速くなっています。

![win_task_mgr2.png](https://qiita-image-store.s3.amazonaws.com/0/11188/26c52bc8-3e68-171a-befc-61d329af7a0c.png)


簡単に並行プログラミングできて、素敵な言語です。