使用列表理解和随机性模拟翻转硬币，代码首先工作然后挂起

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，坏。真的很糟糕的你运行的更多实验）。

我掀起了一个（基本的）程序，它将在线性（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")

因为我们没有为每次重复遍历整个列表，所以速度要快得多。