Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 16.06.2014 | нет комментариев

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

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

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

Возьмем для начала алгорифм в наивном исполнении:

def substr(text, pattern): 
	test_plan = []
	imap = {}
	for i, c in enumerate(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 i, c in enumerate(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 i, c in enumerate(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 символами. Этого немного даже для английского языка.

 

Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB