Является ли str.replace(..) заменой (..) ad nauseam стандартной идиомой в 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('&', '&amp;').replace('<', '&lt;').replace('>', '&gt;').replace("'", '&#39;').replace('"', '&quot;')

translation_table = {
    '&': '&amp;',
    '<': '&lt;',
    '>': '&gt;',
    "'": '&#39;',
    '"': '&quot;',
}

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 = [
    ('<', '&lt;'),
    ('>', '&gt;'),
    ...]

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('&', '&amp;').replace('<', '&lt;').replace('>', '&gt;').replace('"', '&quot;').replace("'", '&#39;'))

Ответ 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({'<': '&lt;', '>': '&gt;', "'": '&#39;', '"': '&quot;'})
    return replace_multi(string.replace('&', '&amp;'), 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('&', '&amp;').replace('<', '&lt;').replace('>', '&gt;').replace("'", '&#39;').replace('"', '&quot;')

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({'<': '&lt;', '>': '&gt;', "'": '&#39;', '"': '&quot;'})
    return replace_multi(string.replace('&', '&amp;'), 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),
       [('&', '&'),
        ('<', '&lt;'),
        ('>', '&gt;'),
        ("'", '&#39;'),
        ('"', '&quot;')],
       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(
        {'&': '&amp;',
         '<': '&lt;',
         '>': '&gt;',
         '"': '&quot;',
         "'": '&#39;'}
    )
    return ''.join(itertools.imap(replacer.__getitem__, a_string))

if __name__ == "__main__":
    print escape('''"Hello"<i> to George friend&co.''')

$ python so2484156.py 
&quot;Hello&quot;&lt;i&gt; to George&#39;s friend&amp;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= {
        '&': '&',
        '<': '&lt;',
        '>': '&gt;',
        '"': '&quot;',
        "'": '&#39;',
    }
    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. нет возможности столкнуться с ситуацией, когда первая '>' преобразуется в '>', а затем непреднамеренно снова в '>', потому что каждый символ/байт рассматривается только один раз для подстановки. поэтому эта часть в принципе прекрасна и алгоритмически корректна.

следующий вопрос - жизнеспособность, и это будет включать взгляд на производительность. если жизненно важная задача будет правильно завершена в 0,01 с использованием неудобного кода, но 1 с использованием удивительного кода, то неудобным может считаться предпочтительным на практике (но только если 1-я потеря потеряна на самом деле невыносима). вот код, который я использовал для тестирования; он включает в себя множество различных реализаций. он написан на python 3.1, поэтому мы можем использовать греческие буквы unicode для идентификаторов, которые сами по себе являются удивительными (zip в py3k возвращает то же, что и itertools.izip в py2):

import itertools                                                                  #01
                                                                                  #02
_replacements = {                                                                 #03
  '&': '&',                                                                   #04
  '<': '&lt;',                                                                    #05
  '>': '&gt;',                                                                    #06
  '"': '&quot;',                                                                  #07
  "'": '&#39;', }                                                                 #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('&', '&amp;').replace('<', '&lt;').replace('>', '&gt;')\    #24
    .replace("'", '&#39;').replace('"', '&quot;')                                 #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 год.