elixir - 如何在 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 运行时间仅 0.5 多秒，而 Ruby(2.2，从未以速度着称)运行时间略高于 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? 时，您实际上是在计算“因子和素数”，这比实际的“因子”要昂贵得多，因为它最终会调用 is_prime?再次递归。

正如某人在某处所说:

让它工作

让它美丽

使其快速(如有必要)

:)