Самая быстрая реализация для выполнения множественных подстановок строк в Python

Question

Есть ли какой-либо рекомендуемый способ сделать несколько подстановок строк, кроме выполнения replace цепочки строк (например, text.replace(a, b).replace(c, d).replace(e, f)...)?Как бы вы, например, реализовали быструю функцию, которая ведет себя как PHP htmlspecialchars в Python?

Я сравнил (1) метод множественного replace, (2) метод регулярного выражения и (3)Метод Мэтта Андерсона.

При n = 10 прогонов результаты выглядят следующим образом:

На 100 символов:

TIME: 0 ms [ replace_method(str) ]
TIME: 5 ms [ regular_expression_method(str, dict) ]
TIME: 1 ms [ matts_multi_replace_method(list, str) ]

На 1000 символов:

TIME: 0 ms [ replace_method(str) ]
TIME: 3 ms [ regular_expression_method(str, dict) ]
TIME: 2 ms [ matts_multi_replace_method(list, str) ]

На 10000 символов:

TIME: 3 ms [ replace_method(str) ]
TIME: 7 ms [ regular_expression_method(str, dict) ]
TIME: 5 ms [ matts_multi_replace_method(list, str) ]

На 100000 символов:

TIME: 36 ms [ replace_method(str) ]
TIME: 46 ms [ regular_expression_method(str, dict) ]
TIME: 39 ms [ matts_multi_replace_method(list, str) ]

На 1000000 символов:

TIME: 318 ms [ replace_method(str) ]
TIME: 360 ms [ regular_expression_method(str, dict) ]
TIME: 320 ms [ matts_multi_replace_method(list, str) ]

На 3687809 символов:

TIME: 1.277524 sec [ replace_method(str) ]
TIME: 1.290590 sec [ regular_expression_method(str, dict) ]
TIME: 1.116601 sec [ matts_multi_replace_method(list, str) ]

Так что поблагодарите Мэтта за избиение метода multi replace на довольно большой входной строке.

У кого-нибудь есть идеи, как обыграть его на меньшей строке?

Answer 1

Может быть, что-то вроде следующего?Разделите текст на части с первым заменяемым элементом «from», затем рекурсивно разбивайте каждую из этих частей на части со следующим заменяемым элементом «from» и т. Д., Пока не пройдете все замены,Затем присоедините к каждому элементу замены "to", когда завершится рекурсивная функция.

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

def multi_replace(pairs, text):
    stack = list(pairs)
    stack.reverse()
    def replace(stack, parts):
        if not stack:
            return parts
        # copy the stack so I don't disturb parallel recursions
        stack = list(stack) 
        from_, to = stack.pop()
        #print 'split (%r=>%r)' % (from_, to), parts
        split_parts = [replace(stack, part.split(from_)) for part in parts]
        parts = [to.join(split_subparts) for split_subparts in split_parts]
        #print 'join (%r=>%r)' % (from_, to), parts
        return parts
    return replace(stack, [text])[0]


print multi_replace(
    [('foo', 'bar'), ('baaz', 'foo'), ('quux', 'moop')], 
    'foobarbaazfooquuxquux')

для:

barbarfoobarmoopmoop

Answer 2

Обычно метод .replace превосходит все остальные методы.(См. Мои тесты выше.)

Answer 3

Как быстро?Кроме того, насколько велики ваши строки?

Существует довольно простой рецепт для создания регулярного выражения для работы на другом сайте.Может потребоваться некоторая настройка для обработки метасимволов регулярных выражений;Я не слишком внимательно присматривался.

Если это не достаточно хорошо, вам, честно говоря, вам, вероятно, нужно написать код на C.Вы можете создать простой конечный автомат для выполнения всех замен, а затем обработать любую строку за байтом без возврата по машине, чтобы фактически выполнить работу.Однако я сомневаюсь, что вы побьете движок регулярных выражений, не переходя на Си и не оптимизируя его.