V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
goodboy95
V2EX  ›  问与答

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

  •  
  •   goodboy95 · 2021-02-18 12:27:08 +08:00 · 1296 次点击
    这是一个创建于 1134 天前的主题,其中的信息可能已经有所发展或是发生改变。
    给出一个二维 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 秒多了。
    后来想了半天,把每一行转成字符串,删掉里面所有的逗号和空格,然后正则寻找边界,稍微快了一点,不过还是将近一秒。

    有人知道怎么样可以尽可能快的做这种查找吗?
    20 条回复    2021-02-19 16:53:20 +08:00
    alazysun
        1
    alazysun  
       2021-02-18 12:43:06 +08:00
    都要尽可能快了。。不直接上 C/C++?
    goodboy95
        2
    goodboy95  
    OP
       2021-02-18 13:24:22 +08:00
    @alazysun 因为一些要求,这次必须 python,这个不是输出实际生产力的项目,所以也不要想着可以跟上头讨论了
    ungrown
        3
    ungrown  
       2021-02-18 15:27:04 +08:00
    遍历也慢不到哪里去了,正则之所以快是因为自带的正则库已经是经过性能优化之后的了,没猜错的话里面的模块都是 C 语言写的。
    imn1
        4
    imn1  
       2021-02-18 17:05:46 +08:00
    本来想写位运算的,看到 1000 个,pass

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

    耗时就不知道了,没数据测试,直觉不一定比 re 快
    goodboy95
        5
    goodboy95  
    OP
       2021-02-18 17:41:59 +08:00
    @imn1 哎,要是 groupby 能提供起始位置的话就舒服多了,可惜没给……
    本来测试 groupby 完了 sum 也是可以快一些的,可惜矩阵里存在 0,没法用 sum 定位……
    现在好怀念 MySQL 里面的 groupby,一 count 了事,python 转 list 之后 count 就没有速度优势了。
    goodboy95
        6
    goodboy95  
    OP
       2021-02-18 17:51:23 +08:00
    @imn1 我收回刚刚说的一部分话,sum 完之后如果要做除法也不快
    bytesfold
        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)

    ```
    bytesfold
        8
    bytesfold  
       2021-02-18 18:44:59 +08:00
    你再改改,感觉能满足你的需求
    goodboy95
        9
    goodboy95  
    OP
       2021-02-18 20:15:10 +08:00
    @bytesfold 抱歉,我这边可能有点跟不上思路,为什么要把二维矩阵展成一维,是说展成一维之后用正则一次查找会快吗?不过我这边试了一下,速度实际上没什么差别。
    lpts007
        10
    lpts007  
       2021-02-18 20:41:39 +08:00 via Android
    最好是把测试数据、测试结果、cpu 贴出来,这样大家也能试试。
    goodboy95
        11
    goodboy95  
    OP
       2021-02-18 21:11:37 +08:00
    @lpts007 我的测试用程序和矩阵数据放网盘上了:
    https://cloud.189.cn/t/qYfYFf73qQ7j

    跑 5 次的速度一般就是正则 0.94s ,遍历 1.06s
    xupefei
        12
    xupefei  
       2021-02-18 21:58:09 +08:00 via iPhone
    竖向连续的 1 算吗?如果算的话就用 bfs 或 dfs,复杂度 O(mn)。
    不算的话也无所谓,反正就是个只考横向的 bfs 或 dfs 。
    hsfzxjy
        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 这种结构吗?能不能一开始就用别的方式储存?
    hsfzxjy
        14
    hsfzxjy  
       2021-02-18 23:24:50 +08:00
    @hsfzxjy #13
    打错了是 str(mapData[i]).replace(", ", "") -> bytes(mapData[i])
    renmu123
        15
    renmu123  
       2021-02-18 23:33:44 +08:00 via Android
    我觉得难,你不遍历一遍就不知道有哪些数字是 1,这样就起码得遍历一遍,我觉得只能在遍历的时候做做优化,比如双指针跳过一些判断
    goodboy95
        16
    goodboy95  
    OP
       2021-02-19 09:32:49 +08:00
    @hsfzxjy 太感谢了,bytes 确实有不少提速。
    规则是必须 tuple of tuple,这个确实没法改。
    hsfzxjy
        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
    goodboy95
        18
    goodboy95  
    OP
       2021-02-19 11:54:06 +08:00
    @hsfzxjy 现在才发现 python 判断 true,false 比判断是否等于 0 要快一些,非常感谢。
    顺便问一下另外一个问题:
    比如 spanA 和 spanB,格式都是(4,10)这样的一个 tuple,代表从 4 到 10 的一个区间,我需要判断两个区间是否相交。
    我目前的方法是 spanA[0] <= spanB[1] and spanA[1] >= spanB[0],不过总感觉略慢。
    不知道 python 里面,对这种比较有没有什么优化方式
    hsfzxjy
        19
    hsfzxjy  
       2021-02-19 14:13:29 +08:00   ❤️ 1
    @goodboy95 #18 提前解包会有一定提升

    a, b = spanA
    c, d = spanB
    if a <= d and c <= b: ...
    iqhy
        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

    这样遍历快一点
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3123 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 12:42 · PVG 20:42 · LAX 05:42 · JFK 08:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.