How can this code be better structured in Elixir?

Question

I study Elixir as my first functional style language. As the first simple project to familiarize myself with the environment and syntax, I decided to create a simple program that calculates the main factors for the 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 it works quite slowly. On my laptop, the startup time is about 11 seconds to calculate the main odds of 50,000,000.

As I read more, it seems like this original solution is not very similar to Elixir. So I redid the code:

 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)}" 

The typical runtime of this code to calculate the basic coefficients of 50,000,000 is much worse: more than 17 seconds.

I built equivalent programs in Swift and Ruby. Optimized Swift runs in just 0.5 seconds, and Ruby (2.2 and is never known for its speed) runs a little over 6 seconds.

My main question is: how should Elixir's code be structured more idiomatic and avoid the performance issues that I see?

I also left some problems associated with such a simple problem, you can write Elixir code, which is very different from the efficiency. Perhaps this is mainly my inexperience in functional styles?

Answer 1

Let me start with a quick bombast, then we get to the answer. I believe that we are worried about the wrong here. Once you posted the Ruby code, my first thought was: why does Elixir code not look as simple as Ruby?

First solve this problem:

 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. Can I run this clean version? 3.5 seconds on my car (compared to 24 seconds earlier).

Now with cleaner code, it’s easier to compare what is wrong with your implementation. Your _factors function is actually _factors_and_prime , because you are already checking to see if there is a number. So when do you check is_prime? , do you actually compute “factors and simplicity”, which are much more expensive to compute than the actual “factors,” since in the end it calls and recursively calls is_prime? .

Someone once said:

• Make it work.
• Make it beautiful.
• Do it fast (if necessary)

:)

Answer 2

Optimized operation for a second:

 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 

Bonus tests:

 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 

As a result, we get a much more competent / idiomatic elixir, reducing the problem area. Further optimization can be achieved, but possibly with a loss of readability without a significant increase in performance. In addition, since documents and tests are built into the platform, they are also painless and make the code more readable. :)