Как заменить все экземпляры подпоследовательности в списке в Python?

Question

В настоящее время я использую этот код:

""" 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

Пример:

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

Есть ли более эффективный и / или элегантный способ сделать это?

Answer 1

Для повышения эффективности вы можете использовать алгоритм поиска строки Бойера – Мура при поиске подсписка в списке

код ( кредит )

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

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

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

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

Answer 3

Использование xrange - это простое улучшение, которое ускорит ваш код.xrange возвращает генератор, поэтому улучшения производительности будут особенно заметны для длинных списков.Но даже с вашим действительно коротким тестовым кодом я получаю приличное увеличение.

Используя timeit:

replace_subsequence        0.337936162949, 100000 runs
replace_subsequence_xrange 0.275990962982, 100000 runs

Кроме того, вы должны присвоить переменную len(a) вне цикла, таким образом выне будет продолжать вызывать функцию len().Это также приведет к значительному ускорению.