Обнаружение всех определенных подстрок в последовательности Python

Question

Приведенный ниже код демонстрирует игру Пенни - вероятность появления одной последовательности голов и хвостов перед другой. В частности, я задаюсь вопросом об эффективности while not all(i in sequence for i in [pattern1, pattern2]): и более глобально о ее оптимальном кодировании в Python. Является ли это разумной попыткой в ​​Python или является более эффективным способом. Чем больше я думаю, что знаю о Python, тем больше я считаю, что всегда есть лучший способ!

import random 

pattern1 = 'TTT' 
pattern2 = 'HTT' 

pattern1Wins = 0 
pattern2Wins = 0 

trials = 1000 

for _ in range(trials): 

    sequence = '' 

    while not all(i in sequence for i in [pattern1, pattern2]): 
     sequence += random.choice(['H','T']) 

    if sequence.endswith(pattern1): 
     pattern2Wins += 1 
    else: 
     pattern1Wins += 1 

print pattern1, 'wins =', pattern1Wins 
print pattern2, 'wins =', pattern2Wins 

print str((max([pattern1Wins, pattern2Wins])/float(trials) * 100)) + '%' 

Answer 1

Создать вашу последовательность с тремя вызовами выбора изначально, то просто добавьте два последних и новый выбор не зацикливание, пока один из появляется узоры:

pattern1 = 'TTT' 
pattern2 = 'HTT' 
trials = 1000 
d = {pattern1: 0, pattern2: 0} 

for _ in range(trials): 
    sequence = random.choice("HT") + random.choice("HT") + random.choice("HT") 
    while sequence not in {pattern1, pattern2}: 
     sequence = sequence[-2:] + random.choice("HT") 
    d[sequence] += 1 

print pattern1, 'wins =', d[pattern1] 
print pattern2, 'wins =', d[pattern2] 
print str((max([d[pattern1], d[pattern2]])/float(trials) * 100)) + '%' 

Некоторые тайминги с random.seed:

In [19]: import random 
In [20]: random.seed(0) 
In [21]: %%timeit 
    ....: pattern1 = 'TTT' 
    ....: pattern2 = 'HTT' 
    ....: trials = 1000 
    ....: patterns = {'TTT': 0, 'HTT': 0} 
    ....: for _ in range(trials): 
    ....:  sequence = '' 
    ....:  while True: 
    ....:   sequence += random.choice('HT') 
    ....:   for pattern in patterns: 
    ....:    if sequence.endswith(pattern): 
    ....:     patterns[pattern] += 1 
    ....:     break 
    ....:   else: 
    ....:    continue 
    ....:   break 
    ....: 
100 loops, best of 3: 7.28 ms per loop 

In [22]: %%timeit 
    ....: pattern1 = 'TTT' 
    ....: pattern2 = 'HTT' 
    ....: trials = 1000 
    ....: d = {pattern1: 0, pattern2: 0} 
    ....: for _ in range(trials): 
    ....:  sequence = random.choice("HT") + random.choice("HT") + random.choice("HT") 
    ....:  while sequence not in {pattern1, pattern2}: 
    ....:   sequence = sequence[-2:] + random.choice("HT") 
    ....:  d[sequence] += 1 
    ....: 
100 loops, best of 3: 4.95 ms per loop 

In [23]: %%timeit 
pattern1 = 'TTT' 
pattern2 = 'HTT' 
pattern1Wins = 0 
pattern2Wins = 0 
trials = 1000 
for _ in range(trials): 
    sequence = ''        
    while True:          
     sequence += random.choice('HT') 
     if sequence.endswith(pattern1): 
      pattern2Wins += 1   
     elif sequence.endswith(pattern2): 
      pattern1Wins += 1 
     else: 
      continue 
     break 
    ....: 
100 loops, best of 3: 6.65 ms per loop 

Answer 2

Учитывая, что вы заботитесь только о последних трех символов является одним из двух подстрок, я бы что-то вроде:

sequence = '' 
while True: 
    sequence += random.choice('HT') 
    if sequence.endswith(pattern1): 
     pattern2Wins += 1 
    elif sequence.endswith(pattern2): 
     pattern1Wins += 1 
    else: 
     continue 
    break 

endswith является гораздо более эффективным, чем in, потому что это не проверьте всю строку для совпадений (где вы уже знаете, что не будет).

---

В качестве альтернативы, вы можете вынесем pattern1 и pattern2 к словарю {pattern: wins}:

patterns = {'TTT': 0, 'HTT': 0} 

... 

sequence = '' 
while True: 
    sequence += random.choice('HT') 
    for pattern in patterns: 
     if sequence.endswith(pattern): 
      patterns[pattern] += 1 
      break 
    else: 
     continue 
    break 

---

Наконец, конкатенация с + не очень эффективным; строки неизменяемы, поэтому каждый раз создается новая строка. Вместо этого, рассмотреть вопрос о создании результатов в список, и проверка последние три элемента него:

sequence = [] 
while True: 
    sequence.append(random.choice('HT')) 
    if sequence[-3:] == ['H', 'T', 'T']: 
     ...