【Elixir】素数の無限リスト【関数型】

  • 2021年12月23日
  • 2022年8月8日
  • Elixir
  • 33View
  • 0件

はじめに

関数型言語の Elixir で素数の無限リスト生成を実装します。

素数とは、2以上の自然数で、他の数字で割り切ることができないような数を表します。
Elixir では、Stream モジュールを利用することで、無限リストを遅延評価で生成することができます。

Wikipedia 素数

サンプルコード

実直な実装

実行速度をあまり考慮していない実装です。
実装の分かりやすさ重視です。

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.161s

Agent によるメモ化

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

Elixirの最新記事8件