这是一个创建于 1704 天前的主题，其中的信息可能已经有所发展或是发生改变。
给出一个二维 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 秒多了。
后来想了半天，把每一行转成字符串，删掉里面所有的逗号和空格，然后正则寻找边界，稍微快了一点，不过还是将近一秒。
有人知道怎么样可以尽可能快的做这种查找吗？
比如((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 秒多了。
后来想了半天，把每一行转成字符串，删掉里面所有的逗号和空格，然后正则寻找边界，稍微快了一点，不过还是将近一秒。
有人知道怎么样可以尽可能快的做这种查找吗？
 | 1 alazysun 2021-02-18 12:43:06 +08:00 都要尽可能快了。。不直接上 C/C++？ |
 | 2 goodboy95 OP @alazysun 因为一些要求，这次必须 python，这个不是输出实际生产力的项目，所以也不要想着可以跟上头讨论了 |
 | 3 ungrown 2021-02-18 15:27:04 +08:00 遍历也慢不到哪里去了，正则之所以快是因为自带的正则库已经是经过性能优化之后的了，没猜错的话里面的模块都是 C 语言写的。 |
 | 4 imn1 2021-02-18 17:05:46 +08:00 本来想写位运算的，看到 1000 个，pass 难点在位置，只找连续 1 比较容易 用 itertools.compress + range，可以只保留值为 1 的序号 官网有个 itertools.group 找连续递增子串的例子 两个结合，因为序号连续递增就是连续 1 的位置 耗时就不知道了，没数据测试，直觉不一定比 re 快 |
| 5 goodboy95 OP @imn1 哎，要是 groupby 能提供起始位置的话就舒服多了，可惜没给…… 本来测试 groupby 完了 sum 也是可以快一些的，可惜矩阵里存在 0，没法用 sum 定位…… 现在好怀念 MySQL 里面的 groupby，一 count 了事，python 转 list 之后 count 就没有速度优势了。 |
 | 7 bytesfold 2021-02-18 18:44:29 +08:00 ```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) ``` |
| 8 bytesfold 2021-02-18 18:44:59 +08:00 你再改改，感觉能满足你的需求 |
| 9 goodboy95 OP @bytesfold 抱歉，我这边可能有点跟不上思路，为什么要把二维矩阵展成一维，是说展成一维之后用正则一次查找会快吗？不过我这边试了一下，速度实际上没什么差别。 |
 | 10 lpts007 2021-02-18 20:41:39 +08:00 via Android 最好是把测试数据、测试结果、cpu 贴出来，这样大家也能试试。 |
| 11 goodboy95 OP |
 | 12 xupefei 2021-02-18 21:58:09 +08:00 via iPhone 竖向连续的 1 算吗？如果算的话就用 bfs 或 dfs，复杂度 O(mn)。 不算的话也无所谓，反正就是个只考横向的 bfs 或 dfs 。 |
 | 13 hsfzxjy 2021-02-18 23:23:41 +08:00  1 你网盘给的代码中转成 str 没必要，bytes 就足够了 ''.join(map(str, mapData[i])) -> bytes(maData[i]) '0+' -> b'\x00+' 另外一定要 tuple of tuple 这种结构吗？能不能一开始就用别的方式储存？ |
| 14 hsfzxjy 2021-02-18 23:24:50 +08:00 @hsfzxjy #13 打错了是 str(mapData[i]).replace(", ", "") -> bytes(mapData[i]) |
 | 15 renmu123 2021-02-18 23:33:44 +08:00 via Android 我觉得难，你不遍历一遍就不知道有哪些数字是 1，这样就起码得遍历一遍，我觉得只能在遍历的时候做做优化，比如双指针跳过一些判断 |
| 16 goodboy95 OP @hsfzxjy 太感谢了，bytes 确实有不少提速。 规则是必须 tuple of tuple，这个确实没法改。 |
| 17 hsfzxjy 2021-02-19 10:19:51 +08:00 1 @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 |
| 18 goodboy95 OP @hsfzxjy 现在才发现 python 判断 true，false 比判断是否等于 0 要快一些，非常感谢。 顺便问一下另外一个问题： 比如 spanA 和 spanB，格式都是(4,10)这样的一个 tuple，代表从 4 到 10 的一个区间，我需要判断两个区间是否相交。 我目前的方法是 spanA[0] <= spanB[1] and spanA[1] >= spanB[0]，不过总感觉略慢。 不知道 python 里面，对这种比较有没有什么优化方式 |
| 19 hsfzxjy 2021-02-19 14:13:29 +08:00 1 |
 | 20 iqhy 2021-02-19 16:53:20 +08:00 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 这样遍历快一点 |
Select Language