Pythonic的方式来确定是否不为空列表条目是“连续的”
我正在寻找一种方法来轻松地确定是否所有不在列表中的无项目出现在一个连续的切片。 我将使用整数作为非无项目的示例。
例如，列表[None, None, 1, 2, 3, None, None]符合我对连续整数条目的要求。 相反， [1, 2, None, None, 3, None]是不连续的，因为在整数之间没有任何条目。
还有一些例子可以使这一点变得尽可能清楚。
连续 ：
[1, 2, 3, None, None]
[None, None, 1, 2, 3]
[None, 1, 2, 3, None]
不连续 ：
[None, 1, None, 2, None, 3]
[None, None, 1, None, 2, 3]
[1, 2, None, 3, None, None]
我的第一个方法是使用variables来跟踪我们是否遇到了一个None ，还有我们是否碰到过一个int – 这个结果是高度嵌套的，非常难以遵循ifembedded在for循环中的/ else语句。 （在丑陋之上，我承认我没有得到它在任何情况下工作）。
任何人都知道一个更简单的方法来弄清楚，如果在一个列表中没有无项目出现在一个连续的切片？
def contiguous(seq): seq = iter(seq) all(x is None for x in seq) # Burn through any Nones at the beginning any(x is None for x in seq) # and the first group return all(x is None for x in seq) # everthing else (if any) should be None.
这里有几个例子。 您可以使用next(seq)从迭代器中获取下一个项目。 我会在每个标记之后加上一个指向下一个项目的标记
例1：
seq = iter([None, 1, 2, 3, None]) # [None, 1, 2, 3, None] # next^ all(x is None for x in seq) # next^ any(x is None for x in seq) # next^ (off the end) return all(x is None for x in seq) # all returns True for the empty sequence
例2：
seq = iter([1, 2, None, 3, None, None]) # [1, 2, None, 3, None, None] # next^ all(x is None for x in seq) # next^ any(x is None for x in seq) # next^ return all(x is None for x in seq) # all returns False when 3 is encountered
好的，我们itertools.groupby 。
from itertools import groupby def contiguous(seq): return sum(1 for k,g in groupby(seq, lambda x: x is not None) if k) == 1
给
>>> contiguous([1,2,3,None,None]) True >>> contiguous([None, 1,2,3,None]) True >>> contiguous([None, None, 1,2,3]) True >>> contiguous([None, 1, None, 2,3]) False >>> contiguous([None, None, 1, None, 2,3]) False >>> contiguous([None, 1, None, 2, None, 3]) False >>> contiguous([1, 2, None, 3, None, None]) False
[编辑]
由于在评论中似乎有一些讨论，我将解释为什么我喜欢这种方法比其他一些更好。
我们试图找出是否有一个连续的非None对象组
sum(1 for k,g in groupby(seq, lambda x: x is not None) if k)
使用stdlib中用于进行连续组收集的函数来计算连续的非None对象的数量。 一旦我们看到groupby ，我们就会认为“连续的群体”，反之亦然。 从这个意义上讲，这是自我logging。 这基本上是我的目标的定义 。
恕我直言，唯一的弱点是它不会短路，这可能是固定的，但考虑一下后，我仍然更喜欢这个，因为它使用我喜欢的原语 – “计数连续的非无数组” – 我宁愿简单地“告诉我是否有不止一个连续的非无组”。
许多实现最后一个的方法依赖于对这个问题的聪明的观察，比如“如果只有一组连续的非 – 无对象，那么如果我们扫描，直到find第一个非 – 无对象，然后扫描对象直到find第一个非None组，如果存在，那么剩下的是None还是给了我们答案。 （或者类似的东西，这是我的问题的一部分：我必须考虑这个问题。）对于我来说，就像使用关于该问题的“实现细节”来解决问题一样，并且关注可以用来解决问题的属性而不是简单地将问题指定给Python，并让Python来完成工作。
正如俗话所说，我是一只小脑袋，我喜欢避免聪明，正如我的经验，这是一条散布着失败的路线。
与往常一样，每个人的里程数可能会有所不同，当然也可能与他们的聪明程度成正比。
你可以使用像itertools.groupby ：
from itertools import groupby def are_continuous(items): saw_group = False for group, values in groupby(items, lambda i: i is not None): if group: if saw_group: return False else: saw_group = True return True
这将只会重复，直到它看到一个组两次。 我不确定你是否考虑[None, None] ，所以调整到您的需求。
这可能不是最好的方法，但可以查找第一个非None项和最后一个non-None项，然后检查切片的None 。 例如：
def is_continuous(seq): try: first_none_pos = next(i for i,x in enumerate(seq) if x is not None) #need the or None on the next line to handle the case where the last index is `None`. last_none_pos = -next(i for i,x in enumerate(reversed(seq)) if x is not None) or None except StopIteration: #list entirely of `Nones` return False return None not in seq[first_none_pos:last_none_pos] assert is_continuous([1,2,3,None,None]) == True assert is_continuous([None, 1,2,3,None]) == True assert is_continuous([None, None, 1,2,3]) == True assert is_continuous([None, 1, None, 2,3]) == False assert is_continuous([None, None, 1, None, 2,3]) == False assert is_continuous([None, 1, None, 2, None, 3]) == False assert is_continuous([1, 2, None, 3, None, None]) == False
这将适用于任何序列types。
消耗序列元素的自然方法是使用dropwhile ：
from itertools import dropwhile def continuous(seq): return all(x is None for x in dropwhile(lambda x: x is not None, dropwhile(lambda x: x is None, seq)))
我们可以不用嵌套的函数调用来表示这个：
from itertools import dropwhile def continuous(seq): core = dropwhile(lambda x: x is None, seq) remainder = dropwhile(lambda x: x is not None, core) return all(x is None for x in remainder)
一个class轮：
contiguous = lambda l: ' ' not in ''.join('x '[x is None] for x in l).strip()
真正的工作是由stripfunction完成的。 如果在剥离的string中有空格，那么它们不是前导/尾随。 函数的其余部分将列表转换为一个string，每个None都有一个空格。
我做了一些分析，比较@ gnibbler的方法和groupby方法。 @ gnibber的方法一贯更快，尤其是。 为更长的名单。 例如，对于长度为3-100的随机input，我看到大约50％的性能增益，50％的概率包含单个int序列（随机select），否则具有随机值。 下面的testing代码。 我穿插了两种方法（随机select哪一种先进行），以确保任何caching效果都被取消。 基于此，我认为虽然groupby方法更直观，但是如果分析表明这是优化整体代码的重要部分，那么@ gnibber的方法可能是适当的，在这种情况下，应该使用适当的注释指出使用全部/任何消费者迭代器值的情况。
from itertools import groupby import random, time def contiguous1(seq): # gnibber's approach seq = iter(seq) all(x is None for x in seq) # Burn through any Nones at the beginning any(x is None for x in seq) # and the first group return all(x is None for x in seq) # everthing else (if any) should be None. def contiguous2(seq): return sum(1 for k,g in groupby(seq, lambda x: x is not None) if k) == 1 times = {'contiguous1':0,'contiguous2':0} for i in range(400000): n = random.randint(3,100) items = [None] * n if random.randint(0,1): s = random.randint(0,n-1) e = random.randint(0,ns) for i in range(s,e): items[i] = 3 else: for i in range(n): if not random.randint(0,2): items[i] = 3 if random.randint(0,1): funcs = [contiguous1, contiguous2] else: funcs = [contiguous2, contiguous1] for func in funcs: t0 = time.time() func(items) times[func.__name__] += (time.time()-t0) print for f,t in times.items(): print '%10.7f %s' % (t, f)
这是一个由numpy启发的解决scheme。 获取所有非null元素的数组索引。 然后，将每个索引与它后面的索引进行比较。 如果差值大于1，则在非空值之间有空值。 如果没有指数的指数超过一个以上，那就没有差距。
def is_continuous(seq): non_null_indices = [i for i, obj in enumerate(seq) if obj is not None] for i, index in enumerate(non_null_indices[:-1]): if non_null_indices[i+1] - index > 1: return False return True
这个algorithm有一些缺点（从列表中删除项目）。 但这是一个解决scheme。
基本上如果你从开始和结束删除所有连续None 。 如果在列表中发现了一些None ，那么整数不是连续的。
def is_continuous(seq): while seq and seq[0] is None: del seq[0] while seq and seq[-1] is None: del seq[-1] return None not in seq assert is_continuous([1,2,3,None,None]) == True assert is_continuous([None, 1,2,3,None]) == True assert is_continuous([None, None, 1,2,3]) == True assert is_continuous([None, 1, None, 2,3]) == False assert is_continuous([None, None, 1, None, 2,3]) == False assert is_continuous([None, 1, None, 2, None, 3]) == False assert is_continuous([1, 2, None, 3, None, None]) == False
然而，另一个小代码可能会变成邪恶的例子。
我希望strip()方法可用于list 。
我的第一个方法是使用variables来跟踪…
…这最终将嵌套在一个for循环中，嵌套很高，很难遵循if / else语句系列。
没有！ 其实你只需要一个variables。 用你的方法从有限状态机（FSM）的angular度思考这个问题将会产生一个很好的解决scheme。
我们称之为州。 首先， p是0.然后我们开始在这两个状态之间走。
当列表中的所有元素被检查并仍然没有失败时，答案为True 。
一个在dict中编译转换表的版本
def contiguous(s, _D={(0,0):0, (0,1):1, (1,0):2, (1,1):1, (2,0):2, (2,1):3}): p = 0 for x in s: p = _D[p, int(x is not None)] if p >= 3: return False return True
另一个使用if语句的版本：
def contiguous(s): p = 0 for x in s: if x is None and p == 1 or x is not None and (p == 0 or p == 2): p += 1 if p >= 3: return False return True
所以我的观点是使用if和for仍然是pythonic。
更新
我发现了另一种编码FSM的方法。 我们可以将翻译表打包成12位整数。
def contiguous(s): p = 0 for x in s: p = (3684 >> (4*p + 2*(x!=None))) & 3 if p >= 3: return False return True
这里可以通过以下方式获得这个魔法数字3684：
_D[p,a] 3 2 1 2 1 0 p 2 2 1 1 0 0 a 1 0 1 0 1 0 bin(3684) = 0b 11 10 01 10 01 00
可读性不如其他版本，但它更快，因为它避免了字典查找。 第二个版本和这个一样快，但是这个编码思想可以推广到解决更多的问题。
