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).

First 2 of 2 Posts Switch mode

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 OP

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

— All posts loaded —

Where Next?

Trending in Discussions Top

AstonJ
As the title says, please share what you’ve been up to with Elixir. Whether that’s been learning it, looking into it, making stuff with i...
2977 91561 914
New
byu
@chrismccord : I just saw the Extract AGENTS.md from Phoenix.new into phx.new generator commit to the phoenix project. My initial shotgu...
New
arcanemachine
I was working on an Ecto migration and I needed a timestamp. So, for the nth time, I looked up the different data types for timestamps, a...
New
AstonJ
Just a general thread to post chat/news/info relating to AI/ML stuff that may be relevant for Nx now or in the future. Got anything to sh...
New
type1fool
I just stumbled on a newly redesigned elixir-lang.org. :tada: It looks like @Software_Mansion did the work, and I think it is generally a...
New
juhalehtonen
There has been a thread to discuss the Stack Overflow Developer Survey on this forum every year since 2018, so here’s yet another one for...
New
alexslade
Fly’s CEO posted this recently - Turn And Face The Strange · The Fly Blog It says that Fly is going all-in on sprites, which is a worry ...
New

Other Trending Topics Top

JesseHerrick
Hey, I’m Jesse and I’m the main contributor behind Dexter, a full-featured, lightning-fast Elixir LSP optimized for large codebases. It s...
New
jimsynz
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
Damirados
Hello everyone. After busy few months I am happy to announce v0.1.0 of Emerge &amp; Solve. They are GUI (Emerge) and State management (S...
New
ausimian
Emily is an Elixir library that runs Nx computations on Apple’s MLX. Install it as the default Nx backend and Nx, defn, Axon, Nx.Serving,...
New
akoutmos
@hugobarauna and I (Alex Koutmos) have been hard at work on writing a book on Nerves that takes you from simply blinking LEDs to building...
New
wintermeyer
There are three potential reasons for members of this forum to have a look at https://vutuv.de You are tired or annoyed of LinkedIn. Yo...
New

We're in Beta

About us Mission Statement