It’s almost twice faster than Elixir’s
Quoting the example in the problem: > If we list all the natural numbers up to but not including 20 that are > multiples of either 3 or 5, we get 3, 5, 6 and 9, 10, 12, 15, and 18. > The sum of these multiples is 78.
The solution for the problem itself is simple, whereby we can filter the list of numbers which is a multiple of one of the factors. I have defined a private function
is_multiple?/2 which returns
true if a number is a multiple of the factors or
def to(limit, factors) do 1..limit-1 |> Enum.filter(&(is_multiple?(&1, factors))) |> Enum.sum end
Now the interesting part happens in
Enum.any?/2 which returns true as soon as an element of a list satisfies the predicate function. In this case, the predicate is simply checking that the remainder of the number divided by the factor is 0.
defp is_multiple?(num, factors) do factors |> Enum.any?(&(rem(num, &1) == 0)) end
This works, but then I started thinking about how to write it in a more Elixir way, so here comes pattern matching with recursion. It checks if the number is a multiple of the first factor in the list. If so, it returns true, otherwise, it recurses through the list until there is no more factor left in the list.
defp is_multiple?(num, ), do: false defp is_multiple?(num, [factor | _]) when rem(num, factor) == 0, do: true defp is_multiple?(num, [_ | factors]), do: is_multiple?(num, factors)
This works too! All fine and dandy!
Then comes the next question of how do they perform at scale. I wanted to know how do the performance differ, so I wrote a simple test with 10 million as the limit and the list of factors being the first 1000 prime numbers.
test "very large number and many factors" do n = 10_000_000 multiples = primes(1000) assert SumOfMultiples.to(n, multiples) == 499999500000 end def is_prime(x), do: (2..x |> Enum.filter(fn a -> rem(x, a) == 0 end) |> length()) == 1 def prime(n), do: Stream.interval(1) |> Stream.drop(2) |> Stream.filter(&is_prime/1) |> Enum.take(n)
The result surprised me. With
Enum.any?, the test completed in just after a minute.
SumOfMultiplesTest * test very large number and many prime factors (62269.0ms)
With pattern matching, the test took almost half the time and completed in just over 33 seconds.
SumOfMultiplesTest * test very large number and many prime factors (33141.2ms)
This is a promising finding and it makes me more intrigued by the Elixir pattern matching capability.