はじめに
関数型言語の Elixir で素数の無限リスト生成を実装します。
素数とは、２以上の自然数で、他の数字で割り切ることができないような数を表します。
Elixir では、Stream モジュールを利用することで、無限リストを遅延評価で生成することができます。
サンプルコード
実直な実装
実行速度をあまり考慮していない実装です。
実装の分かりやすさ重視です。
defmodule Example do
def prime_numbers() do
Stream.iterate(2, &(&1 + 1))
|> Stream.filter(&prime_number?/1)
end
defp prime_number?(2), do: true
defp prime_number?(n) do
prime_numbers()
|> Stream.take_while(&(&1 * &1 <= n))
|> Enum.all?(&(rem(n, &1) != 0))
end
end
Example.prime_numbers() |> Enum.take(10) |> IO.inspect()
Example.prime_numbers() |> Enum.at(9) |> IO.inspect()
Example.prime_numbers() |> Enum.at(999) |> IO.inspect()
Example.prime_numbers() |> Enum.at(9_999) |> IO.inspect()❯ time elixir example.exs
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
29
7919
104729
real 0m23.462s
user 0m23.183s
sys 0m0.161sAgent によるメモ化
Agent を利用して、生成済みのリストをキャッシュするようにしました。
6倍くらい速くなりましたが、まだイマイチな速度です。
defmodule Example do
def prime_numbers() do
{seed, ps} = Agent.get(__MODULE__, &(&1))
Stream.concat(ps, prime_numbers(seed))
end
def prime_numbers(seed) do
Stream.iterate(seed, &(&1 + 1))
|> Stream.filter(&prime_number?/1)
|> Stream.each(fn x -> Agent.update(__MODULE__, &({x + 1, elem(&1, 1) ++ [x]})) end)
end
def init() do
Agent.start_link(fn -> {2, []} end, name: __MODULE__)
end
defp prime_number?(2), do: true
defp prime_number?(n) do
prime_numbers()
|> Stream.take_while(&(&1 * &1 <= n))
|> Enum.all?(&(rem(n, &1) != 0))
end
end
Example.init()
Example.prime_numbers() |> Enum.take(10) |> IO.inspect()
Example.prime_numbers() |> Enum.at(9) |> IO.inspect()
Example.prime_numbers() |> Enum.at(999) |> IO.inspect()
Example.prime_numbers() |> Enum.at(9_999) |> IO.inspect()❯ time elixir example_memo.exs
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
29
7919
104729
real 0m4.154s
user 0m3.901s
sys 0m0.194s実行速度重視の実装
Stream.unfold を利用して、素数のリストを保持しながら列を生成します。
実装は少しわかりづらくなりますが、前述の例よりはだいぶ速いです。
defmodule Example do
def prime_numbers(), do: Stream.unfold({2, []}, &next_n/1)
defp next_n({n, ps}) do
if divisible_any?(n, ps) do
next_n({n + 1, ps})
else
{n, {n + 1, ps ++ [n]}}
end
end
defp divisible_any?(n, ps) do
ps
|> Stream.take_while(&(&1 * &1 <= n))
|> Enum.any?(&(rem(n, &1) == 0))
end
end
Example.prime_numbers() |> Enum.take(10) |> IO.inspect()
Example.prime_numbers() |> Enum.at(9) |> IO.inspect()
Example.prime_numbers() |> Enum.at(999) |> IO.inspect()
Example.prime_numbers() |> Enum.at(9_999) |> IO.inspect()❯ time elixir example_another.exs
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
29
7919
104729
real 0m0.831s
user 0m0.625s
sys 0m0.116s