La masse de la chaîne de remplacer en python?

Question

Dire que j'ai une chaîne qui ressemble à ceci:

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

Vous remarquerez un grand nombre d'endroits de la chaîne où il y a une esperluette, suivie par un caractère (comme "&y" et "&c"). J'ai besoin de remplacer ces caractères avec une valeur appropriée que j'ai dans un dictionnaire, comme suit:

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

Quel est le moyen le plus rapide pour ce faire? J'ai pu trouver manuellement tous les esperluettes, puis la boucle à travers le dictionnaire pour les changer, mais qui semble lent. Faire un tas de regex remplace semble lent (je vais avoir un dictionnaire d'environ 30 à 40 paires dans mon code).

Toutes les suggestions sont appréciés, merci.

Edit:

Comme cela a été souligné dans les commentaires à travers cette question, mon dictionnaire est défini avant l'exécution, et ne changera jamais, au cours du cycle de vie des applications. C'est une liste de séquences d'échappement ANSI, et aura environ 40 éléments. Ma moyenne de la longueur de la chaîne à comparer sera d'environ 500 caractères, mais il y aura ceux qui sont jusqu'à 5000 caractères (même si ce sera rare). Je suis également à l'aide de Python 2.6 actuellement.

Edit #2 J'ai accepté Tor Valamos réponse comme correcte, car il a non seulement donné une solution valable (même si ce n'était pas la meilleure solution), mais a tous les autres en compte et a fait un travail énorme de comparer tous les d'entre eux. La réponse est l'un des meilleurs, la plupart des réponses utiles que j'ai jamais rencontré sur StackOverflow. Bravo à vous.

Answer 1

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

J'ai pris la liberté de la comparaison de quelques solutions:

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

Les résultats en 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

Les deux claudiu et andrew solutions continué en 0, donc j'ai dû passer à 10 000 pistes.

Je l'ai couru en Python 3 (à cause de l'unicode) avec le remplacement de caractères à partir de 39 à 1024 (38 est commercial, donc je n'ai pas envie de l'inclure). La longueur de la chaîne jusqu'à 10 000 dont environ 980 remplacements avec des variable aléatoire insertions de la longueur de 0 à 20. Les valeurs unicode à partir de 39 à 1024 provoque des caractères à la fois 1 et 2 octets de longueur, ce qui pourrait affecter certaines solutions.

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)

Résultats:

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

(** Note que gnibbler code utilise un autre dict, où les clés n'ont pas le '&' inclus. Andrew code utilise aussi cette autre dict, mais il n'a pas beaucoup de différence, peut-être seulement 0,01 x speedup.)

Answer 2

Essayez ceci, en faisant usage de l'expression régulière de substitution, et de la norme de chaîne de formatage:

# 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'

La re.sub() appel remplace toutes les séquences de commercial suivi par simple lettre avec le motif %(..)contenant le même modèle.

L' % mise en forme bénéficie d'une fonction de mise en forme de chaîne qui peut prendre un dictionnaire pour spécifier la substitution, plutôt que les plus fréquentes des arguments de position.

Une alternative peut le faire directement dans le re.sous, à l'aide d'un rappel:

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

Cette fois, je suis à l'aide d'une fermeture de référence, le dictionnaire de l'intérieur de la fonction de rappel. Cette approche pourrait vous donner un peu plus de souplesse. Par exemple, vous pouvez utiliser quelque chose comme dict.get(m.group(), '??') pour éviter de déclencher des exceptions si vous avait des chaînes non reconnu de séquences de code.

(En passant, les deux "dict" et "str" sont des fonctions internes, et vous serez d'avoir des ennuis si vous utiliser ces noms dans votre propre code beaucoup. Juste au cas où vous ne saviez pas que. Ils vont bien pour une question comme ça, bien sûr.)

Edit: j'ai décidé de vérifier Tor du code de test, et a conclu que c'est loin d'être représentatif, et, en fait, buggy. La chaîne générée n'ont même pas les esperluettes en elle (!). La version révisée du code ci-dessous génère un représentant du dictionnaire et de la ficelle, similaires à la discussion de l'exemple d'entrées.

Je voulais aussi vérifier que chaque algorithme est le résultat était le même. Ci-dessous est une version révisée du programme de test, avec seulement de Tor, de la mine, et Claudiu du code -- parce que les autres étaient de rupture sur l'échantillon d'entrée. (Je pense qu'ils sont tous fragiles, à moins que le dictionnaire des cartes, fondamentalement, tous les possibles esperluette séquences, qui Tor du code de test a été fait.) Ce bien de graines le générateur de nombre aléatoire de sorte que chaque course est la même. Enfin, j'ai ajouté une variation mineure à l'aide d'un générateur qui permet d'éviter certaines d'appel de fonction, les frais généraux, d'un mineur, l'amélioration de la performance.

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

J'ai oublié d'inclure les résultats d'un benchmark avant:

 L'exécution de 10000 fois avec de la ficelle de longueur 1000 et 96 arobases
 ('Tor fixe & variable dict ', 2.9890000820159912)
 (Peter fixe & variable dict ', 2.6659998893737793)
 (Peter fixe dict ', 1.0920000076293945)
 (Peter générateur", 1.0460000038146973)
 ('Claudio fixe dict ', 1.562000036239624)

Aussi, des extraits de ses entrées et de sortie correct:

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...'

En comparant avec ce que j'ai vu de Tor du test de sortie de code:

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

Answer 3

Si vous voulez vraiment creuser le sujet, jetez un oeil à ceci: http://en.wikipedia.org/wiki/Aho-Corasick%5Falgorithm

La solution la plus évidente par itération sur le dictionnaire et le remplacement de chaque élément de la chaîne de caractères O(n*m) du temps, où n est la taille du dictionnaire, m est la longueur de la chaîne.

Alors que l'Aho-Corasick-Algorithme trouve toutes les entrées du dictionnaire en O(n+m+f) où f est le nombre d'éléments trouvés.

Answer 4

Si le nombre de clés dans la liste est grande, et le nombre d'occurences de la chaîne est faible (et la plupart du temps zéro), vous pouvez effectuer une itération sur les occurences de l'esperluette dans la chaîne, et d'utiliser le dictionnaire gérés par le premier caractère de la sous-chaînes. Je n'ai pas de code souvent en python de sorte que le style peut être un peu hors sujet, mais voici mon point de vue à elle:

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

Bien sûr, il est question de ce qui se passe quand il y a une esperluette qui est à venir à partir de la chaîne elle-même, vous avez besoin de s'échapper d'une certaine façon avant de se nourrir grâce à ce processus, et puis ne pas encoder la suite de ce processus.

Bien sûr, comme c'est assez bien d'habitude avec les problèmes de performances, le calendrier, les différentes approches sur votre typique (et aussi pour le pire des cas) données et de les comparer est une bonne chose à faire.

EDIT: la placer dans une fonction séparée de travailler avec arbitraires dictionnaire:

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

EDIT2: se débarrasser de l'inutile concaténation, semble toujours être un peu plus rapide que la précédente sur le nombre d'itérations.

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

Answer 5

Ici, c'est le C des Extensions de l'Approche de 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 codes que j'ai testé

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]

Résultats

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.

Son suppose de pouvoir s'exécuter en O(n), et A seulement pris de 160 ms (avg) pour 11 MO chaîne dans Mon Mobile Celeron 1.6 GHz PC

Il sera également ignorer les caractères inconnus comme, par exemple &Unknown sera de retour comme c'est

Laissez-moi savoir Si vous avez un problème avec la compilation, des bugs, etc...