Performance of Random number generators of pyroot and random

Question

I was looking to optimize a simple given code that generates a random number ([0,1,2]) that is not in a given list. The random number generator is TRandom3 from ROOT.

def getNumber(noList, randomgen):
    #Fügen Sie hier Ihren Code ein!: 
    i = randomgen.Integer(3)
    while i in noList:
        i = randomgen.Integer(3)
    return i

It is very basic and just generates new numbers until an allowed one is reached.

My own optimized code looked like this:

def bessereAuswahl(noList):
    return random.choice([elem for elem in [0,1,2] if elem not in noList])

I just remove all not allowed numbers from my list [0,1,2] and use random.choice to pick one element.

Running on windows 10 I had a performance increase, running the same code on linux I had a performance decrease.

Why is that the case?

Is there a hidden performance penalty for random on linux or is it a performance boost in pyroot?

Answer 1

So this is an implementation and complexity question:

the random.choice is implemented as:

The complexity of random.choice(list) is O(log n) where n is the number of elements in the list.

More on that second answer here

Whereas a random integer generation with Mersenne Twister agorithm is O(1), source code here

So the first part of the answer is, that asymptotically choice is slower. However, the question is, if you have to generate a certain amount of numbers.

So if you have to create n numbers and the set of allowed numbers in the total set is relatively small, the amount of retrials can grow more significantly than the individual runtime of draws