I recently read a book for computer beginners listing a code snip about the rock paper scissors game. The program uses primitive integers 0, 1, and 2 to represent rock, scissors, and paper.
The most straightforward algorithm is to enumerate all the 3x3=9 situations.
a = rand.randint(0, 2)
b = rand.randint(0, 2)
if a == 0 and b == 0:
print("draw game")
elif a ==0 and b ==1:
print("winner is A")
...
Then, the author hints that if we use little mathematical skills to find the relationship between the three numbers and three possible outcomes, the program can be simplified and run faster.
if a == b:
print("draw game")
elif a == (b + 1) % 3:
print("winner is B")
else:
print("winner is A")
Assuming that the probabilities of entering all if-else branches in the two algorithms are not much different (excluding the situation where a player always gestuers stone), then I think there are no significant performance differences between the two algorithms or even the performance of the latter may be slightly worse, because the remainder(%) operation seems to consume more CPU cycles than ==.
However, I did a performance test with the following code($ time python3 game.py), which showed that the latter algorithm runs faster. I am curious why this is happening.
I was considering that either rand.randint(0, 2) or print() is much slower than the comparison operation, so I pre-generated some test cases, put them into the list, and used pass instead of print().
def brute_force(a, b):
if a == 0 and b == 0:
pass
...
def mod(a, b):
if a == b:
pass
elif a == (b + 1) % 3:
pass
else:
pass
if __name__ == '__main__':
testcases = [...]
num_repetions = 1_000_000
for i in range(num_repetions):
for a, b in testcases:
brute_force(a, b)
# mod(a, b)
time with brute_force samples(in second): [17.014, 18.069, 16.956, 17.931, 17.919, 17.211, 17.983, 16.984, 17.581, 17.048]
time with mod samples: [15.921,14.817,15.723,15.715,15.715,16.917,14.957,15.196,16.115,14.763]
There are two factors involved in the difference, the number of tests and the intrinsic operation performed during the test.
Let's compute the number of tests for each pair of a/b, as well as the timing for 10M repetitions of each case.
There is only one case in which the number of tests is greater for "mod" than "brute", in all other cases there is a greater or equal number of tests. Even when only 1 test is performed, then the mod approach is ~9% faster than the brute force one. When repeating many times these operations, we can expect on average a ~20% faster code for the mod approach.
# brute_tests, mod_tests: number of if/elif evaluated
# brute, mod: average timing over 10M repetitions
# ratio: ((mod/brute)-1)*100
brute_tests mod_tests brute mod ratio
a b
0 0 1 1 0.716118 0.650637 -9%
1 2 3 0.851238 0.931243 +9% # only mod>brute timing
2 3 2 0.979143 0.879900 -10%
1 0 4 2 0.957501 0.861337 -10%
1 5 1 1.022147 0.619716 -39%
2 6 3 1.121240 0.847757 -24%
2 0 7 3 1.083824 0.869857 -20%
1 8 2 1.220271 0.854881 -30%
2 9 1 1.384442 0.738560 -47%