Имитируя подбрасывание монеты с использованием списка и случайности, код сначала работает, а затем зависает

Question

Проблемы с симуляцией броска монеты. Этот код должен подсчитывать количество бросков в среднем, необходимое для подбрасывания монеты и получения хвостов три раза подряд (поэтому успех = 3 't', 1 успех удовлетворяет первому эксперименту).

import random

experiments = [1, 10, 100, 1000, 10000, 100000]

for number in experiments:
    experiment = []
    success = 0
    while success < number:
        face = random.choice(['h','t'])
        experiment.append(face)
        success = ''.join(experiment).count('ttt')
    print(f'Experiments: {number}')
    print(f'Average flips: {len(experiment)/success}\n')

Вывод выглядит так:

[evaluate troubleshooting.py]
Experiments: 1
Average flips: 27.0

Experiments: 10
Average flips: 6.4

Experiments: 100
Average flips: 14.39

Experiments: 1000

Answer 1

Ну, я думаю, что главная проблема в том, что строка success = ''.join(experiment).count('ttt') заставит вашу программу искать весь список для каждого прохода по циклу while, что будет иметь O (n ^ 2) временную сложность (AKA, BAD). Действительно очень плохо, чем больше экспериментов ты проводишь).

Я создал (рудиментарную) программу, которая будет выполнять эту часть за линейное (O (n)) время:

import random

experiment_size = [1,10,100,1000,10000,100000]

for number in experiment_size:
    last = False # track whether the last 3 flips were tails. False = don't care, 
                 # True = tails
    last_2 = False
    last_3 = False

    success = 0
    runs = 0
    while success < number:
        runs += 1
        last_3 = last_2 #bump the 3rd from last flip
        last_2 = last
        last = bool(random.getrandbits(1)) #get True or False, randomly
        if(last & last_2 & last_3): #if all are tails
            success += 1
            last, last_2, last_3 = False, False, False #reset so that you have to get 3
                                                       #in a row again
    print("Runs: " + str(runs) + "\nSuccesses: " + str(success) +"\nAverage: " + str(runs/success) + "\n")

Поскольку мы не просматриваем весь список для каждого повторения, это намного быстрее.