如何在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)}"

它有效,但运行得相当慢.在我的笔记本电脑上,运行时间约为11秒,以计算50,000,000的素因子.

在我阅读更多内容时,似乎这个原始解决方案并不像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?再次以递归方式调用.

作为某人,在某处,说:

1. 让它起作用
2. 让它美丽
3. 快点(如有必要)

:)

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

我们最终通过减少问题领域来编写更有文化/惯用的灵药.可以实现进一步的优化,但可能在没有显着性能增益的情况下丧失可读性.此外,随着文档和测试内置到平台中,包括它们是无痛的并且使代码更具可读性.:)