It’s almost twice faster than Elixir’s Enum.any?/2.

That’s an observation I had while doing an Elixir exercise on Exercism. In the exercise Sum of Multiples, I had to calculate the sum of numbers from 1 to n, which are multiples of any given factors.

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 false otherwise.

def to(limit, factors) do
  1..limit-1
  |> Enum.filter(&(is_multiple?(&1, factors)))
  |> Enum.sum
end

Now the interesting part happens in is_multiple?/2.

Coming from Ruby & Javascript background, my first instinct is to use 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.