Давайте начистоту, все мы любим микрооптимизации. Да, как правило они бессмысленны, а иногда и вредны. Никакие хитрости не помогут, если алгоритм плох, или инструментальные средства изначально выбраны неправильно.
С другой стороны, само занятие микрооптимизацией, при поддержке, конечно же, тестов и контроле инвариантов, на нервной и пищеварительной системах сказывается исключительно благотворно. Код находится под контролем, ничего не ломается, ничего не меняется, только замеры производительности становятся все лучше и лучше. Лучше и лучше. Душеполезнейшее занятие.
В этой заметке я бы хотел поделиться замечаниями по микрооптимизации алгоритма поиска подстроки в строке использующего карту вероятностей. Все описанное касается только CPython, в других реализациях все может быть немного по-другому.
Возьмем для начала алгоритм в наивном исполнении:
def substr(text, pattern):
test_plan = []
imap = {}
for c, i in zip(pattern, range(len(pattern))):
test_plan += [(stat_map[c], i, c)]
if not c in imap:
imap[c] = [i]
else:
imap[c] = imap[c] + [i]
test_plan.sort()
for i in range(0, len(text), len(pattern)):
c = text[i]
if c in imap:
for h in imap[c]:
found = True
for (_, ti, tc) in test_plan:
if i - h + ti >= len(text) or text[i - h + ti] != tc:
found = False
break
if found:
return i-h
return -1
Алгоритм работает так: для паттерна составляется тест-план, включающий каждый символ и его позицию. Тест-план сортируется по вероятности вхождения символа в текст таким образом, что наименее вероятный символ будет проверяться в первую очередь. Также для паттерна составляется карта вхождений символа. Каждому символу ставится в соотвествие список его вхождений. Например, для строки «Hello world!» тест-план и карта будут соответственно такими:
[(11, '!'), (0, 'H'), (6, 'w'), (2, 'l'), (3, 'l'), (9, 'l'), (4, 'o'), (7, 'o'), (10, 'd'), (8, 'r'), (1, 'e'), (5, ' ')]
{'!': [11], ' ': [5], 'e': [1], 'd': [10], 'H': [0], 'l': [2, 3, 9], 'o': [4, 7], 'r': [8], 'w': [6]}
Далее для текста проверяется каждый n символ, где n — длина паттерна. Если символ содержится в карте, то для каждой его позиции в паттерне выполняется проверка остальных символов согласно тест-плану до первого расхождения. Если ни одного расхождения нет, все хорошо — мы нашли первое вхождение.
Сделаем замер производительности: время поиска нескольких строк в значительном объеме текста. Для этих целей в CPython есть профайлер. Для профилирования кода достаточно запустить его с модулем profile: python -m profile your_code.py.
Детали замера несущественны. Мы просто подгоним размер текста, чтобы цифры замера были одновременно и достаточно большими для сравнения, и достаточно маленькими, чтобы не ждать их долго каждую итерацию. В моем случае первое число: 2.35 с.
Теперь попробуем оптимизировать. Первое и очевидное: избавиться от проверок в карте. Вместо if a in map мы можем воспользоваться конструкцией map.get(a, []), которая возвращает значение по умолчанию, если в карте нет нужного значения. Делаем замер, и… 3.0. Питон, в отличие от C++ STL, использует хеш-таблицы для организации словарей, они же мапы, карты и ассоциативные массивы. Проверка на содержание выполняется в среднем за константное время, и время это меньше, чем время создания нового списка в текущем контексте.
Сразу скажу, что замена карты списком, по образцу плюсовой же замены ассоциативного массива на вектор, тоже плодов не даст. В плюсах мы уходим от логарифмической сложности к константной, здесь же нам уходить не от чего.
Хорошо, но все-таки лишняя проверка в цикле выглядит плохо. Ее можно убрать, если убедиться, что все возможные символы заведомо лежат в карте, но возвращают пустой список. Пробуем… 2.3. Чуть лучше, но незначительно. Зато теперь с используется в одном месте и мы можем ее не объявлять, а сразу брать в этом месте text[i]. Код теперь выглядит так:
def substr(text, pattern):
test_plan = []
imap = {}
imap = {}
for i in range(128):
imap[chr(i)] = []
for c, i in zip(pattern, range(len(pattern))):
test_plan += [(stat_map[c], i, c)]
imap[c] += [i]
test_plan.sort()
for i in range(0, len(text), len(pattern)):
for h in imap[text[i]]:
found = True
for (_, ti, tc) in test_plan:
ni = i - h + ti
if ni >= len(text) or text[ni] != tc:
found = False
break
if found:
return i-h
return -1
Проверяем. 2.25. Объявление переменных, стало быть, дорогое удовольствие. Попробуем заодно избавиться от ni. 2.26. Разница невелика, но стало хуже. Мы обменяли одну локальную переменную на два сложения и они примерно друг друга стоят.
К вопросу о лишних переменных. В кортеже тест-плана первое значение — вероятность вхождения — используется только для сортировки. Мы же ее получаем в неиспользуемую переменную _. Кстати, это не эрланговский вайлд-карт, а вполне легитимное имя переменной. Просто оно хорошо смотрится в роли бесполезного значения. «Почистим» же тест-план, чтобы лишнего не брать. 2.18. Хорошо.
Далее к циклу. Конечно, рефлексы сишника подсказывают, что создавать список и ходить по нему — занятие бесполезное. Цикл можно переписать так, чтобы избавиться от «рендж».
i = 0
len_text = len(text)
len_pattern = len(pattern)
while i < len_text:
for h in imap[text[i]]:
found = True
for (ti, tc) in test_plan:
ni = i - h + ti
if ni >= len(text) or text[ni] != tc:
found = False
break
if found:
return i-h
i += len_pattern
И… 2.55. Это не работает. Питон очень эффективен со списками. Зато вот мысль предрассчитать длину текста — здравая.
if ni >= len_text or text[ni] != tc:
1.88. Конечно же, len не считает длину строки перебором, как в чистом Си. Это довольно эффективная функция, но все-таки функция. Лишний вызов функции дороже, чем доступ к переменной.
И к слову о проверках. А насколько часто у нас будет превышаться длина строки? Не более чем (n^2)/2 раз, если я правильно понимаю. Так как мы считаем n длиной паттерна, а не текста, это не очень много. В Питоне or работает до первой правды. То есть если слева стоит более часто выполнимое условие, вся проверка работает эффективнее. Поменяем местами условия. 1.77. И кстати, раз уж теперь второе условие считается не так уж часто, обмен переменой на плюсы может сработать.
Осталась, правда, одна некрасивость. Переменная found. Если бы в языке был goto или break с параметрами, можно было бы без нее обойтись. В Питоне goto нет, но есть else. Да, это неочевидно, но else работает с циклами и выполняется, когда цикл проходит без единого break. Замеряем. 1.55. И код выглядит так.
def substr(text, pattern):
test_plan = []
imap = {}
imap = {}
for i in range(128):
imap[chr(i)] = []
for c, i in zip(pattern, range(len(pattern))):
test_plan += [(stat_map[c], i, c)]
imap[c] += [i]
test_plan.sort()
test_plan = [(ti, tc) for (_, ti, tc) in test_plan]
text_len = len(text)
for i in range(0, len(text), len(pattern)):
for h in imap[text[i]]:
for (ti, tc) in test_plan:
ni = i - h + ti
if text[ni] != tc or ni >= text_len:
break
else:
return i-h
return -1
Очень нехорошо, что теперь код работает только с 128 символами. Этого мало даже для английского языка. Рано или поздно кто-то захочет написать «naïve», имея на то полное право, и все поломается. Стоит ли того десяток микросекунд на тесте? Едва ли.
Выводы
Микрооптимизация как явление — это и хорошо, и плохо. Это замечательное упражнение, позволяющее узнать глубже язык, его структуры данных, его особенности и неочевидности. Но для живого рабочего кода, исключая исключения, повышение производительности на проценты, а не на порядки — плохой фокус. Увлекшись оптимизацией очень просто забыть то, для чего мы делаем то, что делаем.
Автор: akalenuk
