您应该如何查看可迭代对象中过去的项目？

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 函数，以便它可以正确处理任何给定的可迭代对象？

Answer 1

我会像这样完全改变我的方法：

#! /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."""
    length = len(sequence)
    if length > len(iterable):
        return False
    else:
        upper_bound = len(iterable) - length
        for i in range(upper_bound + 1):
            if iterable[i:i + length] == sequence:
                return True
    return False


if __name__ == '__main__':
    main()

我不是一次检查一个项目，而是检查长度为 len(sequence) 的 mother 列表的一部分是否与 sequence. upper_bound 控制所需的检查次数。

PS: 他们都return "PASS".

Answer 2

原始（损坏的）解决方案的问题在于，如果发生部分匹配然后失败，算法应该倒回到可迭代数据流中较早的位置。一些语言允许它们的迭代器被回绕，但 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()

Answer 3

尚未使用 "all iterables" 进行测试，但已尝试使用应该有效的成语

编辑根据评论的新要求：（看起来只有一个更大的范围 try/except 有效）

a, b = (2, ), (2, 1)
def contains(a, b):      
    # a may be "any iterable", using generator to access
    ag = (i for i in a)    
    try:
    # initialize history with 1st len(b) elements of a
        history = [next(ag) for _ in b] 

        while True: # exits with a match or a StopIteration exception

        # check if all elements in iterables: history, b are equal
        # independent of b container type
        # deMorgan logic in list comprehension to "and" matches, 
        # list comprehension returns [] if every element matches
            if not [1 for j, e in zip(history, b) if j != e]:
                return True
        # advance history contents        
            history.pop(0) 
            history.append(next(ag))

    except StopIteration:
        return False

是的，我读过 pop(0) 效率低下

您应该如何查看可迭代对象中过去的项目？

How should you review past items from an iterable?

python

debugging

iterable

pattern-matching

python-3.x