1
\$\begingroup\$

I'm wondering whether there is a way to make this even more efficient or reduce the number of variables.

import random
numberOfStreaks = 0
results = []
head_streak = ['H'] * 6
tail_streak = ['T'] * 6
sample_size = 1000000
for i, experimentNumber in enumerate(range(sample_size)):
    # Code that creates a list of 100 'heads' or 'tails' values.
    results.append(random.choice(('H', 'T')))

    # Code that checks if there is a streak of 6 heads or tails in a row.
    try:
        temp = results[i-5:]
        if temp == head_streak or temp == tail_streak:
            numberOfStreaks += 1
    except:
        pass

print('Chance of streak: %s%%' % (numberOfStreaks / sample_size))
\$\endgroup\$
1
\$\begingroup\$
    # Code that creates a list of 100 'heads' or 'tails' values.
    results.append(random.choice(('H', 'T')))

This comment is severely misleading: the code does not create a list of 100 values, it create an infinitely growing list that extends up to sampleSize values by the time the program terminates.


Independently of the misleading comment, this is a bad idea, and can be avoided by limiting the size of the results list in some say (del results[:-6], or results = results[-6:], I'm not sure which is better). This would also obsolete the temp variable, because the results array would no longer contain extra flips.


    try:
        temp = results[i-5:]
        if temp == head_streak or temp == tail_streak:
            numberOfStreaks += 1
    except:
        pass

Bare except statements are a bad idea. Bare except:pass statements even more so. Among other problems, it means that if you press Ctrl-C while your code is executing that section, the code won't exit.

It's not clear what exception you are trying to catch (results[i-5:] doesn't throw an error if results is less than five items long; it just truncates the list), so I can't suggest a direct replacement, but I would recommend either catching a specific exception, or removing the try-catch entirely.


Python lists natively support negative indexing, so you can simplify results[i-5:] to results[-6:] and remove the i variable entirely. As suggested by the question asker in the comments, this makes the enumerate call unnecessary.


The i variable will then be unused. It's clearer to name variables you don't use as _, so it's easy to tell that they aren't used.


Full code:

import random
numberOfStreaks = 0
results = []
head_streak = ['H'] * 6
tail_streak = ['T'] * 6
sample_size = 1000000
for _ in range(sample_size):
    # Code that generates another 'heads' or 'tails' value
    results.append(random.choice(('H', 'T')))

    # Code that checks if there is a streak of 5 heads or tails in a row.
    results = results[-6:]
    if results == head_streak or results == tail_streak:
        numberOfStreaks += 1

print('Chance of streak: %s%%' % (numberOfStreaks / sample_size))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ in that case i wouldn't even need enumerate would i, for i in range(samplesize) works \$\endgroup\$ – DeltaHaxor Jun 17 at 22:24
3
\$\begingroup\$

Eliminating useless code

Enumerating a range is really pointless

In [6]: sample_size = 5

In [7]: for i, experimentNumber in enumerate(range(sample_size)):
   ...:     print(i, experimentNumber)
   ...:     
0 0
1 1
2 2
3 3
4 4

So we can easily replace one by the other. We do not even need to replace as experimentNumber is not used anywhere. Next we notice that i is also used only once where we can replace results[i-5:] by superior construct results[-6:]. We also eliminate the superfluous exception handling. So far this is already covered by @ppperys answer.

Efficiency

you create a complet list of length sample_size of random values in memory. This is not required and may be a problem on big sample sizes. As you always need the last 6 values only you could go for collections.deque which can maintain a maxlen.

from collections import deque
results = deque(maxlen=6)

For the evaluation made easy we do not use ('H', 'T') but numbers. We do not need to comare with a streak any more but do it arithmetically. Here is the only pitfall - we must check if the queue is filled completely to not accidentally accept a short sequence of zeros.

for _ in range(sample_size):
    results.append(random.choice((0, 1)))
    if len(results) == 6 and sum(results) in (0, 6):
        numberOfStreaks += 1

This not only saves memory but we also get rid of a temporary temp and the predifined head_streak and tail_streak. We notice the magic number 6 appearing multiple times - use a variable. We also make a testable function. We end up with

import random
from collections import deque

def streak_probability(streak_len, sample_size):
    results = deque(maxlen=streak_len)
    numberOfStreaks = 0
    for _ in range(sample_size):
        results.append(random.choice((0, 1)))
        if len(results) == streak_len and sum(results) in (0, streak_len):
            numberOfStreaks += 1
    return numberOfStreaks / sample_size


print('Chance of streak: %s%%' % (streak_probability(6, 1000000))

Algorithm

This simulation will give good results for big numbers of sample_size. However if the sample size was smaller than 6 it will always return 0. As you divide the final streak count by the sample size you indicate, that you would like to get the probability of a streak per "additional" coin toss. So we should fill the queue before starting to count. That way an average of a large number of runs with a small sample size would match a single run of a large sample size. If we prefill we do not have to check the fill state of the queue (yes I filled to the max while one less would be sufficient).

def prefilled_streak_probability(streak_len, sample_size):
    results = deque((random.choice((0, 1)) for _ in range(streak_len)), maxlen=streak_len)
    numberOfStreaks = 0
    for _ in range(sample_size):
        results.append(random.choice((0, 1)))
        if sum(results) in (0, streak_len):
            numberOfStreaks += 1
    return numberOfStreaks / sample_size

Now test the difference - we compare the original sample size of 1.000.000 to 100.000 repetitions of sample size 10

s=10
n=100000
print('no prefill')
print('Single big sample - Chance of streak: %s%%' % (streak_probability(6, s*n)))
probs = [streak_probability(6, s) for _ in range(n)]
print('Multiple small samples - Chance of streak: %s%%' % (sum(probs)/len(probs)))

print('with prefill')
print('Single big sample - Chance of streak: %s%%' % (prefilled_streak_probability(6, s*n)))
probs = [prefilled_streak_probability(6, s) for _ in range(n)]
print('Multiple small samples - Chance of streak: %s%%' % (sum(probs)/len(probs)))

we get

no prefill
Single big sample - Chance of streak: 0.031372%
Multiple small samples - Chance of streak: 0.01573599999999932%
with prefill
Single big sample - Chance of streak: 0.031093%
Multiple small samples - Chance of streak: 0.031131999999994574%
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You could use random.choices and drop the loop for shorter and more readable code. \$\endgroup\$ – agtoever Jun 19 at 21:53
  • \$\begingroup\$ @agtoever Right. But I was explicitely going for a smaller memory footprint. If going for speed I would change not only the random function but also the streak counting. \$\endgroup\$ – stefan Jun 22 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.