请教 Python 快速寻找连续 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

  这样遍历快一点