Complexity of Enum functions

Questions / Help
1

I wanted to know what is the time complexity of Enum.random and Enum.shuffle.

More specifically i wanted to figure out if I want to select 50 random values from a possible set of 10,000 values, will it be faster to shuffle the list and then take first 50 elements or select random elements 20 times

2

The shuffle implementation is straightforward. It creates assigns a random number to each list element and then sorts them and returns the result: https://github.com/elixir-lang/elixir/blob/master/lib/elixir/lib/enum.ex#L2080 Enum.random depends on Enum.take_random which seems to creates a map with all the elements and takes a few of them.

To answer your question, you should run a few benchmarks using benchee to decide which one to use. If you want multiple random elements use Enum.take_random(enumerable, count) instead of running Enum.random multiple times.

3

Random on a range is O(1), all other enumerables are O(n).

4

So 20 times Enum.random() will still run in constant time but Enum.shuffle and then Enum.slice() will take O(n). Am I correct?

5

If and only if you use a Range as input for Enum.random/1 you will get get your result in constant time.

But you also have to remember that there are differences between both versions of code:

def pick20a(enum) do
  1..20
  |> Enum.map(fn (_) -> Enum.random(enum) end)
end

def pick20b(enum) do
  enum
  |> Enum.shuffle()
  |> Enum.take(20)
end

pick20a/1 might return some elements multipletimes, while pick20b/1 won’t, also pick20b will never return more elements than your input has:

iex(2)> M.pick20a(1..10)
[3, 4, 3, 10, 5, 10, 9, 1, 8, 9, 1, 10, 3, 7, 3, 8, 4, 5, 5, 7]
iex(3)> M.pick20b(1..10)
[7, 3, 5, 1, 6, 2, 9, 8, 4, 10]