Является ли str.replace(..) заменой (..) ad nauseam стандартной идиомой в Python?
Например, я хочу, чтобы функция удаляла строку для использования в HTML (как в Django escape-фильтр):
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 использовать то, что я написал раньше?
Ответы
Ответ 1
У вас есть приложение, которое работает слишком медленно, и вы профилировали его, чтобы найти, что строка, подобная этому фрагменту, вызывает ее медленную работу? Узкие места происходят в неожиданных местах.
Текущий фрагмент обходит строку 5 раз, делая каждую вещь каждый раз. Вы предлагаете пройти его один раз, возможно, делая каждый раз по пять вещей (или, по крайней мере, делая что-то каждый раз). Непонятно, что это автоматически сделает мне лучшую работу. В настоящее время используется алгоритм O (nm) (при условии, что длина строки больше, чем материал в правилах), где n - длина строки, а m - количество правил подстановки. Вы могли бы, я думаю, уменьшить алгоритмическую сложность до чего-то вроде O (nlog (m)) и в конкретном случае, в котором мы находимся, где исходные вещи - всего один символ (но не в случае нескольких вызовов replace вообще) -O (n), но это не имеет значения, так как m равно 5, но n неограничен.
Если m поддерживается постоянным, то сложность обоих решений действительно идет на O (n). Мне непонятно, что будет достойной задачей попытаться превратить пять простых проходов в один сложный, фактическое время, о котором я не могу догадаться в настоящий момент. Если бы в этом было что-то, что могло бы улучшить его масштабирование, я бы подумал, что это гораздо более стоящая задача.
Выполнение всего за один проход, а не последовательные проходы также требует ответа на вопросы о том, что делать с противоречивыми правилами и как они применяются. Разрешение этих вопросов ясно с помощью цепочки replace.
Ответ 2
Как насчет того, чтобы мы просто тестировали различные способы сделать это и видеть, что быстрее выходит (если мы только заботимся о самом быстром способе сделать это).
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
Цифры почти одинаковы. В первом случае они на самом деле даже более согласованы, так как прямая замена строк выполняется быстрее.
Ответ 3
Я предпочитаю что-то чистое:
substitutions = [
('<', '<'),
('>', '>'),
...]
for search, replacement in substitutions:
string = string.replace(search, replacement)
Ответ 4
Что то, что 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("'", '''))
Ответ 5
В соответствии с предложением 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)
Намного лучше:). Спасибо за помощь.
Изменить
Nevermind, Майк Грэхем был прав. Я сравнивал его, и замена заканчивается на самом деле намного медленнее.
код:
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
Так много для этого.
Ответ 6
Вы можете использовать сокращение:
reduce(lambda s,r: s.replace(*r),
[('&', '&'),
('<', '<'),
('>', '>'),
("'", '''),
('"', '"')],
string)
Ответ 7
По-видимому, это довольно распространено, чтобы реализовать это через регулярное выражение. Вы можете найти пример этого в ASPN и здесь.
Ответ 8
Если вы работаете с строками, отличными от Unicode, и 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 friend&co.''')
$ python so2484156.py
"Hello"<i> to George's friend&co.
Это ближе к "одиночному сканированию" входной строки в соответствии с вашим желанием.
ИЗМЕНИТЬ
Мое намерение состояло в создании эквивалента unicode.translate, который не ограничивался заменой одного символа, поэтому я придумал ответ выше; Я получил комментарий пользователя "поток", который почти полностью вышел из контекста, с одной правильной точкой: вышеприведенный код, как есть, предназначен для работы с байтовыми строками, а не с строками unicode. Существует очевидное обновление (то есть unichr()... xrange (sys.maxunicode + 1)), который мне сильно не нравится, поэтому я придумал еще одну функцию, которая работает как в unicode, так и в байтовых строках, учитывая, что 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 с последовательностью кортежей: для любого символа, не содержащего dictacer dict, возвращаем указанный символ.
Ответ 9
ok, поэтому я сел и сделал математику. PLS не рассердился на меня, я отвечаю конкретно, обсуждая решение TΖΩΤΖΙΟΥs, но это было бы несколько сложно сделать в комментариях, поэтому позвольте мне сделать это таким образом. на самом деле я также рассмотрю некоторые соображения, имеющие отношение к вопросу ОП.
сначала, я обсуждал с ΤΖΩΤΖΙΟΥ элегантность, правильность и жизнеспособность его подхода. оказывается, что это похоже на предложение, в то время как он использует (по сути неупорядоченный) словарь в качестве регистра для хранения пар замещения, на самом деле последовательно возвращает правильные результаты, где я утверждал, что это не будет. это связано с тем, что вызов itertools.starmap() в строке 11 ниже получает в качестве второго аргумента итератор поверх пар одиночных символов/байтов (подробнее об этом позже), который выглядит как [ ( 'h', 'h', ), ( 'e', 'e', ), ( 'l', 'l', ), ... ]. эти пары символов/байтов - это то, с чем неоднократно вызывается первый аргумент replacer.get. нет возможности столкнуться с ситуацией, когда первая '>' преобразуется в '>', а затем непреднамеренно снова в '&gt;', потому что каждый символ/байт рассматривается только один раз для подстановки. поэтому эта часть в принципе прекрасна и алгоритмически корректна.
следующий вопрос - жизнеспособность, и это будет включать взгляд на производительность. если жизненно важная задача будет правильно завершена в 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% -ный штраф за исполнение ( "методы вызова дороги, но в целом вы все равно должны это делать" ). в сравнении, реализация TΖΩΤΖΙΟΥs занимает около 5 раз до тех пор, пока традиционный метод, который, учитывая его более высокую сложность, который должен конкурировать с длинными отточенными, оптимизированными строковыми методами pythons, не удивляет.
здесь есть еще один алгоритм, простой. насколько я вижу, это очень точно делает то, что делает метод ΤΖΩΤΖΙΟΥs: он выполняет итерации над символами/байтами в тексте и выполняет поиск для каждого, затем объединяет все символы/байты вместе и возвращает полученный экранированный текст. вы можете видеть, что, когда один из способов сделать это включает довольно длительную и правдивую формулировку, реализация SIMPLE на самом деле понятна с первого взгляда.
что действительно меня здесь трогает, так это то, как сильно ПРОСТОЙ подход работает в производительности: он примерно в 10 раз медленнее, чем традиционный, а также в два раза медленнее, чем метод TΖΩΤΖΙΟΥs. я здесь совершенно не понимаю, может быть, кто-то может придумать, почему это должно быть так. он использует только самые основные строительные блоки python и работает с двумя неявными итерациями, поэтому он избегает создания списков отбрасывания и всего, но он все еще медленный, и я не знаю почему.
позвольте мне завершить этот обзор кода с замечанием о достоинстве решения TΖΩΤΖΙΟΥs. я сделал это достаточно ясным, я считаю, что код трудно читать и слишком раздутый для этой задачи. Тем не менее, более критичным, чем я, я считаю, что он относится к персонажам и уверен, что для данного небольшого диапазона персонажей они будут вести себя как байт-подобный стиль, немного раздражающий. уверен, что он работает для этой задачи, но как только я повторяю, например. над bytestring 'ΤΖΩΤΖΙΟΥ', что я делаю, перебирает смежные байты, представляющие одиночные символы. в большинстве ситуаций это именно то, чего вам следует избегать; это именно то, почему в строках py3k теперь есть "юникодные объекты старого", а "старые" стали "байтами" и "bytearray". если бы я должен был назначить одну особенность py3k, которая могла бы гарантировать возможную дорогостоящую миграцию кода из серии 2 в 3 серии, это было бы единственным свойством py3k. 98% всех моих проблем с кодировкой только что распустились с тех пор, период, и нет умного взлома, который мог бы заставить меня серьезно сомневаться в моем движении. указанный алгоритм не "концептуально 8бит-чистый и безопасен в Юникоде, который для меня является серьезным недостатком, учитывая, что это 2010 год.
