Generating 5,000+ random strings, improving performance by an order of magnitude, but can it be better?

I’m currently building an app where I’ll be creating random discount codes in bulk. Probably up to 5,000 at a time.

The business rules are the discount codes should be 19 characters long and should be broken up in groups of 4 characters like this XXXX-XXXX-XXXX-XXXX and they should only be composed of upper case letters and numbers.

Ideally, the entire charset should be CDEFGHJKLMNPQRTUVWXYZ23679. The missing letters and numbers are to avoid situations where a user might not quickly be able to tell if it’s a 0 or O, 5 or S, etc… So I removed a bunch of problem characters.

I’m still quite new to Elixir but a first shot implementation I came up with (with some Googling, etc.) was this:

 def random_code() do
    charset = "CDEFGHJKLMNPQRTUVWXYZ23679" |> String.split("", trim: true)

    random_chars = Enum.reduce((0..16), [], fn (_i, acc) ->
      [Enum.random(charset) | acc]
    end) |> Enum.join("")

    group_a = String.slice(random_chars, 1..4)
    group_b = String.slice(random_chars, 5..8)
    group_c = String.slice(random_chars, 9..12)
    group_d = String.slice(random_chars, 13..16)

    "#{group_a}-#{group_b}-#{group_c}-#{group_d}"
   end

On an i5 3.2ghz quad core running in Docker, that code was able to generate 5,000 codes in about 730ms (no DB writes). Not too shabby, but I’m not just looking to complete my app and ship it. I want to really learn Elixir and Erlang along the way, so I took some time looking up alternative solutions.

Here’s another implementation that was roughly 10x faster, which generated 5,000 codes in 70ms:

  defp generate_strong_random_string(length, case \\ :upper) do
    # TODO: limit this to charset: CDEFGHJKLMNPQRTUVWXYZ23679
    :crypto.strong_rand_bytes(length)
    |> Base.encode32(case: case)
    |> binary_part(0, length)
  end

  def generate_random_discount_code() do
    group_a = generate_strong_random_string(4)
    group_b = generate_strong_random_string(4)
    group_c = generate_strong_random_string(4)
    group_d = generate_strong_random_string(4)

    "#{group_a}-#{group_b}-#{group_c}-#{group_d}"
  end

As you can see, I kind of hit a brick wall in how to implement a custom character set into the faster solution.

So my questions to you are:

  1. How can I use my custom character set?
  2. Is there a different / better way to do this?

Side note:

For benchmarking, I Googled around and found this:

defmodule TimeFrame do
  defmacro execute(name, units \\ :microsecond, do: yield) do
    quote do
      start = System.monotonic_time(unquote(units))
      result = unquote(yield)
      time_spent = System.monotonic_time(unquote(units)) - start
      IO.puts("Executed #{unquote(name)} in #{time_spent} #{unquote(units)}")
      result
    end
  end
end

# And then you use it like this:

require TimeFrame 

def random_codes() do      
  TimeFrame.execute "original" do
    for x <- 0..4999 do
      random_code()
    end
  end

  TimeFrame.execute "improved" do
    for x <- 0..4999 do
      generate_random_discount_code()
    end
  end
end
2 Likes

I’ve put up a project here with the two versions you wrote and Benchee. Benchee is important because benchmarking stuff properly can be tricky, and Benchee has done a good job there. Here’s the initial results:

Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-7920HQ CPU @ 3.10GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.8.1
Erlang 21.2.2

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

Benchmarking v1...
Benchmarking v2...

Name           ips        average  deviation         median         99th %
v2        163.08 K        6.13 μs   ±547.42%           5 μs          18 μs
v1         10.01 K       99.93 μs    ±18.27%          96 μs         185 μs

Comparison: 
v2        163.08 K
v1         10.01 K - 16.30x slower +93.79 μs

I’ll report back with a V3 that aims to be faster.

Noticeably though, your :crypto version is closer to 16x faster, although it also doesn’t meet the requirements.

7 Likes

Oh wow, thanks. The benchee results are a lot nicer to see.

Yeah, in the 2nd solution I am not sure how to limit the charset while using the raw erlang modules. Definitely open to anyone willing to modify it for that.

I did a much sloppier job than @benwilson512 – his code is very fast. Still, mine respects your charset.

