srowley

srowley

List traversal vs. recursive binary pattern-matching

I was working on the Luhn algorithm exercise on Exercism and took two approaches to the problem. Then I benchmarked them. I am curious to hear about which approach you would assume performed better.

As background (simplifying a bit), the algorithm involves:

  • Starting with a string of presumably digits and spaces
  • Strip the spaces
  • Perform a calculation on each number (which calculation depends on position in the stripped string)
  • Sum up the transformed numbers
  • Take the remainder of the sum divided by 10

My first approach was to strip the spaces, convert the number to a charlist then a list of integers, and traverse the list of digits to do the transformation, then Enum.sum/1 and divide.

My second approach was to strip the spaces, and recursively process the string by binary pattern-matching on the first character, performing the applicable calculation and accumulating a sum, then divide.

Which of these approaches would you expect to perform better in a simple Benchee-style test?

I am curious to hear what people think; if anyone is interested enough to respond with their reasoned take I’ll post the results (and the code so you can tell me what I did wrong either in the slower case or the benchmarking).

Most Liked

Eiji

Eiji

I believe that second one:

However your description is not enough clear for me …

  • Is stripping spaces the first thing you do?
  • How do you then fetch index?
  • Do you use something like String.split/2?

In my opinion not only index should be incremented on recursive pattern-matching, but also the calculation could be done in exactly same step.

This is what I have written in few minutes …
defmodule Example do
  def sample(string), do: string |> parse(0, [[]]) |> Enum.sum() |> Kernel.rem(10)

  defp parse("", _index, [[] | acc]), do: acc

  defp parse("", index, [last | tail]), do: [get_value(last, index) | tail]

  defp parse(<<" ", rest::binary>>, 0, [[]]), do: parse(rest, 0, [[]])

  defp parse(<<" ", rest::binary>>, index, [last | tail]) do
    parse(rest, index + 1, [[], get_value(last, index) | tail])
  end

  defp parse(<<digit::utf8, rest::binary>>, index, [last | tail]) when digit in ?0..?9 do
    parse(rest, index, [[digit | last] | tail])
  end

  defp get_value(list, index), do: list |> Enum.reverse() |> List.to_integer() |> calculate(index)

  defp calculate(integer, index), do: integer * index
end
Feel free to compare it with your current code.

In this code we have such 3 steps:

  1. Parsing - just simple recursive iteration
    At end of string and/or at any whitespace (except whitespaces at start) we need to reverse list (because of previously used [head | tail] optimization), convert it to integer and do some calculation based on the incremented (by any whitespaces except those at start) index.
  2. After that we are calling Enum.sum/1
  3. And finally calculatiing remainder of division by 10
srowley

srowley

Thanks for participating! I agree. There are some nuances to the algorithm but my second approach was reasonably close to what you offered. And here are the results (where original_luhn is the list version and string_luhn is the recursive pattern matching version:

Operating System: Linux
CPU Information: Intel(R) Core(TM) i5-9300H CPU @ 2.40GHz
Number of Available Cores: 8
Available memory: 15.79 GB
Elixir 1.10.3
Erlang 22.3.4.1

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 14 s

Benchmarking original_luhn...
Benchmarking string_luhn...

Name                    ips        average  deviation         median         99th %
original_luhn      440.61 K        2.27 μs   ±925.00%        2.10 μs        3.20 μs
string_luhn        325.14 K        3.08 μs  ±1930.38%        2.80 μs        3.70 μs

Comparison: 
original_luhn      440.61 K
string_luhn        325.14 K - 1.36x slower +0.81 μs

I found these results to be pretty surprising. I am wondering if the explanation is that I am unaware of something expensive in the string version, something optimized in the list version, or if I am benchmarking/interpreting the benchmark wrong.

Here is a link to the repo with both versions and a full explanation of the algorithm.

https://github.com/srowley/luhn

Where Next?

Popular in Discussions Top

andre1sk
A big advantage to Elixir is all the distributed goodness but for many applications running on multiple nodes having integrated Etcd, Zoo...
New
New
AngeloChecked
What learn first? Rust or Elixir Hi Elixir community! I’m here because i want learn a new language. I’m a junior developer and mainly i ...
New
Fl4m3Ph03n1x
Background This question comes mainly from my ignorance. Today is Black Friday, one of my favorite days of the year to buy books. One boo...
New
mmmrrr
Just saw that dhh announced https://hotwire.dev/ Is it just me or is this essentially live view? :smiley: Although I like the “iFrame-e...
New
lorenzo
Hey everone! I created a prototype for my app using Nodejs for the api. But the framework I chose wasnt great (in general theresnt any g...
New
jer
I’ve been using umbrellas for a while, and generally started off (on greenfield projects at least) by isolating subapps based on clearly ...
New
und0ck3d
Hello everyone! A few days ago I’ve created a topic here about how people were creating CMSs with Elixir and Phoenix. I’ve been studying...
New
dogweather
I wrote this comment on r/haskell, and it’s not popular there. :wink: But I think I’m on to something… Haskell reminds me of Java, and e...
New
slashdotdash
Phoenix Live View is now publicly available on GitHub. Here’s Chris McCord’s tweet announcing making it public.
New

Other popular topics Top

9mm
I am constructing a JSON object (map) and I need to conditionally set a field. I’m trying to write proper elixir-way code… and I’m at a l...
New
siddhant3030
Hi, I have to write a raw query for one of my project. But till now I have used ecto queries and don’t have much experience writing raw ...
New
lastday4you
I wanted to check elixir version in phoenix because i found that my elixir is 1.5 but when i use Enum.chunk_by it said the function is un...
New
chrismccord
Phoenix 1.4.0 released Phoenix 1.4 is out! This release ships with exciting new features, most notably with HTTP2 support, improved deve...
688 30877 112
New
JorisKok
I have a server on AWS, and was running a load test using artillery. When looking at the Phoenix dashboard I see the Ports going to 100% ...
New
joeerl
Hello again - after a longish gap I’ve decided I really must dig into Elixir and see what’s been happening here - so I have a few questio...
New
Emily
I have VueJS GUIs with the project generated using Webpack. I have Elixir modules that will need to be used by the VueJS GUIs. I forese...
New
aalberti333
As the title describes, I’m trying to run Enum.map() over a list of key/value pairs, where the value is a map. My data looks like this: ...
New
sergio_101
I am VERY much an elixir newbie. I have taken one elixir course and one phoenix course on Udemy. During that course, I saw the instructor...
New
jononomo
For some reason my phoenix channels are working for me in my local dev environment, but as soon as I deploy via Docker, I get a 403 error...
New

We're in Beta

About us Mission Statement