Why is my random number lookup slow using lists?

Lists do not support random access and access is linear, so to get nth element you need n steps. In other words the Enum.at/2 for list will be implemented as:

def at([], _), do: nil
def at([val | rest], 0), do: val
def at([_ | rest], n) when n > 0, do: at(rest, n - 1)

Thanks for the help, and learned very quickly that in func lang, recursive is your friend - meaning you can’t do list[index] … that not gone work

I tried your solution above but seems slower (And tried as in I prbl done something horribly wrong using your code, but have to start somewhere :)) - used Benchee for my benchmark results

defmodule Monkeyatwork do
  def at([], _), do: nil
  def at([val | rest], 0), do: val
  def at([_ | rest], n) when n > 0, do: at(rest, n - 1)     

  def test1() do
    chars = 'ABCDEFGHIJKLMNOPQRSTUVW'
    data = List.to_tuple(chars)
    
    for x <- 0..1000000 do 
        elem(data, :rand.uniform(22))    
    end        
  end

  def test2() do
    chars = 'ABCDEFGHIJKLMNOPQRSTUVW'
    
    for x <- 0..1000000 do 
      at(chars, :rand.uniform(22))    
    end        
  end  
end

Benchee.run(
  %{
    "test1" => fn -> Monkeyatwork.test1() end,
    "test2" => fn -> Monkeyatwork.test2() end
  }
)

My results

Benchmarking test1...
Benchmarking test2...

Name            ips        average  deviation         median         99th %
test1          2.39      419.25 ms     ┬▒4.15%      414.50 ms      453.00 ms
test2          1.89      528.10 ms     ┬▒3.04%      523.50 ms      562.00 ms

Comparison:
test1          2.39
test2          1.89 - 1.26x slower +108.85 ms

He wasn’t providing a faster solution, he was showing how the code underlying your existing solution worked, demonstrating that it was O(N).

Probably the fastest thing is to just compute a random number between 0 and 22 and add the correct ASCII offset.

random_char = [:random.uniform(22) + 65]

Except I would write it as:

random_char = [:rand.uniform(?Z - ?A) + ?A)]

For less “magic numbers”. Also :rand is preferred solution over :random.

However I am not sure if Enum.random(?A..?Z) isn’t optimised for such case (and if not it probably would be nice addition).

EDIT:

Enum.random(?A..?Z) will run in constant time and space, so it would be the best and the fastest solution.

cc @oegma2

Thanks, @hauleth, and @benwilson512 for the input - going to try the Enum.random(?A..?Z), [:rand.uniform(?Z - ?A) + ?A)] and [:rand.uniform(?Z - ?A) + ?A)]

Agree with @hauleth regarding the :rand is preferred solution over :random - valid point, but my use-case, don;t need true crypto style random numbers. But good to keep it in mind

Thanks so much for the help and quick response - really awesome community!

For cryptographically secure rands you need to use :crypto.random_bytes/1, :rand isn’t crypto safe either.

Yes, this is explicitly mentioned in the module rand docs:

The builtin random number generator algorithms are not cryptographically strong. If a cryptographically strong random number generator is needed, use something like crypto:rand_seed/0.

So I’ve done some testing and found 2 options that pretty fast for our Monkey app hitting random keys. Thanks to @hauleth and @benwilson512 for providing me with test1 option below

@hauleth / @rvirding : Thanks for the info on :rand regarding crypto. For my example, since the monkies just need a random number, it don’t need super secure random numbers, just random. But solid info and will keep that in mind for future projects that require secure random numbers.

Back to the monkies app - The strange part is that using tuple’s in this case with the Kernel elem(tuple, index) seems to be a bit faster than Enum.random(?A..?Z)

I’ve asked the Monkies to try and type the following sequence in order “FOXYL” at random, and if they type FOD they start over - must be in perfect sequence, else they start from scratch. It’s actually scary to think a random monkey got that word in under 4 seconds in test1 and under 2 seconds in test2

Below is the results from Benchee
test1 using Enum.random(?A..?Z)
test2 using

  def rand_key() do
    data = {65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90}
    elem(data, :rand.uniform(26) - 1)    
  end

Name            ips        average  deviation         median         99th %
test2          0.62         1.62 s    ┬▒82.72%         1.44 s         3.87 s
test1          0.22         4.49 s    ┬▒87.21%         3.42 s         8.83 s

Comparison:
test2          0.62
test1          0.22 - 2.76x slower +2.86 s

Ok, I have tested on my own, and to my surprise you are right.

range = ?A..?Z
tuple = range |> Enum.to_list() |> List.to_tuple()

defmodule Bench.Random do
  def pick(from..to), do: from + :rand.uniform(to - from)
end

Benchee.run(
  %{
    "tuple" => fn -> for _ <- 0..1000, do: elem(tuple, :rand.uniform(tuple_size(tuple)) - 1) end,
    "range" => fn -> for _ <- 0..1000, do: Enum.random(range) end,
    "picker" => fn -> for _ <- 0..1000, do: Bench.Random.pick(range) end,
    "add random" => fn -> for _ <- 0..1000, do: ?A + :rand.uniform(tuple_size(tuple)) end
  }
)

Results with:

Operating System: macOS"
CPU Information: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
Number of Available Cores: 12
Available memory: 32 GB
Elixir 1.9.4
Erlang 22.1.7

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


Benchmarking add random...
Benchmarking picker...
Benchmarking range...
Benchmarking tuple...

Name                 ips        average  deviation         median         99th %
add random        5.26 K      190.09 μs     ±9.44%         184 μs         276 μs
tuple             5.21 K      191.99 μs     ±7.48%         189 μs         272 μs
picker            4.97 K      201.27 μs     ±8.91%         196 μs         288 μs
range             3.16 K      316.42 μs     ±9.32%         305 μs         471 μs

Comparison:
add random        5.26 K
tuple             5.21 K - 1.01x slower
picker            4.97 K - 1.06x slower
range             3.16 K - 1.66x slower

Which I find a little bit weird, as I would assume that range would be faster.