在二进制列表中查找重复 0 的位置

Question

我有一个从 k = 2 的 k 均值分类返回的二进制列表，我正在尝试 1) 识别给定长度的 0,0,0,... 子串的数量 - 比如说最小长度为 3，并且 2) 确定这些子列表的开始和结束位置，因此在列表中：L = [1,1,0,0,0,0,0,1,1,1,0,0,1,0,0,0]，理想情况下输出为：number = 2 和 start_end_locations = [[2,6],[13,15]]。我正在处理的列表包含数万个元素，因此我需要找到一种计算速度快的方法来执行此操作。我看过许多使用 itertools 中的 groupby 的帖子，但我找不到将它们应用到我的任务中的方法。预先感谢您的建议！

Answer 1

Thanks in advance for your suggestions!

制作一个 regular expression 匹配您的模式：三个或更多零
将列表项连接到字符串
使用re.finditer和匹配对象的start()和end()方法构造一个索引列表

将列表连接到一个字符串可能是最昂贵的部分 - 除非您尝试，否则您不会知道； finditer 应该很快。需要不止一次通过数据，但可能努力编码。

这可能会更好 - 单次遍历列表，但你需要注意逻辑 - 编码更努力。

使用 enumerate
当您找到零时
- 捕获其索引并
- 设置一个标志，表明您正在跟踪零点
当你找到一个
- 如果您正在跟踪零
  - 捕获索引
  - 如果连续零的长度满足您的条件捕获运行个零的开始和结束索引
- 根据需要重置标志和中间变量

与 word 版本有点不同：

def g(a=a):
    y = []
    criteria = 3
    start,end = 0,0
    prev = 1
    for i,n in enumerate(a):
        if not n:        # n is zero
            end = i
            if prev:     # previous item one
                start = i
        else:
            if not prev and end - start + 1 >= criteria:
                y.append((start,end))
        prev = n
    return y

Answer 2

您可以使用 zip() 依次检测 1,0 和 0,1 中断的索引。然后在中断索引上使用 zip() 来形成范围并提取以零开头且至少跨越 3 个位置的范围。

def getZeroStreaks(L,minSize=3):
    breaks = [i for i,(a,b) in enumerate(zip(L,L[1:]),1) if a!=b]
    return [[s,e-1] for s,e in zip([0]+breaks,breaks+[len(L)])
                        if e-s>=minSize and not L[s]]

输出：

L = [1,1,0,0,0,0,0,1,1,1,0,0,1,0,0,0]
print(getZeroStreaks(L))
[[2, 6], [13, 15]]

from timeit import timeit

t = timeit(lambda:getZeroStreaks(L*1000),number=100)/100

print(t) # 0.0018 sec for 16,000 elements

可以推广该函数以查找列表中任意值的条纹：

def getStreaks(L,N=0,minSize=3):
    breaks = [i for i,(a,b) in enumerate(zip(L,L[1:]),1) if (a==N)!=(b==N)]
    return [[s,e-1] for s,e in zip([0]+breaks,breaks+[len(L)])
                         if e-s>=minSize and L[s]==N]

在二进制列表中查找重复 0 的位置

Finding locations of repeated 0 in a binary list

python

binary

group-by

list

itertools