你应该如何从一个表中回顾过去的项目？

Question

当我试图回答一个关于代码评审的问题时，我意识到我的解决方案是有缺陷的。代码通过了为其创建的第一个测试，但是第二个测试证明它并不总是有效的。某些序列可以部分匹配，然后阻止正确的匹配成功。你知道吗

#! /usr/bin/env python3
def main():
    """Source: http://codereview.stackexchange.com/questions/149867"""
    print('PASS' if contains((0, 1, 3, 4, 5), (1, 3, 4)) else 'FAIL')
    print('PASS' if contains((1, 2, 1, 2, 1, 3), (1, 2, 1, 3)) else 'FAIL')


def contains(iterable, sequence):
    """Determine if sequence can be found in iterable and return the result."""
    offset, length = 0, len(sequence)
    for item in iterable:
        if item == sequence[offset]:
            offset += 1
            if offset == length:
                return True
        elif offset:
            offset = 0
    return False


if __name__ == '__main__':
    main()

如何修改contains函数，使其能够正确地与任何给定的iterable一起工作？你知道吗

Answer 1

原始（断开的）解决方案的问题是，如果出现部分匹配，然后出现故障，则算法应该回退到iterable数据流中较早的位置。有些语言允许重绕迭代器，但Python不允许重绕，因为迭代器的长度是无限的。通过引入具有历史记录的迭代器包装器，原始代码只需稍加修改。你知道吗

#! /usr/bin/env python3
import collections


def main():
    """Source: http://codereview.stackexchange.com/questions/149867"""
    print('PASS' if contains((0, 1, 3, 4, 5), (1, 3, 4)) else 'FAIL')
    print('PASS' if contains((1, 2, 1, 2, 1, 3), (1, 2, 1, 3)) else 'FAIL')
    print('PASS' if not contains((1, 2, 1), (1, 2, 1, 3)) else 'FAIL')


def contains(iterable, sequence):
    """Determine if sequence can be found in iterable and return the result."""
    offset, length = 0, len(sequence)
    iterator = IteratorWithHistory(iterable, length - 1)
    for item in iterator:
        if item == sequence[offset]:
            offset += 1
            if offset == length:
                return True
        elif offset:
            iterator.rewind(offset)
            offset = 0
    return False


class IteratorWithHistory:

    """IteratorWithHistory(iterable, history_size) -> New Instance"""

    def __init__(self, iterable, history_size):
        """Initialize a new instance of the class."""
        self.__iterator = iter(iterable)
        self.__history = collections.deque((), history_size)
        self.__offset = 0

    def __iter__(self):
        """Return the iterator object itself."""
        return self

    def __next__(self):
        """Return the next item from the container."""
        if self.__offset:
            item = self.__history[-self.__offset]
            self.__offset -= 1
        else:
            item = next(self.__iterator)
            self.__history.append(item)
        return item

    def rewind(self, offset):
        """Rewind the iterator back by the offset value."""
        if not isinstance(offset, int):
            raise TypeError('offset must be of type int')
        if offset < 1:
            raise ValueError('offset must be a positive number')
        new_offset = self.__offset + offset
        if new_offset > len(self.__history):
            raise ValueError('cannot rewind that far back')
        self.__offset = new_offset


if __name__ == '__main__':
    main()