时间戳

首页 > 解决方案 > 检查列表是否是有效的块序列

python - 检查列表是否是有效的块序列

问题描述

我想检查一个列表是否是一个有效的块序列，其中每个块以某个值开始，并以下一次出现的相同值结束。例如，这是三个块的有效序列：

lst = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]
       \___________/  \_____/  \_______________________/

这是一个无效的：

lst = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]
       \___________/  \_____/  \_____ ... missing the 2 to end the chunk

我有一个解决方案，但它很糟糕。你看到更好的东西了吗？

def is_valid(lst):
    while lst:
        start = lst.pop(0)
        if start not in lst:
            return False
        while lst[0] != start:
            lst.pop(0)
        lst.remove(start)
    return True

# Tests, should print: True, False, True, False, True
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]))
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]))
print(is_valid(['I', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']))
print(is_valid(['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']))
print(is_valid([]))

标签： pythonlistvalidationsequencechunks

解决方案

怎么样，iter从列表中创建一个并在该迭代上向前搜索，直到next找到匹配的元素。请注意，这可能会失败，因为它None可以是列表的元素；那么您应该定义并与 sentinel 进行比较obj = object()。

def is_valid(lst):
    it = iter(lst)
    for x in it:
        if next((y for y in it if y == x), None) is None:
            return False
    return True

由于我们实际上并不需要返回的值next，我们也可以直接使用any，同时解决default元素的问题。Like next,any将使用迭代器，直到匹配元素（如果有）：

def is_valid(lst):
    it = iter(lst)
    for x in it:
        if not any(y == x for y in it):
            return False
    return True

这可以使用all而不是外for循环进一步缩短：

def is_valid(lst):
    it = iter(lst)
    return all(any(y == x for y in it) for x in it)

这最终可以简化为同样神秘和有趣的：

def is_valid(lst):
    it = iter(lst)
    return all(x in it for x in it)

每种方式，每个元素都被访问一次，原始列表没有改变，几乎没有额外的空间，恕我直言，它甚至有点容易阅读和理解。

这从来都与速度无关，但无论如何：以下是不同解决方案的一些基准测试（以及更多变体），运行问题中的测试用例以及两个包含 1,000 个整数的随机列表，一个有效，一个无效，10,000 次，在 Python 3.8.10 上：

# with long lists             # only short test lists
1.52 is_valid_index           0.22 is_valid_index
3.28 is_valid_next            0.30 is_valid_next
2.78 is_valid_for_for_else    0.13 is_valid_for_for_else
5.26 is_valid_for_any         0.32 is_valid_for_any
5.29 is_valid_all_any         0.38 is_valid_all_any
3.42 is_valid_all_any_if      0.36 is_valid_all_any_if
2.02 is_valid_all_in          0.18 is_valid_all_in
1.97 is_valid_all_in_if       0.17 is_valid_all_in_if
1.87 is_valid_for_in          0.11 is_valid_for_in

当然，都是 O(n)。对于长 1000 个元素列表，使用的解决方案index是最快的，但使用的解决方案x in it也不错。any解决方案有些落后，但与使用带有条件的生成器时一样快（或慢），next但仍比使用普通for循环时慢。只有简短的测试列表，有点不同：在这里，使用一个迭代器的解决方案和for-for-else和for-in最快的相当多。

推荐阅读