如何在 Elixir 中更好地组织这段代码？

Question

我正在学习 Elixir 作为我的第一门函数式语言。作为熟悉环境和语法的第一个简单项目，我选择构建一个简单的程序来计算命令行上提供的数字的质因数。这是我的第一个解决方案：

defmodule Prime do
  defp is_factor?(number, divisor) do
    cond do
      rem(number, divisor) == 0 -> divisor
      true                      -> nil
    end
  end

  defp not_nil?(thing) do
    !is_nil(thing)
  end

  def factors(number) when number == 1 do
    []
  end

  def factors(number) do
    1..div(number, 2)
      |> Enum.map(&(is_factor?(number, &1)))
      |> Enum.filter(&not_nil?/1)
  end

  def is_prime?(number) when number == 1 do
    true
  end

  def is_prime?(number) do
    factors(number) == [1]
  end

  def prime_factors(number) do
    factors(number)
      |> Enum.filter(&is_prime?/1)
  end
end

input = hd(System.argv)
number = String.strip(input) |> String.to_integer
IO.puts "Prime factors of #{number} are #{inspect Prime.prime_factors(number)}"

它有效，但运行速度相当慢。在我的笔记本电脑上，运行计算 50,000,000 的质因数大约需要 11 秒。

随着我了解更多，这个原始解决方案似乎不太像 Elixir。所以我将代码重组为：

defmodule PrimeFactors do
  def of(n) do
    _factors(n, div(n, 2))
  end

  defp _factors(_n, 1) do
    [1]
  end
  defp _factors(n, divisor) when rem(n, divisor) == 0 do
    cond do
      is_prime?(divisor) -> _factors(n, divisor - 1) ++ [divisor]
      true               -> _factors(n, divisor - 1)
    end
  end
  defp _factors(n, divisor) do
    _factors(n, divisor - 1)
  end

  defp is_prime?(1) do
    true
  end
  defp is_prime?(n) do
    of(n) == [1]
  end
end

input = hd(System.argv)
number = String.strip(input) |> String.to_integer
IO.puts "Prime factors of #{number} are #{inspect PrimeFactors.of(number)}"

此代码计算 50,000,000 的质因数的典型运行时间要差得多：超过 17 秒。

我在 Swift 和 Ruby 中构建了等效程序。优化 Swift 运行s 仅需 0.5 秒多一点，Ruby（2.2，但从未以速度着称）运行s 仅需 6 秒多一点。

我的主要问题是：Elixir 代码的结构应该如何更加地道并避免我遇到的性能问题？

我还有一些顾虑，考虑到这样一个简单的问题，可能会编写出效率差异很大的 Elixir 代码。或许这主要是我对功能性风格展示经验不足？

Answer 1

让我先快速吐槽一下，然后我们将转向答案。我相信我们在这里担心的是错误的事情。一旦你发布了 Ruby 代码，我的第一个想法是：为什么 Elixir 代码看起来不像 Ruby 那样干净？

我们先解决这个问题：

defmodule PrimeFactors do
  def of(n) do
    factors(n, div(n, 2)) |> Enum.filter(&is_prime?/1)
  end

  def factors(1, _), do: [1]
  def factors(_, 1), do: [1]
  def factors(n, i) do
    if rem(n, i) == 0 do
      [i|factors(n, i-1)]
    else
      factors(n, i-1)
    end
  end

  def is_prime?(n) do
    factors(n, div(n, 2)) == [1]
  end
end

IO.inspect PrimeFactors.of(50_000_000)

好多了。让我们运行这个更干净的版本？在我的机器上 3.5 秒（与之前机器的 24 秒相比）。

现在有了更简洁的代码，可以更轻松地比较您的实现中的错误。您的 _factors 函数实际上是 _factors_and_prime 因为您已经在检查其中的数字是否为素数。因此，当您检查 is_prime? 时，您实际上是在计算 "factors and prime"，这比实际的 "factors" 计算成本高得多，因为它最终会再次递归调用 is_prime?。

正如某人在某处所说：

让它发挥作用
让它美丽
加快速度（如有必要）

:)

Answer 2

优化后的工作时间不到一秒：

defmodule PF do

  @doc "Calculates the unique prime factors of a number"
  def of(num) do
    prime_factors(num)
    |> Enum.uniq
  end

  @doc """
  Calculates all prime factors of a number by finding a low factor
  and then recursively calculating the factors of the high factor.
  Skips all evens except 2.
  Could be further optimized by only using known primes to find factors.
  """
  def prime_factors(num , next \ 2)
  def prime_factors(num, 2) do
    cond do
      rem(num, 2) == 0 -> [2 | prime_factors(div(num, 2))]
      4 > num          -> [num]
      true             -> prime_factors(num, 3)
    end
  end
  def prime_factors(num, next) do
    cond do
      rem(num, next) == 0 -> [next | prime_factors(div(num, next))]
      next + next > num   -> [num]
      true                -> prime_factors(num, next + 2)
    end
  end

end

奖金、测试：

ExUnit.start

defmodule PFTest do
  use ExUnit.Case

  test "prime factors are correct" do
    numbers = [4, 15, 22, 100, 1000, 2398, 293487,
               32409850, 95810934857, 50_000_000]
    Enum.map(numbers, fn (num) ->
      assert num == Enum.reduce(PF.prime_factors(num), &*/2)
    end)
  end
end

我们最终通过减少问题领域写出了更多 literate/idiomatic 长生不老药。可以实现进一步的优化，但可能会在没有显着性能提升的情况下损失可读性。此外，由于文档和测试内置于平台中，因此包含它们是无痛的，并使代码更具可读性。 :)

如何在 Elixir 中更好地组织这段代码？

How can this code be better structured in Elixir?

elixir