python - 在 python 中，如何有效地找到作为较大连续序列子集的连续序列？

Question

我需要找到一个月中发生某种活动的所有日子。活动发生的日子将是连续的。天的顺序可以从一到整个月不等，并且该顺序将每月恰好发生一次。

测试活动是否在任何一天发生并不是一个昂贵的计算，但我想我会用这个问题学习一些新的东西。哪种算法可以最大限度地减少我必须测试的天数？

score 5 · Accepted Answer

没有比遍历序列找到第一个匹配项，然后迭代直到第一个不匹配项更好的了。您可以使用itertools它使它变得美观和可读：

itertools.takewhile(mytest, 
                    itertools.dropwhile(lambda x: not mytest(x), mysequence))

score 2 · Accepted Answer

我认为@isbadawi 建议的线性探针是找到子序列开头的最佳方法。这是因为子序列可能非常短，并且可能位于较大序列中的任何位置。

但是，一旦找到子序列的开头，我们就可以使用二分搜索来找到它的结尾。与进行第二个线性探头相比，这将需要更少的测试，因此它对您来说是一个更好的解决方案。

正如其他人指出的那样，这样做没有太多实际的理由。这是真的有两个原因：你的大序列很短（只有大约 31 个元素），无论如何你仍然需要做至少一个线性探测，所以 big-O 运行时在大序列的长度上仍然是线性的序列，即使我们已经将算法的一部分从线性减少到对数。

score 2 · Accepted Answer

最好的方法取决于您的输入数据结构。如果您的输入数据结构是一个月中每一天的布尔值列表，那么您可以使用以下代码。

start = activity.find(True)
end = activity.rfind(True)

3 回答 3