How can this code be better structured in Elixir?

elixir

Solution

Let me start with a quick rant then we will move to the answer. I believe we are worrying about the wrong thing here. Once you posted the Ruby code, my first thought was: why does the Elixir code does not look as clean as the Ruby one?

Let's solve this problem first:

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)

Much better. Let's run this cleaner version? 3.5 seconds on my machine (compared to 24 seconds of the earlier one).

Now with a cleaner code, it is easier to compare what is wrong in your implementation. Your `_factors` function is actually `_factors_and_prime` because you are already checking if the number is prime in there. So when you check for `is_prime?`, you are actually computing "factors and prime" which is much more expensive to calculate than the actual "factors" since it ends up calling `is_prime?` again and recursively.

As someone, somewhere, said:

- Make it work

- Make it beautiful

- Make it fast (if necessary)

:)

Problem

I'm learning Elixir as my first functional-style language. As a first simple project to familiarize myself with the environment and syntax, I chose to build a simple program that computes the prime factors for a number provided on the command line. This is my first solution: ``` 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)}" ``` It works, but runs rather slowly. On my laptop, run times are around 11 seconds to compute the prime factors of 50,000,000. As I read more, it seems like this original solution is not very Elixir-like. So I restructured the code to this: ``` 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)}" ``` Typical run time of this code to compute the prime factors of 50,000,000 is substantially worse: over 17 seconds. I built equivalent programs in Swift and Ruby. Optimized Swift runs in just over 0.5 seconds, and Ruby (2.2, and never known for its speed) runs in a bit over 6 seconds. My primary question is: How should the Elixir code be structured to be more idiomatic and to avoid the performance problems I'm seeing? I'm also left with some concerns that given such a simple problem, it's possible to write Elixir code that varies wildly in efficiency. Perhaps this is mostly my inexperience in functional styles showing?

Original source