¿Cómo reemplazar todas las instancias de una subsecuencia en una lista en Python?

Question

Actualmente uso de este código:

 
""" Replace all occurrences of subsequence a with b in list l """ 
def replace_subsequence(l,a,b): 
    for i in range(len(l)): 
     if(l[i:i+len(a)] == a): 
      l[i:i+len(a)] = b 
 

Ejemplo:

>>> l = [1,2,3] 
>>> replace_subsequence(l,[2,3],[4]) 
>>> l 
[1, 4] 

¿Existe una manera más eficiente y/o elegante de hacer esto?

Answer 1

para mejorar la eficiencia, se puede utilizar el Boyer–Moore string search algorithm en la búsqueda de una lista secundaria en una lista

Código (credits)

def match(pattern, list): 
    matches = [] 
    m = len(list) 
    n = len(pattern) 

    rightMostIndexes = preprocessForBadCharacterShift(pattern) 

    alignedAt = 0 
    while alignedAt + (n - 1) < m: 

     for indexInPattern in xrange(n-1, -1, -1): 
      indexInlist = alignedAt + indexInPattern 
      x = list[indexInlist] 
      y = pattern[indexInPattern] 

      if indexInlist >= m: 
       break 

      if x != y: 

       r = rightMostIndexes.get(x) 

       if x not in rightMostIndexes: 
        alignedAt = indexInlist + 1 

       else: 
        shift = indexInlist - (alignedAt + r) 
        alignedAt += (shift > 0 and shift or alignedAt + 1) 

       break 
      elif indexInPattern == 0: 
       matches.append(alignedAt) 
       alignedAt += 1 


    return matches 

def preprocessForBadCharacterShift(pattern): 
    map = { } 
    for i in xrange(len(pattern)-1, -1, -1): 
     c = pattern[i] 
     if c not in map: 
      map[c] = i 

    return map 

if __name__ == "__main__": 
    matches = match("ana", "bananas") 
    for integer in matches: 
     print "Match at:", integer 
    print (matches == [1, 3] and "OK" or "Failed") 

    matches = match([1, 2, 3], [0, 1, 2,3 , 4, 5, 6]) 
    for integer in matches: 
     print "list Match at:", integer 
    print (matches) 

Answer 2

Usando xrange es una simple mejora que acelerará su código. xrange devuelve un generador, por lo que las mejoras de rendimiento serán particularmente notables para listas largas. Pero incluso con su código de prueba realmente corto obtengo un aumento decente.

Usando timeit:

replace_subsequence  0.337936162949, 100000 runs 
replace_subsequence_xrange 0.275990962982, 100000 runs 

Además se debe asignar una variable a len(a) fuera del bucle, de esta manera usted no seguir llamando a la función len(). Esto también producirá una aceleración significativa.

Answer 3

Definitivamente no es elegante, pero me pregunto si la conversión a cadenas y el uso de String.Replace se obtienen mejores resultados si sus datos es tan simple como en el ejemplo ...

def strx(l): 
    return str(l).strip('[]') 

def replace_substring(l, a, b): 
    return strx(l).replace(strx(a), strx(b)).split(', ')