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

The shuffle implementation is straightforward. It creates assigns a random number to each list element and then sorts them and returns the result: elixir/lib/elixir/lib/enum.ex at main · elixir-lang/elixir · GitHub Enum.random depends on Enum.take_random which seems to creates a map with all the ele…

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?

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 e…

Elixir Programming Language Forum

Complexity of Enum functions

Questions & Help Questions

NobbZ December 1, 2017, 6:14am 3

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