Monty Hall in BBC BASIC and Python

Question

How would I be able to improve the speed of this Monty Hall program? Interestingly, the same code written using BBC BASIC for Windows completes the task in half the time of the Python code.

Python:

import random

t = 10000001
j = 0
k = 0

for a in range(1, t):
    p = int(random.random() * 3) + 1
    g = int(random.random() * 3) + 1

    if p == g:
        r = int(random.random() * 2) + 1
        if p == 1:
            r += 1
        if p == 2 and r == 2:
            r = 3
    else:
        r = p ^ g
    s = g
    f = g ^ r
    if s == p:
        j = j + 1
    if f == p:
        k = k + 1

print(f"After a total of {t - 1} trials,")
print(f"The 'sticker' won {j} times ({int(j/t*100)}%)")
print(f"The 'swapper' won {k} times ({int(k/t*100)}%)")

BBC BASIC for Windows:

T% = 10000000

for A% = 1 to T%
  P% = rnd(3)
  G% = rnd(3)
  if P% = G% then

    R% = rnd(2)
    if P% = 1 then R% += 1
    if P% = 2 and R% = 2 then R% = 3
  else
    R% = P% eor G%
  endif
  S% = G%
  F% = G% eor R%
  if S% = P% then J% = J% + 1
  if F% = P% then K% = K% + 1
next

print "After a total of ";T%;" trials,"
print "The 'sticker' won ";J%;" times (";int(J%/T%*100);"%)"
print "The 'swapper' won ";K%;" times (";int(K%/T%*100);"%)"

Answer 1

So this is not the typical code review, as the code in question is pretty basic in terms of what it does. It is a given algorithm, and you need to do the given operations. The one possible varying factor is the random.random() lines. Can this affects times?

Let us test the random generation of some numbers using various random generators:

import random
import numpy
import timeit

t = 100001
def org_random_random(runs=t):
  for a in range(t):
    int(random.random() * 3) + 1

def org_random_randint(runs=t):
  for a in range(t):
    random.randint(1, 3)

def numpy_random_randint(runs=t):
  for a in range(t):
    numpy.random.randint(1, 3)

def numpy_random_randint_x(runs=t):
  numpy.random.randint(1, 3, runs)

orr = timeit.timeit(org_random_random, number=5)
ori = timeit.timeit(org_random_randint, number=5)
nrr = timeit.timeit(numpy_random_randint, number=5)
nrx = timeit.timeit(numpy_random_randint_x, number=5)

Sorry for terrible naming, it's just something I threw together, and when I ran it using https://repl.it/languages/Python3, it gave me the following output:

org_random_random     : 0.18020408600023075
org_random_randint    : 0.8966416030016262
numpy_random_randint  : 0.9019350050002686
numpy_random_randint_x: 0.004406830999869271

All three variants has been 'normalised' to produce a number between 1 and 3, and the last variant generates all of the numbers in one go. And the last one is way faster than the other.

In other words, I would suggest to pre-build the random numbers, and make a custom generator feeding you from this pre-built array of random numbers. This would potentially drastically reduce the running time of your algorithm.

Using a prebuilt random number array

Here is a simple rebuild using a pre-built array of random numbers from numpy:

runs = 10000001
random_numbers = numpy.random.randint(1, 3, runs + 6)

j = 0
k = 0

for i in range(1, runs):
    p = random_numbers[i]
    g = random_numbers[i+1]

    if p == g:
        r = random_numbers[i+2] % 2 + 1
        if p == 1:
            r += 1
        if p == 2 and r == 2:
            r = 3
    else:
        r = p ^ g
    s = g
    f = g ^ r
    if s == p:
        j = j + 1
    if f == p:
        k = k + 1

print(f"After a total of {t - 1} trials,")
print(f"The 'sticker' won {j} times ({int(j/t*100)}%)")
print(f"The 'swapper' won {k} times ({int(k/t*100)}%)")

When timed (without the print statements), this ran about 33% faster than the original. It does kind of reuse the random numbers slightly, but it shouldn't affect the overall randomness too much, I think.

Other possible factors

Just for the fun of it, I also tried exchanging the range() with a while a < runs loop, but that only had a minor effect for the larger number of runs. NB! If you was using Python 2.x, there would most likely be a massive effect out of changing range() into xrange().

The if s == p could be eliminated, and the j += 1 could be moved into the p == g block. This also, has little to no effect in my tests.

Lastly, using various python implementation will also effect timings. Using PyPy, IPython, C-Python(?), or other variations could change the time usage. I've used https://repl.it/languages/Python3, which reports the following on sys.version():

3.6.1 (default, Apr 26 2017, 20:23:36) 
[GCC 4.9.2]

I also tried with an actual generator with both the large prebuilt list of random numbers, and a loopable generator with 1013 random numbers. Those had similar run times to the original code.

So, with the exception of making a python wrapper and implement the algorithm in another language or re-build the algorithm, I would be surprised to see a faster implementation. But I'll happily be proven wrong!