Микрооптимизации в Питоне

Давайте начистоту, все мы любим микрооптимизации. Да, как правило они бессмысленны, а иногда и вредны. Никакие хитрости не помогут, если алгоритм плох, или инструментальные средства изначально выбраны неправильно.

С другой стороны, само занятие микрооптимизацией, при поддержке, конечно же, тестов и контроле инвариантов, на нервной и пищеварительной системах сказывается исключительно благотворно. Код находится под контролем, ничего не ломается, ничего не меняется, только замеры производительности становятся все лучше и лучше. Лучше и лучше. Душеполезнейшее занятие.

В этой заметке я бы хотел поделиться замечаниями по микрооптимизации алгоритма поиска подстроки в строке использующего карту вероятностей. Все описанное касается только 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», имея на то полное право, и все поломается. Стоит ли того десяток микросекунд на тесте? Едва ли.

Выводы

Микрооптимизация как явление — это и хорошо, и плохо. Это замечательное упражнение, позволяющее узнать глубже язык, его структуры данных, его особенности и неочевидности. Но для живого рабочего кода, исключая исключения, повышение производительности на проценты, а не на порядки — плохой фокус. Увлекшись оптимизацией очень просто забыть то, для чего мы делаем то, что делаем.