How can this code be better structured in Elixir?

Question

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?

One thing you can do for sure is avoid the ++ operator when you want to add an element to a list. Elixir lists are made of cons cells, so adding an element to the end of a list should be a O(n) operation while adding it to the head of the list is O(1). A common pattern is to prepend elements to a list ([new_el|list]) and use Enum.reverse/1 to reverse the list before using it. — whatyouhide
That's good to know, but in this case it doesn't make much of a difference. I'm guessing that's because the list of prime factors tends to be quite short (for 50,000,000 the list is [1, 2, 5]). — Steve Madsen
OK, another good suggestion, but the algorithm is the same in the other implementations. I feel like I'm missing a basic understanding of how to structure Elixir code to avoid performance problems. It doesn't seem like there should be such a wide gap between the Ruby implementation and a good Elixir implementation. — Steve Madsen
That code is certainly slow for large numbers, but I believe the main reason for it is the algorithmic complexity. Here's my quick&sloppy take on the solution which is most probably far from optimal but works much faster than the original code: gist.github.com/sasa1977/98e6465bf854a9d86cba — sasajuric
Raw speed is not the primary focus of Erlang, so if it's heavily CPU bound, I'd expect Elixir/Erlang to be slower than most mainstream languages. In this example, I suspect Ruby wins since you do a lot of iterations with C implemented Ruby functions (map, reject, compact), while Elixir iterations are standard Erlang bytecode. Also, (not relevant in this example), using time measures Erlang VM startup time which may affect the result. I really don't think this is a good example though, because once you optimize the code algorithmically, the difference may become insignificant. — sasajuric

José Valim José Valim · Accepted Answer · 2015-02-18T23:00:29

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)

:)

How can this code be better structured in Elixir?

2 Answers