Given this module:

defmodule RandomCode do
  @charset 'CDEFGHJKLMNPQRTUVWXYZ23679'

  def fragment(size) when size > 0 do
    for _ <- 1..size, into: '', do: Enum.random(@charset)
  end

  def original_generate() do
    charset = "CDEFGHJKLMNPQRTUVWXYZ23679" |> String.split("", trim: true)

    random_chars = Enum.reduce((0..16), [], fn (_i, acc) ->
      [Enum.random(charset) | acc]
    end) |> Enum.join("")

    group_a = String.slice(random_chars, 1..4)
    group_b = String.slice(random_chars, 5..8)
    group_c = String.slice(random_chars, 9..12)
    group_d = String.slice(random_chars, 13..16)

    "#{group_a}-#{group_b}-#{group_c}-#{group_d}"
  end

  def generate() do
    [
      fragment(4),
      '-',
      fragment(4),
      '-',
      fragment(4),
      '-',
      fragment(4),
    ]
    |> to_string()
  end
end

…and this benchmark in iex:

Benchee.run %{"original_generate" => fn -> RandomCode.original_generate() end, "generate" => fn -> RandomCode.generate() end}
Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-4870HQ CPU @ 2.50GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.8.2
Erlang 22.0.2

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 generate...
Benchmarking original_generate...

Name                        ips        average  deviation         median         99th %
generate                 9.06 K      110.32 μs     ±9.68%      106.98 μs      154.98 μs
original_generate        8.04 K      124.36 μs     ±7.28%      121.98 μs      165.98 μs

Comparison:
generate                 9.06 K
original_generate        8.04 K - 1.13x slower +14.04 μs

It is only a slight improvement.

That being said, I’d always recommend against rolling your own random codes generator. Better use ex_ulid.

1 Like

Thanks, but looking at its readme file, it doesn’t seem to let you filter what characters get used and it doesn’t let you insert - at arbitrary points so you would end up having to likely call it 4 times (like I am doing in the 2nd version), in which case I’m really using erlang’s libs to generate the codes, not my own code.

Really cool library tho. Not sure if it’ll end up being used for this use case, but it looks useful for potentially other things.

V3:

Name           ips        average  deviation         median         99th %
v3        304.35 K        3.29 μs   ±826.00%           3 μs           6 μs
v2        171.89 K        5.82 μs   ±513.60%           5 μs          19 μs
v1          9.77 K      102.40 μs    ±21.58%          97 μs         196 μs

Comparison: 
v3        304.35 K
v2        171.89 K - 1.77x slower +2.53 μs
v1          9.77 K - 31.16x slower +99.11 μs
defmodule V3 do
  chars = 'CDEFGHJKLMNPQRTUVWXYZ23679'

  @chars List.to_tuple(chars)

  def generate() do
    0
    |> generate()
    |> IO.iodata_to_binary()
  end

  def generate(n) when n in [4, 9, 14] do
    [?- | generate(n + 1)]
  end

  def generate(n) when n >= 19 do
    []
  end

  def generate(n) do
    [elem(@chars, :rand.uniform(26) - 1) | generate(n + 1)]
  end
end
15 Likes

Wow that’s really fast. I know my old benchmarking way was potentially bad but for comparison’s sake, your v3 finishes in 25ms. So 730ms down to 70ms down to 25ms.

There’s a lot of foreign things happening in your code, and many things I haven’t seen yet, but would you mind filling in the gaps and / or correcting my initial reading of it?

@chars ends up being a tuple of character codes for each individual character.

When you initially call generate(), it calls generate(0) and that in turn triggers the last function pattern which kicks off a recursive cycle until the accumulator eventually goes beyond 19 characters (the exit case).

But I’m not sure how it knows to exit then. How does returning an empty list there halt everything?

Also what’s up with [?- | generate(n + 1)]? We’re dealing with a list here and I think this syntax means to put a - at the head of the list at every X char which effectively means to prepend the - to the current unfinished code (unfinished = not 19 chars yet), but what does the question mark do here?

Also in the last pattern, can you completely unwind that? I’m not sure what purpose :rand.uniform(26) serves exactly. I have a feeling this somehow generates a random character code but I have no idea how it all comes together. :smiley:

