Массовая замена строки в python?

mydict = {"&y":"\033[0;30m",
          "&c":"\033[0;31m",
          "&b":"\033[0;32m",
          "&Y":"\033[0;33m",
          "&u":"\033[0;34m"}
mystr = "The &yquick &cbrown &bfox &Yjumps over the &ulazy dog"

for k, v in mydict.iteritems():
    mystr = mystr.replace(k, v)

print mystr
The ←[0;30mquick ←[0;31mbrown ←[0;32mfox ←[0;33mjumps over the ←[0;34mlazy dog

Я взял на себя смелость сравнить несколько решений:

mydict = dict([('&' + chr(i), str(i)) for i in list(range(65, 91)) + list(range(97, 123))])

# random inserts between keys
from random import randint
rawstr = ''.join(mydict.keys())
mystr = ''
for i in range(0, len(rawstr), 2):
    mystr += chr(randint(65,91)) * randint(0,20) # insert between 0 and 20 chars

from time import time

# How many times to run each solution
rep = 10000

print 'Running %d times with string length %d and ' \
      'random inserts of lengths 0-20' % (rep, len(mystr))

# My solution
t = time()
for x in range(rep):
    for k, v in mydict.items():
        mystr.replace(k, v)
    #print(mystr)
print '%-30s' % 'Tor fixed & variable dict', time()-t

from re import sub, compile, escape

# Peter Hansen
t = time()
for x in range(rep):
    sub(r'(&[a-zA-Z])', r'%(\1)s', mystr) % mydict
print '%-30s' % 'Peter fixed & variable dict', time()-t

# Claudiu
def multiple_replace(dict, text): 
    # Create a regular expression  from the dictionary keys
    regex = compile("(%s)" % "|".join(map(escape, dict.keys())))

    # For each match, look-up corresponding value in dictionary
    return regex.sub(lambda mo: dict[mo.string[mo.start():mo.end()]], text)

t = time()
for x in range(rep):
    multiple_replace(mydict, mystr)
print '%-30s' % 'Claudio variable dict', time()-t

# Claudiu - Precompiled
regex = compile("(%s)" % "|".join(map(escape, mydict.keys())))

t = time()
for x in range(rep):
    regex.sub(lambda mo: mydict[mo.string[mo.start():mo.end()]], mystr)
print '%-30s' % 'Claudio fixed dict', time()-t

# Andrew Y - variable dict
def mysubst(somestr, somedict):
  subs = somestr.split("&")
  return subs[0] + "".join(map(lambda arg: somedict["&" + arg[0:1]] + arg[1:], subs[1:]))

t = time()
for x in range(rep):
    mysubst(mystr, mydict)
print '%-30s' % 'Andrew Y variable dict', time()-t

# Andrew Y - fixed
def repl(s):
  return mydict["&"+s[0:1]] + s[1:]

t = time()
for x in range(rep):
    subs = mystr.split("&")
    res = subs[0] + "".join(map(repl, subs[1:]))
print '%-30s' % 'Andrew Y fixed dict', time()-t

Результаты в Python 2.6

Running 10000 times with string length 490 and random inserts of lengths 0-20
Tor fixed & variable dict      1.04699993134
Peter fixed & variable dict    0.218999862671
Claudio variable dict          2.48400020599
Claudio fixed dict             0.0940001010895
Andrew Y variable dict         0.0309998989105
Andrew Y fixed dict            0.0310001373291

Решения Клаудиу и Эндрю продолжали снижаться до 0, поэтому мне пришлось увеличить его до 10 000 прогонов.

Я запустил его в Python 3 (из-за юникода) с заменой символов с 39 на 1024 (38 — это амперсанд, поэтому я не хотел его включать). Длина строки до 10 000, включая около 980 замен с переменными случайными вставками длины 0-20. Значения Юникода от 39 до 1024 вызывают символы длиной 1 и 2 байта, что может повлиять на некоторые решения.

mydict = dict([('&' + chr(i), str(i)) for i in range(39,1024)])

# random inserts between keys
from random import randint
rawstr = ''.join(mydict.keys())
mystr = ''
for i in range(0, len(rawstr), 2):
    mystr += chr(randint(65,91)) * randint(0,20) # insert between 0 and 20 chars

from time import time

# How many times to run each solution
rep = 10000

print('Running %d times with string length %d and ' \
      'random inserts of lengths 0-20' % (rep, len(mystr)))

# Tor Valamo - too long
#t = time()
#for x in range(rep):
#    for k, v in mydict.items():
#        mystr.replace(k, v)
#print('%-30s' % 'Tor fixed & variable dict', time()-t)

from re import sub, compile, escape

# Peter Hansen
t = time()
for x in range(rep):
    sub(r'(&[a-zA-Z])', r'%(\1)s', mystr) % mydict
print('%-30s' % 'Peter fixed & variable dict', time()-t)

# Peter 2
def dictsub(m):
    return mydict[m.group()]

t = time()
for x in range(rep):
    sub(r'(&[a-zA-Z])', dictsub, mystr)
print('%-30s' % 'Peter fixed dict', time()-t)

# Claudiu - too long
#def multiple_replace(dict, text): 
#    # Create a regular expression  from the dictionary keys
#    regex = compile("(%s)" % "|".join(map(escape, dict.keys())))
#
#    # For each match, look-up corresponding value in dictionary
#    return regex.sub(lambda mo: dict[mo.string[mo.start():mo.end()]], text)
#
#t = time()
#for x in range(rep):
#    multiple_replace(mydict, mystr)
#print('%-30s' % 'Claudio variable dict', time()-t)

# Claudiu - Precompiled
regex = compile("(%s)" % "|".join(map(escape, mydict.keys())))

t = time()
for x in range(rep):
    regex.sub(lambda mo: mydict[mo.string[mo.start():mo.end()]], mystr)
print('%-30s' % 'Claudio fixed dict', time()-t)

# Separate setup for Andrew and gnibbler optimized dict
mydict = dict((k[1], v) for k, v in mydict.items())

# Andrew Y - variable dict
def mysubst(somestr, somedict):
  subs = somestr.split("&")
  return subs[0] + "".join(map(lambda arg: somedict[arg[0:1]] + arg[1:], subs[1:]))

def mysubst2(somestr, somedict):
  subs = somestr.split("&")
  return subs[0].join(map(lambda arg: somedict[arg[0:1]] + arg[1:], subs[1:]))

t = time()
for x in range(rep):
    mysubst(mystr, mydict)
print('%-30s' % 'Andrew Y variable dict', time()-t)
t = time()
for x in range(rep):
    mysubst2(mystr, mydict)
print('%-30s' % 'Andrew Y variable dict 2', time()-t)

# Andrew Y - fixed
def repl(s):
  return mydict[s[0:1]] + s[1:]

t = time()
for x in range(rep):
    subs = mystr.split("&")
    res = subs[0] + "".join(map(repl, subs[1:]))
print('%-30s' % 'Andrew Y fixed dict', time()-t)

# gnibbler
t = time()
for x in range(rep):
    myparts = mystr.split("&")
    myparts[1:]=[mydict[x[0]]+x[1:] for x in myparts[1:]]
    "".join(myparts)
print('%-30s' % 'gnibbler fixed & variable dict', time()-t)

Результаты:

Running 10000 times with string length 9491 and random inserts of lengths 0-20
Tor fixed & variable dict      0.0 # disqualified 329 secs
Peter fixed & variable dict    2.07799983025
Peter fixed dict               1.53100013733 
Claudio variable dict          0.0 # disqualified, 37 secs
Claudio fixed dict             1.5
Andrew Y variable dict         0.578000068665
Andrew Y variable dict 2       0.56299996376
Andrew Y fixed dict            0.56200003624
gnibbler fixed & variable dict 0.530999898911

(** Обратите внимание, что в коде gnibbler используется другой словарь, в котором ключи не содержат «&». Код Эндрю также использует этот альтернативный словарь, но это не имеет большого значения, может быть, всего лишь ускорение в 0,01 раза.)

Попробуйте это, используя подстановку регулярных выражений и стандартное форматирование строк:

# using your stated values for str and dict:
>>> import re
>>> str = re.sub(r'(&[a-zA-Z])', r'%(\1)s', str)
>>> str % dict
'The \x1b[0;30mquick \x1b[0;31mbrown \x1b[0;32mfox \x1b[0;33mjumps over the \x1b[0;34mlazy dog'

Вызов re.sub() заменяет все последовательности амперсанда, за которыми следует одна буква, шаблоном %(..)s, содержащим тот же шаблон.

Форматирование % использует преимущество форматирования строк, которое может использовать словарь для указания замены, а не более часто встречающиеся позиционные аргументы.

В качестве альтернативы это можно сделать прямо в re.sub, используя обратный вызов:

>>> import re
>>> def dictsub(m):
>>>    return dict[m.group()]
>>> str = re.sub(r'(&[a-zA-Z])', dictsub, str)

На этот раз я использую замыкание для ссылки на словарь из функции обратного вызова. Этот подход может дать вам немного больше гибкости. Например, вы можете использовать что-то вроде dict.get(m.group(), '??'), чтобы избежать возникновения исключений, если у вас есть строки с нераспознанными последовательностями кода.

(Кстати, и "dict", и "str" ​​являются встроенными функциями, и у вас возникнут проблемы, если вы будете часто использовать эти имена в своем собственном коде. На всякий случай, если вы этого не знали. Они подходят для такой вопрос конечно))

Редактировать: я решил проверить тестовый код Tor и пришел к выводу, что он далеко не репрезентативен и на самом деле содержит ошибки. Сгенерированная строка даже не содержит амперсандов (!). Пересмотренный код ниже создает репрезентативный словарь и строку, аналогичную примерам входных данных OP.

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

from time import time
import string
import random
import re

random.seed(1919096)  # ensure consistent runs

# build dictionary with 40 mappings, representative of original question
mydict = dict(('&' + random.choice(string.letters), '\x1b[0;%sm' % (30+i)) for i in range(40))
# build simulated input, with mix of text, spaces, ampersands in reasonable proportions
letters = string.letters + ' ' * 12 + '&' * 6
mystr = ''.join(random.choice(letters) for i in range(1000))

# How many times to run each solution
rep = 10000

print('Running %d times with string length %d and %d ampersands'
    % (rep, len(mystr), mystr.count('&')))

# Tor Valamo
# fixed from Tor's test, so it actually builds up the final string properly
t = time()
for x in range(rep):
    output = mystr
    for k, v in mydict.items():
        output = output.replace(k, v)
print('%-30s' % 'Tor fixed & variable dict', time() - t)
# capture "known good" output as expected, to verify others
expected = output

# Peter Hansen

# build charset to use in regex for safe dict lookup
charset = ''.join(x[1] for x in mydict.keys())
# grab reference to method on regex, for speed
patsub = re.compile(r'(&[%s])' % charset).sub

t = time()
for x in range(rep):
    output = patsub(r'%(\1)s', mystr) % mydict
print('%-30s' % 'Peter fixed & variable dict', time()-t)
assert output == expected

# Peter 2
def dictsub(m):
    return mydict[m.group()]

t = time()
for x in range(rep):
    output = patsub(dictsub, mystr)
print('%-30s' % 'Peter fixed dict', time() - t)
assert output == expected

# Peter 3 - freaky generator version, to avoid function call overhead
def dictsub(d):
    m = yield None
    while 1:
        m = yield d[m.group()]

dictsub = dictsub(mydict).send
dictsub(None)   # "prime" it
t = time()
for x in range(rep):
    output = patsub(dictsub, mystr)
print('%-30s' % 'Peter generator', time() - t)
assert output == expected

# Claudiu - Precompiled
regex_sub = re.compile("(%s)" % "|".join(mydict.keys())).sub

t = time()
for x in range(rep):
    output = regex_sub(lambda mo: mydict[mo.string[mo.start():mo.end()]], mystr)
print('%-30s' % 'Claudio fixed dict', time() - t)
assert output == expected

Я забыл включить результаты тестов раньше:

    Running 10000 times with string length 1000 and 96 ampersands
    ('Tor fixed & variable dict     ', 2.9890000820159912)
    ('Peter fixed & variable dict   ', 2.6659998893737793)
    ('Peter fixed dict              ', 1.0920000076293945)
    ('Peter generator               ', 1.0460000038146973)
    ('Claudio fixed dict            ', 1.562000036239624)

Кроме того, фрагменты входов и правильный вывод:

mystr = 'lTEQDMAPvksk k&z Txp vrnhQ GHaO&GNFY&&a...'
mydict = {'&p': '\x1b[0;37m', '&q': '\x1b[0;66m', '&v': ...}
output = 'lTEQDMAPvksk k←[0;57m Txp vrnhQ GHaO←[0;67mNFY&&a P...'

Сравнивая с тем, что я видел в выводе тестового кода Tor:

mystr = 'VVVVVVVPPPPPPPPPPPPPPPXXXXXXXXYYYFFFFFFFFFFFFEEEEEEEEEEE...'
mydict = {'&p': '112', '&q': '113', '&r': '114', '&s': '115', ...}
output = # same as mystr since there were no ampersands inside

Если вы действительно хотите углубиться в тему, взгляните на это: http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

Очевидное решение путем перебора словаря и замены каждого элемента в строке занимает O(n*m) времени, где n — размер словаря, m — длина строки.

Принимая во внимание, что алгоритм Ахо-Корасика находит все записи словаря в O(n+m+f), где f — количество найденных элементов.

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

str = "The &yquick &cbrown &bfox &Yjumps over the &ulazy dog"

dict = {"&y":"\033[0;30m",
        "&c":"\033[0;31m",
        "&b":"\033[0;32m",
        "&Y":"\033[0;33m",
        "&u":"\033[0;34m"}

def rep(s):
  return dict["&"+s[0:1]] + s[1:]

subs = str.split("&")
res = subs[0] + "".join(map(rep, subs[1:]))

print res

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

Конечно, как это часто бывает с проблемами производительности, правильно выбрать время для различных подходов к вашему типичному (а также наихудшему) набору данных и сравнить их.

РЕДАКТИРОВАТЬ: поместите его в отдельную функцию для работы с произвольным словарем:

def mysubst(somestr, somedict):
  subs = somestr.split("&")
  return subs[0] + "".join(map(lambda arg: somedict["&" + arg[0:1]] + arg[1:], subs[1:]))

РЕДАКТИРОВАТЬ2: избавиться от ненужной конкатенации, кажется, все еще немного быстрее, чем предыдущая на многих итерациях.

def mysubst(somestr, somedict):
  subs = somestr.split("&")
  return subs[0].join(map(lambda arg: somedict["&" + arg[0:1]] + arg[1:], subs[1:]))

Вот подход расширений C для python

const char *dvals[]={
    //"0-64
    "","","","","","","","","","",
    "","","","","","","","","","",
    "","","","","","","","","","",
    "","","","","","","","","","",
    "","","","","","","","","","",
    "","","","","","","","","","",
    "","","","","",
    //A-Z
    "","","","","",
    "","","","","",
    "","","","","",
    "","","","","",
    "","","","","33",
    "",
    //
    "","","","","","",
    //a-z
    "","32","31","","",
    "","","","","",
    "","","","","",
    "","","","","",
    "34","","","","30",
    ""
};

int dsub(char*d,char*s){
    char *ofs=d;
    do{
        if(*s=='&' && s[1]<='z' && *dvals[s[1]]){

            //\033[0;
            *d++='\\',*d++='0',*d++='3',*d++='3',*d++='[',*d++='0',*d++=';';

            //consider as fixed 2 digits
            *d++=dvals[s[1]][0];
            *d++=dvals[s[1]][1];

            *d++='m';

            s++; //skip

        //non &,invalid, unused (&) ampersand sequences will go here.
        }else *d++=*s;

    }while(*s++);

    return d-ofs-1;
}

Коды Python, которые я тестировал

from mylib import *
import time

start=time.time()

instr="The &yquick &cbrown &bfox &Yjumps over the &ulazy dog, skip &Unknown.\n"*100000
x=dsub(instr)

end=time.time()

print "time taken",end-start,",input str length",len(x)
print "first few lines"
print x[:1100]

Результаты

time taken 0.140000104904 ,input str length 11000000
first few lines
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.

Предполагается, что он может работать со скоростью O(n), и потребовалось всего 160 мс (в среднем) для строки 11 МБ в My Mobile Celeron 1.6. ГГц ПК

Он также будет пропускать неизвестные символы как есть, например, &Unknown будет возвращаться как есть.

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

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

def multiple_replace(dict, text): 
    # Create a regular expression  from the dictionary keys
    regex = re.compile("(%s)" % "|".join(map(re.escape, dict.keys())))

    # For each match, look-up corresponding value in dictionary
    return regex.sub(lambda mo: dict[mo.string[mo.start():mo.end()]], text)

print multiple_replace(dict, str)

Общее решение для определения правил замены — использовать подстановку регулярных выражений с помощью функции для предоставления карты (см. re.sub()).

import re

str = "The &yquick &cbrown &bfox &Yjumps over the &ulazy dog"

dict = {"&y":"\033[0;30m",
        "&c":"\033[0;31m",
        "&b":"\033[0;32m",
        "&Y":"\033[0;33m",
        "&u":"\033[0;34m"}

def programmaticReplacement( match ):
    return dict[ match.group( 1 ) ]

colorstring = re.sub( '(\&.)', programmaticReplacement, str )

Это особенно удобно для нетривиальных замен (например, для всего, что требует математических операций для создания замены).

Вот версия с использованием split/join

mydict = {"y":"\033[0;30m",
          "c":"\033[0;31m",
          "b":"\033[0;32m",
          "Y":"\033[0;33m",
          "u":"\033[0;34m"}
mystr = "The &yquick &cbrown &bfox &Yjumps over the &ulazy dog"

myparts = mystr.split("&")
myparts[1:]=[mydict[x[0]]+x[1:] for x in myparts[1:]]
print "".join(myparts)

Если есть амперсанды с неверными кодами, вы можете использовать это, чтобы сохранить их.

myparts[1:]=[mydict.get(x[0],"&"+x[0])+x[1:] for x in myparts[1:]]

Питер Хансен указал, что это не работает, когда есть двойной амперсанд. В этом случае используйте эту версию

mystr = "The &yquick &cbrown &bfox &Yjumps over the &&ulazy dog"
myparts = mystr.split("&")
myparts[1:]=[mydict.get(x[:1],"&"+x[:1])+x[1:] for x in myparts[1:]]
print "".join(myparts)

Не уверен и в скорости этого решения, но вы можете просто прокрутить свой словарь и неоднократно вызывать встроенный

str.replace(old, new)

Это может работать прилично, если исходная строка не слишком длинная, но очевидно, что она пострадает, когда строка станет длиннее.

Проблема с такой массовой заменой в Python заключается в неизменности строк: каждый раз, когда вы заменяете один элемент в строке, вся новая строка будет снова и снова перераспределяться из кучи.

Поэтому, если вам нужно самое быстрое решение, вам нужно либо использовать изменяемый контейнер (например, список), либо написать этот механизм на простом C (или лучше на Pyrex или Cython). В любом случае я бы предложил написать простой синтаксический анализатор на основе простого конечного автомата и подавать символы вашей строки один за другим.

Предлагаемые решения, основанные на регулярных выражениях, работают аналогичным образом, потому что регулярные выражения работают с использованием fsm за кулисами.

Поскольку кто-то упомянул об использовании простого синтаксического анализатора, я подумал, что приготовлю его с помощью pyparsing. Используя метод transformString pyparsing, pyparsing внутренне сканирует исходную строку и создает список совпадающего текста и промежуточного текста. Когда все будет сделано, transformString затем ''.join's этот список, так что нет проблем с производительностью при построении строк с приращением. (Действие синтаксического анализа, определенное для ANSIreplacer, выполняет преобразование совпадающих символов &_ в желаемую управляющую последовательность и заменяет совпадающий текст выходными данными действия синтаксического анализа. Поскольку только совпадающие последовательности будут удовлетворять выражению синтаксического анализатора, нет необходимости в действие parse для обработки неопределенных последовательностей &_.)

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

from pyparsing import FollowedBy, oneOf

escLookup = {"&y":"\033[0;30m",
            "&c":"\033[0;31m",
            "&b":"\033[0;32m",
            "&Y":"\033[0;33m",
            "&u":"\033[0;34m"}

# make a single expression that will look for a leading '&', then try to 
# match each of the escape expressions
ANSIreplacer = FollowedBy('&') + oneOf(escLookup.keys())

# add a parse action that will replace the matched text with the 
# corresponding ANSI sequence
ANSIreplacer.setParseAction(lambda toks: escLookup[toks[0]])

# now use the replacer to transform the test string; throw in some extra
# ampersands to show what happens with non-matching sequences
src = "The &yquick &cbrown &bfox &Yjumps over the &ulazy dog & &Zjumps back"
out = ANSIreplacer.transformString(src)
print repr(out)

Отпечатки:

'The \x1b[0;30mquick \x1b[0;31mbrown \x1b[0;32mfox \x1b[0;33mjumps over 
 the \x1b[0;34mlazy dog & &Zjumps back'

Это, конечно, не выиграет никаких конкурсов производительности, но если ваша разметка начнет усложняться, то наличие основы синтаксического анализатора облегчит ее расширение.

попробуй это

tr.replace("&y",dict["&y"])

tr.replace("&c",dict["&c"])

tr.replace("&b",dict["&b"])

tr.replace("&Y",dict["&Y"])

tr.replace("&u",dict["&u"])