这是一个创建于 1408 天前的主题，其中的信息可能已经有所发展或是发生改变。
给出一个二维 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(mapData[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