Thanks a lot by the way. Huge improvements (business results are a success and it’s super efficient and while I don’t fully understand it yet, it doesn’t seem out of this world insanely complicated).

Yeah so let’s break this down. @chars is {67, 68, 69, 70, 71, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 89, 90, 50, 51, 54, 55, 57}

This is a tuple, where each item in the tuple is the ascii code corresponding to one of your allowed characters. Why a tuple? Tuples are the absolute fastest data structure for index based access if you don’t need to be modifying stuff. The elem function gets a value out of a tuple by index.

So, the overall game plan is to “get random values out of the tuple”. That’s where :rand.uniform(26) - 1 comes in. It generates a random index, which lets us get a random ascii character out of the tuple.

Let’s play with this in iex

iex(7)> chars = List.to_tuple('CDEFGHJKLMNPQRTUVWXYZ23679')
{67, 68, 69, 70, 71, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 89,
 90, 50, 51, 54, 55, 57}
iex(8)> elem(chars, :rand.uniform(26) - 1) 
55
iex(9)> elem(chars, :rand.uniform(26) - 1)
88
iex(10)> elem(chars, :rand.uniform(26) - 1)
57

The next thing we need to do is generate a bunch of these in a list. Let’s ignore the dashes for a moment.
What I’ve got going on is good old fashioned body recursion. If this doesn’t feel familiar too you it’s definitely worth revisiting some core Elixir material, because as useful as Enum is (I use it all the time) the fundamentals of list building and recursion are critical.

If we ignore the dash clause and focus just on:

  def generate(n) when n >= 19 do
    []
  end

  def generate(n) do
    [elem(@chars, :rand.uniform(26) - 1) | generate(n + 1)]
  end

you should recognize that elem(@chars, :rand.uniform(26) - 1) is just generating a random character for us. The function is basically just

  def generate(n) do
    [ get_random() | generate(n + 1)]
  end

Notice how generate calls itself inside the list. You can think about this at runtime expanding like so:

[ random() | generate(1)]
[ random() | random() | generate(2)]
[ random() | random() | random() | generate(3)]
[ random() | random() | random() | ... | generate(19)]
[ random() | random() | random() | ... | []]

and so forth. when we get to generate(19) we return an empty list. This doesn’t do anything magical or special, it literally is just an empty list. The point though is that the empty list is now at the tail place of the list that’s been expanding in memory from all of our recursive function calls. This now means that the whole value is built and can be returned.

This part:

  def generate(n) when n in [4, 9, 14] do
    [?- | generate(n + 1)]
  end

just special cases the 4th, 9th, and 14th positions to be a dash ascii character instead of a random number. Question mark in front of a character returns that character’s ascii code:

iex(12)> ?- 
45
22 Likes

Epic explanation. Everything is crystal clear now, except one thing. I’m still not sure how it knows to stop at 19 characters by having an empty list as the tail.

If this thing keeps calling itself recursively, what makes [ random() | random() | random() | ... | []] inform Elixir that we’re done and ready to return?

Also before you replied, initially the 26 threw me off because there’s 26 letters in the alphabet, I didn’t realize it’s also the length of the custom character set.

1 Like

Imagine if this was just simple addition:

def outer() do
  1 + some_function()
end

If I call outer(), it won’t return until some_function() runs and returns. The + won’t actually happen until then either, because it can’t actually add a value until some_function is called and returns a value.

This creates what is known as a “call stack” and we use it constantly. Every time we call a function inside another function, we ask the VM to go execute that function and return its value to us before we continue in our function.

Now suppose we have:

def sum(0) do
  0
end
def sum(n) do
  n + sum(n - 1) 
end

If I call sum(3), the body of the function will be:

3 + sum(2)

Well, that can’t actually be done until sum(2) is called and returns. Of course, that itself has an inside function that must be called and returned:

3 + (2 + sum(1))

And so on:

3 + (2 + (1 + sum(0)))

Our initial sum(3) hasn’t returned yet, none of the function calls have returned yet, because to return a function you have to finish executing everything inside it.

