str.replace (..) .replace (..) бесконечно стандартная идиома в Python?
Например, скажите, что я хотел, чтобы функция вышла из строки для использования в HTML (как в фильтре Escape Django):
def escape(string):
"""
Returns the given string with ampersands, quotes and angle
brackets encoded.
"""
return string.replace('&', '&').replace('<', '<').replace('>', '>').replace("'", ''').replace('"', '"')
Это работает, но это становится ужасным быстро и, кажется, имеет плохую алгоритмическую производительность (в этом примере, строка неоднократно пересекается 5 раз). То, что было бы лучше, является чем-то вроде этого:
def escape(string):
"""
Returns the given string with ampersands, quotes and angle
brackets encoded.
"""
# Note that ampersands must be escaped first; the rest can be escaped in
# any order.
return replace_multi(string.replace('&', '&'),
{'<': '<', '>': '>',
"'": ''', '"': '"'})
Такая функция существует, или стандартная идиома Python должна использовать то, что я записал прежде?
9 ответов
У вас есть приложение, которое работает слишком медленно, и вы профилировали его, чтобы обнаружить, что строка, подобная этому фрагменту, замедляет его работу? Узкие места возникают в неожиданных местах.
Текущий сниппет проходит строку 5 раз, каждый раз выполняя одно действие. Вы предлагаете пройти его один раз, вероятно, делая пять дел каждый раз (или, по крайней мере, делая что-то каждый раз). Не ясно, что это автоматически улучшит мою работу. В настоящее время используется алгоритм O (n m) (при условии, что длина строки больше, чем указано в правилах), где n - длина строки, а m - количество правил замены.Я думаю, вы могли бы уменьшить алгоритмическую сложность до чего-то вроде O (n log (m)), и в конкретном случае, в котором мы находимся, - когда все исходные объекты представляют собой только один символ (но не в случае несколько вызовов заменяют в целом) —O (n), но это не имеет значения, поскольку m равно 5 , но n не ограничено .
Если m остается постоянным, то сложность обоих решений действительно достигает O (n). Мне непонятно, будет ли достойной задачей попытаться превратить пять простых проходов в один сложный, точное время которого я не могу угадать в настоящий момент. Если бы в нем было что-то, что могло бы улучшить его масштабирование, я бы подумал, что это гораздо более стоящая задача.
Выполнение всего за один проход, а не за последовательные проходы, также требует ответов на вопросы о том, что делать с конфликтующими правилами и как они применяются. Решение этих вопросов ясно с помощью цепочки replace .
По-видимому, это довольно распространено, чтобы реализовать это через регулярное выражение. Вы можете найти пример этого в ASPN и здесь .
Если вы работаете со строками не в Юникоде и Python <3.0, попробуйте альтернативный метод translate :
# Python < 3.0
import itertools
def escape(a_string):
replacer= dict( (chr(c),chr(c)) for c in xrange(256))
replacer.update(
{'&': '&',
'<': '<',
'>': '>',
'"': '"',
"'": '''}
)
return ''.join(itertools.imap(replacer.__getitem__, a_string))
if __name__ == "__main__":
print escape('''"Hello"<i> to George's friend&co.''')
$ python so2484156.py
"Hello"<i> to George's friend&co.
Это ближе к «одиночному сканированию» входной строки, как вы хотите.
РЕДАКТИРОВАТЬ
Я намеревался создать эквивалент unicode.translate , который не ограничивался бы заменой одного символа, поэтому я придумал ответ выше; Я получил комментарий пользователя "поток", который был почти полностью вне контекста, с единственной правильной точкой: приведенный выше код, как есть, предназначен для работы с байтовыми строками , а не с строками Unicode. . Есть очевидное обновление (например, unichr ()… xrange (sys.maxunicode + 1)), которое мне очень не нравится, поэтому я придумал другую функцию, которая работает как с юникодными, так и с байтовыми строками, учитывая, что Python гарантирует:
all( (chr(i)==unichr(i) and hash(chr(i))==hash(unichr(i)))
for i in xrange(128)) is True
Далее следует новая функция:
def escape(a_string):
replacer= {
'&': '&',
'<': '<',
'>': '>',
'"': '"',
"'": ''',
}
return ''.join(
itertools.starmap(
replacer.get, # .setdefault *might* be faster
itertools.izip(a_string, a_string)
)
)
Обратите внимание на использование starmap с последовательностью кортежей: для любого символа, не входящего в replacer dict, вернуть указанный символ.
Как насчет того, чтобы мы просто протестировали различные способы сделать это и посмотреть, какой из них окажется быстрее (при условии, что мы заботимся только о самом быстром способе сделать это).
def escape1(input):
return input.replace('&', '&').replace('<', '<').replace('>', '>').replace("'", ''').replace('"', '"')
translation_table = {
'&': '&',
'<': '<',
'>': '>',
"'": ''',
'"': '"',
}
def escape2(input):
return ''.join(translation_table.get(char, char) for char in input)
import re
_escape3_re = re.compile(r'[&<>\'"]')
def _escape3_repl(x):
s = x.group(0)
return translation_table.get(s, s)
def escape3(x):
return _escape3_re.sub(_escape3_repl, x)
def escape4(x):
return unicode(x).translate(translation_table)
test_strings = (
'Nothing in there.',
'<this is="not" a="tag" />',
'Something & Something else',
'This one is pretty long. ' * 50
)
import time
for test_i, test_string in enumerate(test_strings):
print repr(test_string)
for func in escape1, escape2, escape3, escape4:
start_time = time.time()
for i in xrange(1000):
x = func(test_string)
print '\t%s done in %.3fms' % (func.__name__, (time.time() - start_time))
print
Выполнение этого дает вам:
'Nothing in there.'
escape1 done in 0.002ms
escape2 done in 0.009ms
escape3 done in 0.001ms
escape4 done in 0.005ms
'<this is="not" a="tag" />'
escape1 done in 0.002ms
escape2 done in 0.012ms
escape3 done in 0.009ms
escape4 done in 0.007ms
'Something & Something else'
escape1 done in 0.002ms
escape2 done in 0.012ms
escape3 done in 0.003ms
escape4 done in 0.007ms
'This one is pretty long. <snip>'
escape1 done in 0.008ms
escape2 done in 0.386ms
escape3 done in 0.011ms
escape4 done in 0.310ms
Похоже, что простая замена их одного за другим идет быстрее всего.
Правка: Повторный запуск тестов с 1000000 итераций дает следующее для первых трех строк (четвертая на моей машине займет слишком много времени, чтобы я мог ждать = P):
'Nothing in there.'
escape1 done in 0.001ms
escape2 done in 0.008ms
escape3 done in 0.002ms
escape4 done in 0.005ms
'<this is="not" a="tag" />'
escape1 done in 0.002ms
escape2 done in 0.011ms
escape3 done in 0.009ms
escape4 done in 0.007ms
'Something & Something else'
escape1 done in 0.002ms
escape2 done in 0.011ms
escape3 done in 0.003ms
escape4 done in 0.007ms
Цифры в значительной степени соответствуют тем же. В первом случае они даже более последовательны, так как прямая замена струны сейчас самая быстрая.
Я предпочитаю что-нибудь чистое, например:
substitutions = [
('<', '<'),
('>', '>'),
...]
for search, replacement in substitutions:
string = string.replace(search, replacement)
Вот что делает Django :
def escape(html):
"""Returns the given HTML with ampersands, quotes and carets encoded."""
return mark_safe(force_unicode(html).replace('&', '&').replace('<', '<').replace('>', '>').replace('"', '"').replace("'", '''))
Вы можете использовать reduce:
reduce(lambda s,r: s.replace(*r),
[('&', '&'),
('<', '<'),
('>', '>'),
("'", '''),
('"', '"')],
string)
В соответствии с предложением bebraw, вот что я в итоге использовал (в отдельном модуле, конечно):
import re
class Subs(object):
"""
A container holding strings to be searched for and replaced in
replace_multi().
Holds little relation to the sandwich.
"""
def __init__(self, needles_and_replacements):
"""
Returns a new instance of the Subs class, given a dictionary holding
the keys to be searched for and the values to be used as replacements.
"""
self.lookup = needles_and_replacements
self.regex = re.compile('|'.join(map(re.escape,
needles_and_replacements)))
def replace_multi(string, subs):
"""
Replaces given items in string efficiently in a single-pass.
"string" should be the string to be searched.
"subs" can be either:
A.) a dictionary containing as its keys the items to be
searched for and as its values the items to be replaced.
or B.) a pre-compiled instance of the Subs class from this module
(which may have slightly better performance if this is
called often).
"""
if not isinstance(subs, Subs): # Assume dictionary if not our class.
subs = Subs(subs)
lookup = subs.lookup
return subs.regex.sub(lambda match: lookup[match.group(0)], string)
Пример использования:
def escape(string):
"""
Returns the given string with ampersands, quotes and angle
brackets encoded.
"""
# Note that ampersands must be escaped first; the rest can be escaped in
# any order.
escape.subs = Subs({'<': '<', '>': '>', "'": ''', '"': '"'})
return replace_multi(string.replace('&', '&'), escape.subs)
Намного лучше :). Спасибо за помощь.
Править
Да ладно, Майк Грэм был прав. Я протестировал его, и замена оказалась на намного медленнее.
Код:
from urllib2 import urlopen
import timeit
def escape1(string):
"""
Returns the given string with ampersands, quotes and angle
brackets encoded.
"""
return string.replace('&', '&').replace('<', '<').replace('>', '>').replace("'", ''').replace('"', '"')
def escape2(string):
"""
Returns the given string with ampersands, quotes and angle
brackets encoded.
"""
# Note that ampersands must be escaped first; the rest can be escaped in
# any order.
escape2.subs = Subs({'<': '<', '>': '>', "'": ''', '"': '"'})
return replace_multi(string.replace('&', '&'), escape2.subs)
# An example test on the stackoverflow homepage.
request = urlopen('http://stackoverflow.com')
test_string = request.read()
request.close()
test1 = timeit.Timer('escape1(test_string)',
setup='from __main__ import escape1, test_string')
test2 = timeit.Timer('escape2(test_string)',
setup='from __main__ import escape2, test_string')
print 'multi-pass:', test1.timeit(2000)
print 'single-pass:', test2.timeit(2000)
Вывод:
multi-pass: 15.9897229671
single-pass: 66.5422530174
Вот и все.
Хорошо, я сел и посчитал. Пожалуйста, не сердитесь на меня, я отвечаю специально, обсуждая решение ΩΤΖΙΟΥ, но это было бы несколько сложно впихнуть в комментарий, поэтому позвольте мне сделать это таким образом. Фактически, я также озвучу некоторые соображения, имеющие отношение к вопросу ФП.
Сначала я обсуждал с ΩΤΖΙΟΥ элегантность, правильность и жизнеспособность его подхода.Оказывается, предложение выглядит так, как будто оно использует (изначально неупорядоченный) словарь в качестве регистра для хранения пар подстановок, но на самом деле постоянно возвращает правильные результаты, хотя я утверждал, что это не так. это потому, что вызов itertools.starmap () в строке 11 ниже получает в качестве второго аргумента итератор по парам одиночных символов / байтов (подробнее об этом позже), который выглядит как [ ('h', 'h',), ('e', 'e',), ('l', 'l',), ...] . с этими парами символов / байтов неоднократно вызывается первый аргумент replacer.get . нет возможности столкнуться с ситуацией, когда сначала '>' преобразуется в '>' , а затем по неосторожности снова в '>' , потому что каждый символ / байт рассматривается только один раз для замены. так что эта часть в принципе прекрасна и алгоритмически правильна.
следующий вопрос - жизнеспособность, и это будет включать анализ производительности. если жизненно важная задача выполняется правильно за 0,01 с с использованием неудобного кода, но 1 с с использованием потрясающего кода, то неудобство может считаться предпочтительным на практике (но только если потеря 1 секунды на самом деле недопустима). вот код, который я использовал для тестирования; он включает в себя ряд различных реализаций. он написан на Python 3.1, поэтому мы можем использовать греческие буквы Unicode для идентификаторов, что само по себе замечательно ( zip в py3k возвращает то же самое, что и itertools.izip в py2):
import itertools #01
#02
_replacements = { #03
'&': '&', #04
'<': '<', #05
'>': '>', #06
'"': '"', #07
"'": ''', } #08
#09
def escape_ΤΖΩΤΖΙΟΥ( a_string ): #10
return ''.join( #11
itertools.starmap( #12
_replacements.get, #13
zip( a_string, a_string ) ) ) #14
#15
def escape_SIMPLE( text ): #16
return ''.join( _replacements.get( chr, chr ) for chr in text ) #17
#18
def escape_SIMPLE_optimized( text ): #19
get = _replacements.get #20
return ''.join( get( chr, chr ) for chr in text ) #21
#22
def escape_TRADITIONAL( text ): #23
return text.replace('&', '&').replace('<', '<').replace('>', '>')\ #24
.replace("'", ''').replace('"', '"') #25
это результаты синхронизации:
escaping with SIMPLE took 5.74664253sec for 100000 items
escaping with SIMPLE_optimized took 5.11457801sec for 100000 items
escaping TRADITIONAL in-situ took 0.57543013sec for 100000 items
escaping with TRADITIONAL took 0.62347413sec for 100000 items
escaping a la ΤΖΩΤΖΙΟΥ took 2.66592320sec for 100000 items
выясняется, что беспокойство оригинального автора о том, что «традиционный» метод быстро становится «уродливым и, кажется, имеет низкую алгоритмическую производительность», кажется частично необоснованным при включении в этот контекст. на самом деле он работает лучше всего; когда они спрятаны в вызов функции, мы действительно видим 8% -ное снижение производительности («вызов методов стоит дорого», но в целом вы все равно должны это делать). Для сравнения, реализация ΤΖΩΤΖΙΟΥ занимает примерно в 5 раз больше времени, чем традиционный метод, что, учитывая его более высокую сложность, должно конкурировать с давно отточенными и оптимизированными строковыми методами Python, неудивительно.
Здесь есть еще один алгоритм, ПРОСТОЙ. насколько я могу судить, это очень похоже на то, что делает метод ΤΖΩΤΖΙΟΥ: он выполняет итерацию по символам / байтам в тексте и выполняет поиск для каждого, затем объединяет все символы / байты вместе и возвращает полученный экранированный текст. вы можете видеть, что там, где один из способов сделать это включает в себя довольно длинную и загадочную формулировку, реализация SIMPLE на самом деле понятна с первого взгляда.
Что меня здесь действительно сбивает с толку, так это то, насколько плох ПРОСТОЙ подход с точки зрения производительности: он примерно в 10 раз медленнее традиционного, а также в два раза медленнее, чем метод ΩΤΖΙΟΥ. я здесь совершенно в недоумении, может кто-нибудь придумает, почему так должно быть. он использует только самые основные строительные блоки python и работает с двумя неявными итерациями, поэтому он избегает создания списков для выброса и всего остального, но все равно работает медленно, и я не знаю почему.
позвольте мне завершить этот обзор кода замечанием о достоинствах решения ΩΤΖΙΟΥ. Я достаточно ясно дал понять, что считаю код трудным для чтения и слишком раздутым для поставленной задачи. более критично, однако, я считаю, как он обращается с персонажами и следит за тем, чтобы для данного небольшого диапазона символов они вели себя побайтово, что немного раздражало. уверен, что это работает для поставленной задачи, но как только я повторяю, напримерпо строке байтов 'ΩΤΖΙΟΥ' я перебираю соседние байты, представляющие отдельные символы. в большинстве ситуаций именно этого следует избегать; Именно по этой причине в py3k «строки» теперь являются «объектами юникода» старого образца, а старые «строки» стали «байтами» и «байтовым массивом». если бы я назначил одну особенность py3k, которая могла бы гарантировать, возможно, дорогостоящую миграцию кода из серии 2 в серию 3, это было бы это единственное свойство py3k. С тех пор 98% всех моих проблем с кодировкой просто исчезли, и нет никакого хитрого хака, который заставил бы меня серьезно усомниться в моем решении. указанный алгоритм не является «концептуально 8-битным и безопасным для юникода», что для меня является серьезным недостатком, учитывая, что это 2010 год.