Python - почему регулярное выражение гораздо эффективнее, чем поиск в списке?

Question

Когда я взглянул на проблему Google Code Jam Qualification Round 2009:: Alien Language, простая идея состоит в том, что вы генерируете все возможные строки из шаблона и удерживаете его в списке, а затем проверяете и подсчитываете согласованные строки. Этот алгоритм прост, прямолинейный, но он потребляет невероятно большую оперативную память, и ваш ноутбук, несомненно, умрет.

Другой способ решить эту проблему - заменить "()" на "[]" для использования регулярного выражения. Python встроенный re.match() и string.replace() занял менее нескольких секунд, чтобы пройти большой тест. Теперь вопрос, почему регулярное выражение гораздо более мощное?

В моем понимании может быть определен механизм, такой как функция yield, которая позволяет генерировать «генератор» - итерабельный и однопроходный. Но это моя догадка.

Answer 1

Ваша интуиция в значительной степени правильная.

Для получения подробной информации о компьютерных науках вы можете найти идеи «nondeterministic finite automaton» и «deterministic finite automaton».

Вы можете думать о регулярных выражениях компилятора как-то, что принимает регулярное выражение и производит функцию, которая работает на вашей входной строке и сохраняет состояние, в котором он обновляет, как он потребляет входную строку, основанную на правилах, полученных из регулярных выражений ,

Надеюсь, я не разделка вещи слишком много, если я скажу, что концептуально регулярное выражение, скажем, (ab|cd) будет производить то, что ведет себя так:

def match_ab_or_cd(s): 
    state = "start" 
    for c in s: 
     if state == "start": 
      if c == "a": 
       state = "state_a" 
      elif c == "c": 
       state = "state_c" 
     elif state == "state_a": 
      if c == "b": 
       return True 
      elif c == "a": 
       state = "state_a" 
      else: 
       state = "start" 
     elif state == "state_c": 
      if c == "d": 
       return True 
      elif c == "c": 
       state = "state_c" 
      else: 
       state = "start" 
    return False 


>>> match_ab_or_cd("ab") 
True 
>>> match_ab_or_cd("cd") 
True 
>>> match_ab_or_cd("ae") 
False 
>>> match_ab_or_cd("aaaaab") 
True 

Так что для многих простых регулярных выражений, что можно производить машина, которая должна потреблять только каждый символ во входной строке один раз. Имейте в виду, что существуют регулярные выражения, которые не играют хорошо, например (x+x+)+y.

О, и вот a fun tool that visualises how regular expressions turn into state machines. Вы можете думать о первой картине, которую она создает как промежуточную стадию, а вторая картина - это то, что можно перевести на машину, как показано выше.