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).
Trending in Discussions
Other Trending Topics
Chat & Discussions>Discussions
Latest on Elixir Forum
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #elixirconf-us
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #metaprogramming
- #hex
- #performance










First 2 of 2 Posts
Eiji
I believe that second one:
However your description is not enough clear for me …
String.split/2?In my opinion not only
indexshould 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 …
In this code we have such 3 steps:
At end of
stringand/or at anywhitespace(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 anywhitespacesexcept those at start)index.Enum.sum/1remainderof division by10srowley
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_luhnis the list version andstring_luhnis the recursive pattern matching version: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