python - 如何替换 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

Example:

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

是否有更有效和/或更优雅的方法来做到这一点？

Answer 1

为了提高效率，可以使用Boyer–Moore string search algorithm在列表中搜索子列表时

代码 ( 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)