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

2024-03-28 22:24:40 发布

您现在位置:Python中文网/ 问答频道 /正文

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

#! /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一起工作?你知道吗


Tags: 代码inreturnifmaindefpassiterable
3条回答

没有测试过“所有iterables”,但尝试使用应该有用的习惯用法

编辑了每个评论的新要求:(看起来只是一个更大的范围尝试/除了工作)

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)是低效的

我会完全这样改变我的方法:

#! /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)母亲列表的一部分是否与sequence相同。upper_bound控制所需检查的数量。你知道吗

PS:它们都返回"PASS"。你知道吗

原始(断开的)解决方案的问题是,如果出现部分匹配,然后出现故障,则算法应该回退到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()

相关问题 更多 >