When we get to sum(0) though, the function clause that matches doesn’t have any functions inside it that need to be executed. It’s just 0. So now, sum(1) can finish executing because it now has 1 + 0. Then sum(2) can finish because it has 2 + 1. Finally `sum(3) can finish and we get 6.

3 + ( 2 + ( 1 + 0) )
3 + (2 + 1)
3 + 3
6

What we have going on with [random | generate(n+ 1) is exactly the same idea, but instead of addition, we’re constructing a list. IMPORTANT: It isn’t about the empty list. For example we could have:

  def generate(n) when n >= 19 do
    'yo-dawg'
  end

which when called would create "TDTU-72V2-YL6T-CLDNyo-dawg". The point is that when that clause is matched, there are no more inner functions to call, and we can stop adding to the call stack. Instead we can start returning values to all of the accumulated functions that haven’t been able to return yet.

11 Likes

Oh yeah. This is what happens when you don’t take a CS course or work with functional languages much. You very rarely deal with recursion. Your explanation rattled an old memory of something I read way back about how tail call optimization is somehow when you can avoid making a christmas tree style call stack?

Really appreciate you going the extra mile. That was a very clear explanation of recursion. Just curious, what made you use [] rather than "" in the base case?

iex(15)> [1,2,3] == [1 | [2 | [3 | []]]]
true

The goal is to make a list, which means you need to end with []. Technically ending with "" works cause of io_list stuff but if you wanted to inspect stuff part way through it’d be weird.

iex(16)> [1 | [2 | [3 | ""]]]           
[1, 2, 3 | ""]

If you’re trying to build a list, tail call optimization basically has you manage the stack yourself instead of building a call stack. For a list of length 19, the difference isn’t really gonna matter, so I figured the body recursive style was easiest.

I really can’t overstate the value of going through some of the intro Elixir material that covers recursion if it doesn’t feel intuitive for you. It’ll really help you level up your functional programming power.

4 Likes

I absolutely love the teaching session @benwilson512 is giving. :heart: And the amazing code he put out.

(TL;DR of everything below: use proven unique ID generators!)

I’ll digress a bit here. I’d still prefer to use an ULID and transcode that to your exact desired output since ULID gives you even better guarantees than UUID (which in some of its older versions actually can produce duplicates). So I went ahead and made a module that has Nick’s original generator, Ben’s and mine – which transcodes an ULID to exactly the code format Nick wants (and uses his charset, and respects the exact expected output length). Apologies for 67 lines of pasted code but I got hooked on this problem! :smiley:

defmodule RandomCode do
  @base36_charset '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  @crockford_base32_charset '0123456789ABCDEFGHJKMNPQRSTVWXYZ'
  @output_charset 'CDEFGHJKLMNPQRTUVWXYZ23679'
  @output_base length(@output_charset)

  @base36_tuple List.to_tuple(@base36_charset)
  @output_tuple List.to_tuple(@output_charset)

  @ulid_to_base32_dictionary (@crockford_base32_charset |> Enum.with_index() |> Enum.map(fn {char, index} -> {char, elem(@base36_tuple, index)} end) |> Map.new())

  @base32_to_output_dictionary 0..@output_base-1 |> Enum.map(fn i -> {elem(@base36_tuple, i), elem(@output_tuple, i)} end) |> Map.new()

  def transcode_ulid(ulid) do
    ulid
    |> to_charlist()
    |> Enum.map(fn char -> @ulid_to_base32_dictionary[char] end)
    |> to_string()
    |> Integer.parse(32)
    |> elem(0)
    |> Integer.to_charlist(@output_base)
    |> Enum.map(fn char -> @base32_to_output_dictionary[char] end)
    |> Enum.take_random(4)
    |> Enum.join("-")
  end

  def dimi_generate() do
    ExULID.ULID.generate()
    |> transcode_ulid()
  end

  def nick_generate() do
    charset = "CDEFGHJKLMNPQRTUVWXYZ23679" |> String.split("", trim: true)

    random_chars = Enum.reduce((0..16), [], fn (_i, acc) ->
      [Enum.random(charset) | acc]
    end) |> Enum.join("")

    group_a = String.slice(random_chars, 1..4)
    group_b = String.slice(random_chars, 5..8)
    group_c = String.slice(random_chars, 9..12)
    group_d = String.slice(random_chars, 13..16)

    "#{group_a}-#{group_b}-#{group_c}-#{group_d}"
  end

  def ben_generate() do
    0
    |> ben_generate()
    |> IO.iodata_to_binary()
  end

  def ben_generate(n) when n in [4, 9, 14] do
    [?- | ben_generate(n + 1)]
  end

  def ben_generate(n) when n >= 19 do
    []
  end

  def ben_generate(n) do
    [elem(@output_tuple, :rand.uniform(26) - 1) | ben_generate(n + 1)]
  end
end

It’s a long chain of piped transforms but still performs quite nicely:

iex> Benchee.run %{"nick_generate" => fn -> RandomCode.nick_generate() end, "dimi_generate" => fn -> RandomCode.dimi_generate() end, "ben_generate" => fn -> RandomCode.ben_generate() end}

...

Name                    ips        average  deviation         median         99th %
ben_generate       226.98 K        4.41 μs   ±500.75%        3.90 μs        8.90 μs
dimi_generate       32.90 K       30.39 μs    ±30.35%       27.90 μs       71.90 μs
nick_generate        7.70 K      129.95 μs    ±19.25%      121.90 μs      262.80 μs

Comparison:
ben_generate       226.98 K
dimi_generate       32.90 K - 6.90x slower +25.99 μs
nick_generate        7.70 K - 29.50x slower +125.54 μs

~32900 codes/sec on a midrange i7 CPU ain’t bad at all. Even if your server is 4x slower than that, you still have a bandwidth of several thousand very safe and never duplicating codes per second, and you will likely never reach such a demand in your app.


Caveat: I am actually taking 4 out of 7 string chunks that my algorithm produces and just discard the other 3 (see the Enum.take_random(4) call in the big code chain). This definitely reduces randomness and increases likelihood of collisions. They can probably be squished together for a bit better entropy but I gave up before getting that far. :slight_smile: Still, that’s a weakness in my approach.

1 Like

And also do Exercism’s ListOps exercise. I really felt my understanding grow times bigger after I successfully finished it with quite good benchmarking results and without cheating. Using the very fast list operations will practically always bottleneck your program on I/O which is ultimately the goal – namely that our programs’ CPU and memory usage to not stand in the way.

1 Like

How about generating more keywords at one go.

This should be significantly faster than doing them one at a time.

  defmodule V4 do
    chars = 'CDEFGHJKLMNPQRTUVWXYZ23679CDEFGHJKL'
    @chars List.to_tuple(chars)

    def encode(data, charset) do
      # Maps the data to the charset
      encode(data, charset, [])
    end

    def encode(<<>>, _, acc) do
      acc
    end

    def encode(
          <<a::size(5), b::size(5), c::size(5), d::size(5), e::size(5), f::size(5), g::size(5),
            h::size(5), a2::size(5), b2::size(5), c2::size(5), d2::size(5), e2::size(5),
            f2::size(5), g2::size(5), h2::size(5), rest::binary>>,
          charset,
          acc
        ) do
      encode(rest, charset, [
        IO.iodata_to_binary([
          elem(@chars, a),
          elem(@chars, b),
          elem(@chars, c),
          elem(@chars, d),
          '-',
          elem(@chars, e),
          elem(@chars, f),
          elem(@chars, g),
          elem(@chars, h),
          '-',
          elem(@chars, a2),
          elem(@chars, b2),
          elem(@chars, c2),
          elem(@chars, d2),
          '-',
          elem(@chars, e2),
          elem(@chars, f2),
          elem(@chars, g2),
          elem(@chars, h2)
        ])
        | acc
      ])
    end

    def generate(n) do
      # We need n codes
      # Each code is 16 bytes from charset
      # Each byte needs 5  bits of random data
      # So the number of bytes needed is
      # n * 16 / 8 * 5 = n * 2 * 5 = n * 10
      :crypto.strong_rand_bytes(n * 10)
      |> encode(@chars)
    end
  end

The code is a bit biased towards a few characters. It fetches all random data needed for all words at a go an then encodes them into the character set. 5 bits are needed for 26 characters so I doubled up a few characters in the look-up map. This means these characters are more likely to occur. If you could introduce 6 other characters to make up 32 then it would not be a problem :smiley:

I ran it with @benwilson512 's codes repository bench.

Doing 5000 codes at a time:

  Name           ips        average  deviation         median         99th %
v4          377.56        2.65 ms     ±8.55%        2.58 ms        3.21 ms
v3           63.23       15.82 ms     ±2.67%       15.76 ms       16.96 ms
v2           40.51       24.69 ms     ±2.40%       24.59 ms       26.40 ms
v1            1.87      534.44 ms     ±1.25%      532.05 ms      555.02 ms

Comparison:
v4          377.56
v3           63.23 - 5.97x slower +13.17 ms
v2           40.51 - 9.32x slower +22.04 ms
v1            1.87 - 201.78x slower +531.79 ms

Doing 1 code at a time and it is not as much faster bit still OK.

Name           ips        average  deviation         median         99th %
v4        860.49 K        1.16 μs  ±3035.06%        0.93 μs        2.16 μs
v3        296.46 K        3.37 μs   ±525.89%        2.88 μs       16.26 μs
v2        188.72 K        5.30 μs   ±498.17%        4.34 μs       18.78 μs
v1         10.08 K       99.19 μs    ±20.93%       93.53 μs      202.76 μs

Comparison:
v4        860.49 K
v3        296.46 K - 2.90x slower +2.21 μs
v2        188.72 K - 4.56x slower +4.14 μs
v1         10.08 K - 85.35x slower +98.02 μs

Is it correct? Who knows :wink:

3 Likes

A musical explanation to what ben already explained.

3 Likes

Nice approach!

Yeah this bit is pretty important. I was figuring the various missing numbers / letters were to avoid numbers / letters that can be confusing. If that’s the case and we can’t add characters, I wonder if there’s a way to add a random selection to the tuple each time without hurting performance too much.

You could use functions instead of a tuple they can be bit faster and doing it in one go like in V6 is arguable more readable.

  defmodule V5 do

    def generate() do
      0
      |> generate()
      |> IO.iodata_to_binary()
    end

    for {match, n} <- [{4, 5}, {9, 10}, {14, 15}] do
      def generate(unquote(match)), do: [?- | generate(unquote(n))]
    end
    def generate(n) when n >= 19, do: []
    def generate(n), do: [char(:rand.uniform(26) - 1) | generate(n + 1)]

    for {n, char} <- Enum.zip(0..26, 'CDEFGHJKLMNPQRTUVWXYZ23679')  do
      def char(unquote(n)), do: unquote(char)
    end
  end

  defmodule V6 do

    def generate() do
      IO.iodata_to_binary([
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
       ?-,
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
       ?-,
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
       ?-,
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
       char(:rand.uniform(26)),
      ])
    end

    for {n, char} <- Enum.zip(1..26, 'CDEFGHJKLMNPQRTUVWXYZ23679')  do
      def char(unquote(n)), do: unquote(char)
    end
  end
Name           ips        average  deviation         median         99th %
v6        267.90 K        3.73 μs   ±713.04%           3 μs           8 μs
v5        235.94 K        4.24 μs   ±570.11%           4 μs          12 μs
v3        178.23 K        5.61 μs  ±1111.91%           4 μs          18 μs
v2        132.65 K        7.54 μs   ±396.05%           6 μs          31 μs
v1          6.85 K      145.94 μs    ±23.12%         137 μs         279 μs

Comparison: 
v6        267.90 K
v5        235.94 K - 1.14x slower +0.51 μs
v3        178.23 K - 1.50x slower +1.88 μs
v2        132.65 K - 2.02x slower +3.81 μs
v1          6.85 K - 39.10x slower +142.21 μs
3 Likes

Hey, thanks for including your solutions.

In V6, would you mind explaining this:

    for {n, char} <- Enum.zip(1..26, 'CDEFGHJKLMNPQRTUVWXYZ23679')  do
      def char(unquote(n)), do: unquote(char)
    end

From my newbie POV, it looks like you have a generator (or is this a comprehension?) just floating in the middle of the module outside of any function. I think I’ve seen unquote before when related to macros but I never read up on macros yet.

How does all of this come together to get the job done?

Those are “unquote fragments” and can say every code, which is not within the do block of def is executed at compile time. In this case this generates functions at compile time, which convert a number to a character. This might be a bit quicker than using data as lookup table (e.g. a map).

2 Likes