请教 Python 快速寻找连续 1 的问题

[goodboy95]

给出一个二维 tuple，里面有一堆 0 和 1，现在需要找到所有连续 1 的起始和终止位置。
比如((1,1,0,1),(0,0,1,1),(0,0,0,0))，我需要知道第一行的(0,1)和(3,3)区间，第二行的(2,3)区间是连续的 1 。
语言是 python3.7，仅可使用标准库，不得借助 cython 之类的东西，也不得用 c 语言自己搞个 dll 然后 python 去调用。

我首先想到的是遍历矩阵然后记录，不过在 python 里面好像有那么一点慢，随机 1000x1000 矩阵跑了 5 次就 1 秒多了。
后来想了半天，把每一行转成字符串，删掉里面所有的逗号和空格，然后正则寻找边界，稍微快了一点，不过还是将近一秒。

有人知道怎么样可以尽可能快的做这种查找吗？

[alazysun]

都要尽可能快了。。不直接上 C/C++？

[goodboy95]

@alazysun 因为一些要求，这次必须 python，这个不是输出实际生产力的项目，所以也不要想着可以跟上头讨论了

[ungrown]

遍历也慢不到哪里去了，正则之所以快是因为自带的正则库已经是经过性能优化之后的了，没猜错的话里面的模块都是 C 语言写的。

[imn1]

本来想写位运算的，看到 1000 个，pass

难点在位置，只找连续 1 比较容易
用 itertools.compress + range，可以只保留值为 1 的序号
官网有个 itertools.group 找连续递增子串的例子
两个结合，因为序号连续递增就是连续 1 的位置

耗时就不知道了，没数据测试，直觉不一定比 re 快

[goodboy95]

@imn1 哎，要是 groupby 能提供起始位置的话就舒服多了，可惜没给……
本来测试 groupby 完了 sum 也是可以快一些的，可惜矩阵里存在 0，没法用 sum 定位……
现在好怀念 MySQL 里面的 groupby，一 count 了事，python 转 list 之后 count 就没有速度优势了。

[goodboy95]

@imn1 我收回刚刚说的一部分话，sum 完之后如果要做除法也不快

[bytesfold]

```markdown
from collections.abc import Iterable


def flatten(items, ignore_types=(str, bytes)):
for x in items:
if isinstance(x, Iterable) and not isinstance(x, ignore_types):
yield from flatten(x)
else:
yield x


items = ((1, 1, 0, 1), (0, 0, 1, 1), (0, 0, 0, 0))
# Produces 1 2 3 4 5 6 7 8
for x in flatten(items):
print(x)

```

[bytesfold]

你再改改，感觉能满足你的需求

[goodboy95]

@bytesfold 抱歉，我这边可能有点跟不上思路，为什么要把二维矩阵展成一维，是说展成一维之后用正则一次查找会快吗？不过我这边试了一下，速度实际上没什么差别。

[lpts007]

最好是把测试数据、测试结果、cpu 贴出来，这样大家也能试试。

[goodboy95]

@lpts007 我的测试用程序和矩阵数据放网盘上了：
https://cloud.189.cn/t/qYfYFf73qQ7j

跑 5 次的速度一般就是正则 0.94s ，遍历 1.06s

[xupefei]

竖向连续的 1 算吗？如果算的话就用 bfs 或 dfs，复杂度 O(mn)。
不算的话也无所谓，反正就是个只考横向的 bfs 或 dfs 。

[hsfzxjy]

你网盘给的代码中转成 str 没必要，bytes 就足够了

''.join(map(str, mapData[i])) -> bytes(mapData[i])
'0+' -> b'\x00+'

另外一定要 tuple of tuple 这种结构吗？能不能一开始就用别的方式储存？

[hsfzxjy]

@hsfzxjy #13
打错了是 str(mapData[i]).replace(", ", "") -> bytes(mapData[i])

[renmu123]

我觉得难，你不遍历一遍就不知道有哪些数字是 1，这样就起码得遍历一遍，我觉得只能在遍历的时候做做优化，比如双指针跳过一些判断

[goodboy95]

@hsfzxjy 太感谢了，bytes 确实有不少提速。
规则是必须 tuple of tuple，这个确实没法改。

[hsfzxjy]

@goodboy95 #16 另外 main2 可以缓存一些中间变量，会有一定的提升：

def main2():
␣␣␣␣iHeight = len(mapData)
␣␣␣␣iWidth = len(mapData[0])
␣␣␣␣res = 0
␣␣␣␣for i in range(0, iHeight):
␣␣␣␣␣␣␣␣isOne = False
␣␣␣␣␣␣␣␣row = mapData[i]
␣␣␣␣␣␣␣␣for j in range(0, iWidth):
␣␣␣␣␣␣␣␣␣␣␣␣ele = row[j]
␣␣␣␣␣␣␣␣␣␣␣␣if not isOne and ele:
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣isOne = True
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣res += j
␣␣␣␣␣␣␣␣␣␣␣␣elif isOne and not ele:
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣isOne = False
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣res += (j - 1)
␣␣␣␣␣␣␣␣if isOne:
␣␣␣␣␣␣␣␣␣␣␣␣res += j


在我这边用 bytes 的 main 是 0.49s ，改进后的 main2 是 0.32s

[goodboy95]

@hsfzxjy 现在才发现 python 判断 true，false 比判断是否等于 0 要快一些，非常感谢。
顺便问一下另外一个问题：
比如 spanA 和 spanB，格式都是(4,10)这样的一个 tuple，代表从 4 到 10 的一个区间，我需要判断两个区间是否相交。
我目前的方法是 spanA[0] <= spanB[1] and spanA[1] >= spanB[0]，不过总感觉略慢。
不知道 python 里面，对这种比较有没有什么优化方式

[hsfzxjy]

@goodboy95 #18 提前解包会有一定提升

a, b = spanA
c, d = spanB
if a <= d and c <= b: ...

[iqhy]

def main2():
....res = 0
....for row in mapData:
........isOne = False
........for j, element in enumerate(row):
............if not isOne and element == 1:
................isOne = True
................res += j
............elif isOne and element == 0:
................isOne = False
................res += (j - 1)
........if isOne:
............res += j

这样遍历快一点