检查列表是否为有效的块序列

问题描述

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

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([]))

---

解决方案

如何，从列表创建iter并在该ITER上向前搜索，直到找到next匹配的元素。请注意，如果None可以是列表的元素，则此操作可能失败；那么您应该定义并比较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元素的问题。与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)

每种方式，每个元素只被访问一次，原始列表不会更改，几乎没有额外的空间，而且它甚至在一定程度上易于阅读和理解。

---

这从来不是速度的问题，而是无论如何：以下是不同解决方案(以及更多变体)的一些基准测试，在Python3.8.10上运行问题中的测试用例以及两个包含1000个整数的随机列表，一个有效，一个无效，10,000次：

# 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解决方案有些滞后，但在使用generator with condition时与next一样快(或慢)，但仍比使用普通for循环时慢。 只有很短的测试列表，这就有点不同了：在这里，使用一个迭代器和for-for-else和for-in的解决方案在相当程度上是最快的。