Python 的多层嵌套循环如何优化?

2022-10-31 11:15:57 +08:00
 mmm159357456
result = list()

for x1 in list_a:
    for x2 in list_b:
        for x3 in list_c:
            // 任意层,xn 皆为 f 的必要参数
            _r = f(x1, x2, x3, *args)
            result.append(_r)

众所周知的 python 循环执行慢,如上情形如何优化?

6375 次点击
所在节点    Python
72 条回复
zzl22100048
2022-10-31 11:29:17 +08:00
优化不知道,多层嵌套一般用 `itertools.product`
buyan3303
2022-10-31 11:32:06 +08:00
mmm159357456
2022-10-31 11:39:29 +08:00
@zzl22100048 #1 对于使用 product 是否能提升执行效率呢?我知道这样是减少了嵌套层数
@buyan3303 #2 我研究下,谢谢
reter
2022-10-31 11:42:57 +08:00
我认为分 IO 和 CPU 密集型

如果是 IO:
1.上多线程
2.上异步

如果是 CPU:
1. 不要管
2. 用其他语言如 C 重写关键逻辑,或者整个逻辑
3. 换解释器,如带 JIT 的 pypy
ospider
2022-10-31 11:46:51 +08:00
如果不需要 IO ,考虑向量化处理,比如 pandas ;
如果需要 IO ,考虑批量处理,减少往返开销。
mmm159357456
2022-10-31 12:05:40 +08:00
@reter
@ospider
如果业务中既有 IO 又有 cpu 密集呢?有无可能并行化 for 循环?是不是需要上协程
apake
2022-10-31 12:19:00 +08:00
上多进程
MrGba2z
2022-10-31 13:04:44 +08:00
如果 abc list 有重复数据 可以给 f 加 @cache
chaunceywe
2022-10-31 13:10:35 +08:00
先把参数元组用 product 创建好,然后再进行下一步处理。可以用 ray 或 joblib 之类的包来运行这些生成好的任务。
mmm159357456
2022-10-31 13:16:15 +08:00
@apake #7 没考虑 GIL 的问题吗?

@MrGba2z #8 收到,我看看文档

@chaunceywe #9 好的,我研究下
hsfzxjy
2022-10-31 13:24:03 +08:00
这种显式循环应该是纯 python 下最快的了
lolizeppelin
2022-10-31 13:29:33 +08:00
转 dict, O(1)

代码也可以变漂亮
try
a = data[i]
b = data2[a]
c = data3[b]
expect IndexError
return 'not found'
wxf666
2022-10-31 13:43:26 +08:00
@mmm159357456 IO 部分用多线程,CPU 部分用多进程,整体用协程管理?

参考: https://docs.python.org/zh-cn/3/library/asyncio-eventloop.html#executing-code-in-thread-or-process-pools
paramagnetic
2022-10-31 13:52:44 +08:00
1. 思考这个地方是不是真的需要优化( doge
2. 能向量化尽量向量化,扔给 numpy, pandas 获得数量级等级的性能提升
3. 实在不行,把结果 list 先初始化成最终大小然后再 mutate 能提升个百分之二三十?
mmm159357456
2022-10-31 14:02:00 +08:00
@lolizeppelin #12 对于硬盘 IO 的循环也可以这么操作吗?

@wxf666 #13 协程给我的感觉就是难以 debug ,能不用我尽量不用

@paramagnetic #14 我现在遇到的问题就在于:需要调取同一目录下不同模式的模拟数据(大概 40 多 G ,3kw 条数据),每种模拟数据还有不同的处理水平,每个模式的数据文件中还有不同的要素,最终需要每个要素正交,分别计算。因为 pandas 只能在单核上跑,后面加上了 dask 之后还是慢,我就在想是不是要优化多层嵌套循环
liuxingdeyu
2022-10-31 14:14:33 +08:00
f 里面干了啥,如果有 io ,那就加线程或者协程做成异步,如果是计算密集加 io 密集,就多进程加多线程或者多进程加协程,如果是纯计算,那就多进程
wxf666
2022-10-31 14:20:54 +08:00
@mmm159357456 我觉得在多线程多进程面前,协程是非常友好容易调试的了。。

另外,你的附加留言里说的好抽象。。要不,举点例子?
mmm159357456
2022-10-31 14:35:17 +08:00
@liuxingdeyu #16 f 里就是根据 list_a 遍历加载模式数据(按日排列),然后根据年份( list_b )及模式中的要素值计算相关指标(几乎都是加减乘除和 datetime 操作),再和定义好的界限值比较,组成新的 dataframe 返回,已经安排上了 dask ,现在是多进程、多线程在跑,但是一个模式也要跑 28h 的样子,现在想调优,但是不知道具体瓶颈是在哪儿

@wxf666 如上,现在的想法是把嵌套的循环打平,不知道先行 product 后,能不能提高执行效率
featureoverload
2022-10-31 14:40:51 +08:00
问题给的例子基本没办法优化。和是否是 Python 语言基本没啥关系。

它本身就是一个 O(na * nb * nc) 复杂度的问题(如果 na ≈ nb ≈ nc ,那么就是 O(n^3) 复杂度)。

如果真的有必要优化。

1. 寻找 na,nb,nc 里面元素的重复之处。
2. 是否有必要遍历全部,是否实际只要执行部分就 break 退出的情况
3. 使用纯 C/C++ 重写和这段代码相关的所有代码 -- 加上优化的功能,类似并行计算等等。
mmm159357456
2022-10-31 14:43:43 +08:00
@featureoverload 好的,我再思考下

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/891370

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX