1

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?

tobias spanke
  • 11
  • 2
  • I find your setup a little weird, so you have a number room I that is split in I1 allowed numbers and I2 forbidden numbers and you draw numbers from I until you draw one from I2? Or what is the goal? – FloLie Nov 29 '20 at 18:07
  • yea, that is the idea. I draw from my numbers [0,1,2] until I draw one that is not in my second list. As this has the problem of a theoretical infinite runtime I wrote the second bit of code that I though would be faster but is for some reason only on Windows not on Linux. And i want to know why it is only faster on Windows. – tobias spanke Nov 29 '20 at 18:16
  • Does my answer answer your question? – FloLie Nov 29 '20 at 18:31

1 Answers1

0

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

FloLie
  • 1,820
  • 1
  • 7
  • 19
  • Thanks, but do you know why the runtime is different between Windows and Linux? – tobias spanke Nov 29 '20 at 18:34
  • how large was the sample you used to test runtime? – FloLie Nov 29 '20 at 18:35
  • I tested 100000 times ```getNumber([], generator) getNumber([1], generator) getNumber([1,2], generator) getNumber([numberOne], generator) getNumber([numberOne], [numberTwo], generator) ``` so I had a large enough sample size. Runtime on my Windows machine is around 0.5s for ```bessereAuswahl()``` and 0.7s for ```getNumber()```. On linux it was 2.9s for ```bessereAuswahl()``` and 2.2s for ```getNumber()```. – tobias spanke Nov 29 '20 at 18:50
  • Both windows and Linux deployed on bare metal or one as a vm within the other? – FloLie Nov 29 '20 at 19:16
  • well, your test environment seems absolutly fine, so unfortunatly I don't have another idea.. sorry mate – FloLie Nov 30 '20 at 10:30