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

优化不知道，多层嵌套一般用 `itertools.product`

@zzl22100048 #1 对于使用 product 是否能提升执行效率呢？我知道这样是减少了嵌套层数
@buyan3303 #2 我研究下，谢谢

我认为分 IO 和 CPU 密集型

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

如果是 CPU：
1. 不要管
2. 用其他语言如 C 重写关键逻辑，或者整个逻辑
3. 换解释器，如带 JIT 的 pypy

如果不需要 IO ，考虑向量化处理，比如 pandas ；
如果需要 IO ，考虑批量处理，减少往返开销。

@reter
@ospider
如果业务中既有 IO 又有 cpu 密集呢？有无可能并行化 for 循环？是不是需要上协程

上多进程

如果 abc list 有重复数据 可以给 f 加 @cache

先把参数元组用 product 创建好，然后再进行下一步处理。可以用 ray 或 joblib 之类的包来运行这些生成好的任务。

@apake #7 没考虑 GIL 的问题吗？

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

@chaunceywe #9 好的，我研究下

这种显式循环应该是纯 python 下最快的了

转 dict, O(1)

代码也可以变漂亮
try
a = data[i]
b = data2[a]
c = data3[b]
expect IndexError
return 'not found'

@mmm159357456 IO 部分用多线程，CPU 部分用多进程，整体用协程管理？

参考： https://docs.python.org/zh-cn/3/library/asyncio-eventloop.html#executing-code-in-thread-or-process-pools

1. 思考这个地方是不是真的需要优化（ doge
2. 能向量化尽量向量化，扔给 numpy, pandas 获得数量级等级的性能提升
3. 实在不行，把结果 list 先初始化成最终大小然后再 mutate 能提升个百分之二三十？

@lolizeppelin #12 对于硬盘 IO 的循环也可以这么操作吗？

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

@paramagnetic #14 我现在遇到的问题就在于：需要调取同一目录下不同模式的模拟数据（大概 40 多 G ，3kw 条数据），每种模拟数据还有不同的处理水平，每个模式的数据文件中还有不同的要素，最终需要每个要素正交，分别计算。因为 pandas 只能在单核上跑，后面加上了 dask 之后还是慢，我就在想是不是要优化多层嵌套循环

@mmm159357456 我觉得在多线程多进程面前，协程是非常友好容易调试的了。。

另外，你的附加留言里说的好抽象。。要不，举点例子？

@liuxingdeyu #16 f 里就是根据 list_a 遍历加载模式数据（按日排列），然后根据年份（ list_b ）及模式中的要素值计算相关指标（几乎都是加减乘除和 datetime 操作），再和定义好的界限值比较，组成新的 dataframe 返回，已经安排上了 dask ，现在是多进程、多线程在跑，但是一个模式也要跑 28h 的样子，现在想调优，但是不知道具体瓶颈是在哪儿

@wxf666 如上，现在的想法是把嵌套的循环打平，不知道先行 product 后，能不能提高执行效率

问题给的例子基本没办法优化。和是否是 Python 语言基本没啥关系。

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

如果真的有必要优化。

1. 寻找 na,nb,nc 里面元素的重复之处。
2. 是否有必要遍历全部，是否实际只要执行部分就 break 退出的情况
3. 使用纯 C/C++ 重写和这段代码相关的所有代码 -- 加上优化的功能，类似并行计算等等。

@featureoverload 好的，我再思考下

@mmm159357456 为啥每一天（ list_a ）都要计算每一年（ list_b ）的指标。。

当 x1 = 2022-10-31 时，也要计算 x2 = 1970/1971/1972/.../2099 的指标吗？？？

还是说，你遍历 list_b 是为了找到 x2 = 2022 ？

list_a 为啥要按日排列？[2099-12-31, 2000-01-01, 1970-12-31, 2099-01-01] 这样的排列有啥问题吗？反正每个日子都要计算 range(1970, 2100) 年的指标的。。



可能你放出函数 f 的伪代码，大家能更好讨论

你这个不是嵌套循环的问题
1. 先考虑是否需要全部遍历
2. a b c 三层是随机变化的还是线性增长的
3. 一次性任务直接 ray 跑就别优化了

@wxf666 https://gist.githubusercontent.com/vfq/0337327cdb29538e2f39e21b9eb99deb/raw/4cb9878145e3723e1919059502e6acfdf82551c2/sample.py

差不多是这样的吧

@zzl22100048 我再看看吧，我现在想做优化的原因在于循环内的处理逻辑一直在变动，每次变动后需要一天的时间才能算出来一个模式（还不知道对不对），我着急...
另外：
1.我确实需要全部遍历
2.每一层的迭代对象我都预处理成固定长度的对象了

你试着把 for 循环的数据构造一个 dataframe 然后和 data join(pandas 里面应该是 merge)然后再算结果呢

@mmm159357456 我觉得三件事可能是有回报的。第一查又没有冗余的计算之类的，可以做个用点空间换时间或者 dp 优化一下。第二就是线程换协程，本质上就是省下来了线程切换的时间；或者直接一个进程里就单线程跑，多搞几个进程，Linux 下进程线程基本上一回事，切来切去的不如多进程搞完再汇总。第三就是把操作用 numpy 之类的 c++库搞一下。

看代码，感觉是不是可以用原始数据 pandas ，对 df 做 groupby 后再 sum 解决？

@mmm159357456 我没看出 level 作用是啥。。


考虑使用数据库吗？感觉可以转成 SQL：

SELECT year(dateday), geometry, SUM(IF(el1 >= theshold, el1, NULL)), SUM(IF(el2 >= theshold, el2, NULL)), ...
　 FROM ...
GROUP BY year(dateday), geometry


基本上，扫一遍文件就算出来了

@FYFX #25 能具体说说吗？我这每个循环都相当于处理逻辑的实参

@liuxingdeyu #26 dask 已经这么做了

@TimePPT #27 可以 groupby ，这样的话就要涉及 multiindex 。另外我的机器内存放不下所有数据

@wxf666 level 用于构建 dataframe ，我再考虑考虑

@mmm159357456 我觉得根据 year(dateday), geometry 来 groupby ，要不了多少内存吧？

大概只需要：200 年 * len(geometry_list) 行，len(elements_in_data) 列

@mmm159357456
就是用 for 循环中的那些数据，生成一个全量的表表头是 geometry start_date end_date theshold(不过我在你代码里没看到这个变量从哪来的），然后和 data 做内连接（而且像前面说的，data 数据可以先做一次预聚合），内连接就是你写的那些条件，然后结果应该就是你要得数据了。还有内存放不下的话，看着行数据之间是没有依赖的，我感觉可以拆 data 的数据分多次处理吧，然后再合并，类似于 map-reduce

@wxf666
@FYFX
我去试试各位的方法，感谢

@FYFX @mmm159357456 我觉得没必要做啥 join ，直接在 data 上 groupby 后，对 el1, el2, ..., elN 做 sum 即可（只累加 >= theshold 的值）

换成 SQL 应该是 28 楼那样

结果应该是 31 楼那样，(年份数 * len(geometry_list)) 行 x (len(elements_in_data)) 列 的表

是在一个很大的时间尺度上做滑窗吗？每个滑窗还要跨文件 IO ，机器还没法一下全读了？
个人经验即使是分布式的 spark 上，优化的空间并不大。而且 spark 上滑窗的计算也很慢，不知道新一点的 dask ，ray 这方便会比 spark 强多少。

@specter119 对，我是在做 rolling ，感觉 dask 也没快到哪里去

或许上 Cython 会有奇效

类似的场景，把那部分逻辑用 c 写了个模块，效率提升上百倍起步

把在硬盘上连续的放在最里面的 for ，这样 io 会快很多，其他的想不到了

@fairless #38 哈哈哈，难度一下子上来了

@nuk 我试试

@mmm159357456 说起来你可能不信，那个函数执行一万次，python 要 26s c 写的只要 0.2 秒不到

当然我这个不仅仅是 for 循环，里面还涉及到大量的基础运算以及 list 、类型转换(int8 int32)等，c 的话运算速度以及数组都非常快，而且不存在类型转换的步骤。

@mmm159357456 你原始数据是 CSV 之类的吗？

能给个 1900 年的数据吗？我想试试用 SQL 能多快 /慢

如果数据比较敏感，可以给个模拟数据。比如：（只要模拟完后，数据量差不多和原来一样即可。如存为 csv 后 1GB ）

dateday, geometry, element1, element2, ..., elementN
1900-01-01, geometry1, 11111111, 11111111, ..., 11111111
1900-01-02, geometry2, 22222222, 22222222, ..., 22222222
...

@wxf666 不好意思，数据给不了，原先数据是存在 csv 里面的，后面我清洗过后转成了 parquet

@mmm159357456 给个模拟数据吧

- 列名是像上面那样吗？
- 平均每一年有多少行？
- 有多少种 geometry ？平均有多少个字符？ geometry1 ？ ggeeoommeettrryy11 ？
- 有多少个 element ？

@wxf666

dateday, geometry, element1, element2, element3, element4


geometry 大概 300 个，为经纬度的组合，精细到小数点后四位；
dateday19010101-21001331 ，timedelta 为 1d ；
element[1-3]均需要处理成滑动平均，element4 计算滑动窗口的总和，所有 elements 值域在[0, 50]

以上组合完成后需要两个处理水平重复，外加 20 种模式（即 X 2 X 20

更正：dateday19010101-21001231 ，timedelta 为 1d ；

@mmm159357456 你还真跨了 200 年嘛。。


假设只有 3 天和 3 个 geometry ，下表符合最终源数据表的格式了嘛？（我把经纬度拆开了）

dateday, geometry_x, geometry_y, element1, element2, element3, element4
2000-01-01, 1.0000, -1.0000, 1, 2, 3, 4
2000-01-01, 2.0000, -2.0000, 5, 6, 7, 8
2000-01-01, 3.0000, -3.0000, 9, 10, 11, 12
2000-01-02, 1.0000, -1.0000, 13, 14, 15, 16
2000-01-02, 2.0000, -2.0000, 17, 18, 19, 20
2000-01-02, 3.0000, -3.0000, 21, 22, 23, 24
2000-01-03, 1.0000, -1.0000, 25, 26, 27, 28
2000-01-03, 2.0000, -2.0000, 29, 30, 31, 32
2000-01-03, 3.0000, -3.0000, 33, 34, 35, 36


下面这俩，是生成上表的规则？还是要求 SQL 计算时要实现的功能？

- 『 element[1-3]均需要处理成滑动平均，element4 计算滑动窗口的总和』
- 『以上组合完成后需要两个处理水平重复，外加 20 种模式（即 X 2 X 20 』


另外：

1. 滑动窗口有多大？要按什么分组和排序吗？（比如，按<年>分组，按<天, 经纬度>排序？）
2. 『两个处理水平重复，外加 20 种模式』是啥意思。。

@wxf666 第一条即是需要实现的功能，原始数据中只有每天的数据，没有滑动，也没有合计

数据表就和你这个差不多，窗口是在 5 、10 、15 中滑动，分组的话按某一年某一点来算。

两个处理水平重复，外加 20 种模式，为上面的表乘以 2 再乘以 20 ，即 40 个相同结构的表但数据不一样

@mmm159357456

你是说：

1. 滑动窗口按 <年, 地区> 分组，按 <时间> 顺序滑动
2. element1/2/3 是窗口大小分别为 5/10/15 的平均值，element4 = 此时这仨平均值之和
3. 每张表都这么算，共计算 40 次

？

@wxf666
1.滑动窗口按 <年, 地区> 分组，按 <时间> 顺序滑动，计算 element1/2/3 的滑动平均值，并将值安置在滑动起点的同一行
2.element1/2/3 是窗口大小分别为 5/10/15 的平均值，element4 是对应滑动窗口内的 element4 值的合计
3.对

@mmm159357456

假设下表是 2000 年某地区的一张表（省略年份和经纬度），列 1 窗口大小为 2 ，列 2 为 4 ，列 3 为 6：

　　日期　　列１　列２　列３　列４

０１－０１　１１　２１　３１　４１
０１－０２　１２　２２　３２　４２
０１－０３　１３　２３　３３　４３
０１－０４　１４　２４　３４　４４
０１－０５　１５　２５　３５　４５
０１－０６　１６　２６　３６　４６
０１－０７　１７　２７　３７　４７
０１－０８　１８　２８　３８　４８
０１－０９　１９　２９　３９　４９

1. 1 日、2 日、9 日，新的『列 1 』值应为多少？

a. (11+12)/2 ，(12+13)/2 ，19
b. (11+12)/2 ，不算 2 日，19
c. ……？

2. 新的『列 4 』值怎么算？（像上面那样，随便写两三个日期即可）

列 1 窗口大小为 2 ，选择 min_period = 1,那么 01-01 对应 11 ，01-02 对应 (11+12)/2 ，01-03 对应(12+13)/2...01-09 对应(18+19)/2

列 4 相对于列 1 来说如果 窗口大小为 2 ，选择 min_period = 1 ，那么 01-01 对应 41 ，01-02 对应 41+42 ，01-03 对应 42+43....01-03 对应 48+49 （简而言之列 4 的窗口是相对于前面三列的窗口来相应调整）

所有的 rolling 均是向前滑动，即滑动的值均是针对已出现的值，计算 01-09 不能用 01-10 的值，因为 01-10 是将来时

@mmm159357456

1. 你不是说『将值安置在滑动<起点>的同一行』吗？我就在想，(11+12)/2 要放在 11 那行。。

2. 上面假设了，『列 1 窗口大小为 2 ，列 2 为 4 ，列 3 为 6 』。所以，列 4 的窗口大小是怎么调整的？直接 = 列 1 窗口大小 = 2 ？？

3. 所以，最终结果是 40 张表，每张表的表头是 (日期、经纬度、列 1 、2 、3 、4)，共计 3KW 行？？

@wxf666
1.所有滑动是向前滑动，参考我上一条最后一句。(11+12)/2 是 01-02 的滑动值
2.对
3.其实说是有 40 张表，其实最开始是 element[1-4]是分别处在不同里的，我跟你说的表都是合并过后的，具体的行数大概是 300*200*365*2*20

我觉得优化逻辑才是根本，可以参考恋爱循环的嵌套。

@GoodRui
https://www.google.com/search?q=%E6%81%8B%E7%88%B1%E5%BE%AA%E7%8E%AF&rlz=1C1CHWL_zh-CNCN986CN986&sourceid=chrome&ie=UTF-8

really ？？

如果这里是热点，可以考虑 C++ 重写，然后用 Python 调用吧。一般来说能快两个数量级

@buyan3303 好文章 感谢推荐

@mmm159357456 用 SQLite 测试了生成整张表、计算整张表，结果如下：

　　项目　　　　　　结果大小　　　　用时

生成数据库　１．０２ＧＢ的数据库　２分钟
计算整张表　１．３５ＧＢ的ＣＳＶ　７分钟


## 数据库预览（ CSV 形式预览。200 年 x 365/366 天 x 360 个经纬度 = 26297640 行）：

year,dateday,geometry_x,geometry_y,element1,element2,element3,element4
1900,1900-01-01,0.0,0.0,1,1001,2001,3001
1900,1900-01-02,0.0,0.0,2,1002,2002,3002
1900,1900-01-03,0.0,0.0,3,1003,2003,3003
……
1900,1900-12-29,0.0,0.0,363,1363,2363,3363
1900,1900-12-30,0.0,0.0,364,1364,2364,3364
1900,1900-12-31,0.0,0.0,365,1365,2365,3365
1900,1900-01-01,1.0,-1.0,1,1001,2001,3001
1900,1900-01-02,1.0,-1.0,2,1002,2002,3002
1900,1900-01-03,1.0,-1.0,3,1003,2003,3003
……
1900,1900-12-29,359.0,-359.0,363,1363,2363,3363
1900,1900-12-30,359.0,-359.0,364,1364,2364,3364
1900,1900-12-31,359.0,-359.0,365,1365,2365,3365
1901,1901-01-01,0.0,0.0,1,1001,2001,3001
1901,1901-01-02,0.0,0.0,2,1002,2002,3002
1901,1901-01-03,0.0,0.0,3,1003,2003,3003
……
2099,2099-12-29,359.0,-359.0,363,1363,2363,3363
2099,2099-12-30,359.0,-359.0,364,1364,2364,3364
2099,2099-12-31,359.0,-359.0,365,1365,2365,3365


## 计算结果预览（ CSV 文件）：

1900,0.0,0.0,1900-01-01,1.0,1001.0,2001.0,3001.0
1900,0.0,0.0,1900-01-02,1.5,1001.5,2001.5,3001.5
1900,0.0,0.0,1900-01-03,2.0,1002.0,2002.0,3002.0
1900,0.0,0.0,1900-01-04,2.5,1002.5,2002.5,3002.5
1900,0.0,0.0,1900-01-05,3.0,1003.0,2003.0,3003.0
1900,0.0,0.0,1900-01-06,4.0,1003.5,2003.5,3004.0
……


## 计算方式预览（ CSV 形式。可保存后用 Excel 查看）：

1900,0.0,0.0,1900-01-01,(1)/1,(1001)/1,(2001)/1,(3001)/1
1900,0.0,0.0,1900-01-02,(1+2)/2,(1001+1002)/2,(2001+2002)/2,(3001+3002)/2
1900,0.0,0.0,1900-01-03,(1+2+3)/3,(1001+1002+1003)/3,(2001+2002+2003)/3,(3001+3002+3003)/3
1900,0.0,0.0,1900-01-04,(1+2+3+4)/4,(1001+1002+1003+1004)/4,(2001+2002+2003+2004)/4,(3001+3002+3003+3004)/4
1900,0.0,0.0,1900-01-05,(1+2+3+4+5)/5,(1001+1002+1003+1004+1005)/5,(2001+2002+2003+2004+2005)/5,(3001+3002+3003+3004+3005)/5
1900,0.0,0.0,1900-01-06,(2+3+4+5+6)/5,(1001+1002+1003+1004+1005+1006)/6,(2001+2002+2003+2004+2005+2006)/6,(3002+3003+3004+3005+3006)/5
1900,0.0,0.0,1900-01-07,(3+4+5+6+7)/5,(1001+1002+1003+1004+1005+1006+1007)/7,(2001+2002+2003+2004+2005+2006+2007)/7,(3003+3004+3005+3006+3007)/5
1900,0.0,0.0,1900-01-08,(4+5+6+7+8)/5,(1001+1002+1003+1004+1005+1006+1007+1008)/8,(2001+2002+203+2004+2005+2006+2007+2008)/8,(3004+3005+3006+3007+3008)/5
1900,0.0,0.0,1900-01-09,(5+6+7+8+9)/5,(1001+1002+1003+1004+1005+1006+1007+1008+1009)/9,(2001+2002+2003+2004+2005+2006+2007+2008+2009)/9,(3005+3006+3007+3008+3009)/5
1900,0.0,0.0,1900-01-10,(6+7+8+9+10)/5,(1001+1002+1003+1004+1005+1006+1007+1008+1009+1010)/10,(2001+2002+2003+2004+2005+2006+2007+2008+2009+2010)/10,(3006+3007+3008+3009+3010)/5
1900,0.0,0.0,1900-01-11,(7+8+9+10+11)/5,(1002+1003+1004+1005+1006+1007+1008+1009+1010+1011)/10,(2001+2002+2003+2004+2005+2006+2007+2008+2009+2010+2011)/11,(3007+3008+3009+3010+3011)/5
……
1900,0.0,0.0,1900-12-31,(361+362+363+364+365)/5,(1356+1357+1358+1359+1360+1361+1362+1363+1364+1365)/10,(2351+2352+2353+2354+2355+2356+2357+2358+2359+2360+2361+2362+2363+2364+2365)/15,(3361+3362+3363+3364+3365)/5
1900,1.0,-1.0,1900-01-01,(1)/1,(1001)/1,(2001)/1,(3001)/1
1900,1.0,-1.0,1900-01-02,(1+2)/2,(1001+1002)/2,(2001+2002)/2,(3001+3002)/2
……


## 使用方式：

去 SQLite 官网下载个 1 MB 的 sqlite3.exe ，然后保存下面的 SQLite 代码为 main.sql ，然后命令行运行：

```shell
sqlite3.exe data.db < main.sql
```


## SQLite 代码：

*（ V 站排版原因，行首有全角空格）*

```sql
-- PRAGMA journal_mode = off; -- 取消日志记录。但这会输出个 off 。。
PRAGMA synchrOnous= off; -- 提交写请求给操作系统后，就可继续后续计算
PRAGMA cache_size = -8192; -- 占用 8 MB 内存

-- 建表
CREATE TABLE IF NOT EXISTS data (
　　 year INT,
　　 dateday DATE,
　　 geometry_x REAL,
　　 geometry_y REAL,
　　 element1 INT,
　　 element2 INT,
　　 element3 INT,
　　 element4 INT,
　　 PRIMARY KEY (year, geometry_x, geometry_y, dateday)
) WITHOUT ROWID;

-- 生成数据
INSERT INTO data
SELECT year.value,
　　　 DATE(year.value || '-01-01', day_of_year.value || ' days'),
　　　 area.value * 1.0,
　　　 area.value * -1.0,
　　　 day_of_year.value + 1,
　　　 day_of_year.value + 1001,
　　　 day_of_year.value + 2001,
　　　 day_of_year.value + 3001
　 FROM generate_series(1900, 2099) year,
　　　 generate_series(0, STRFTIME('%j', year.value || '-12-31') - 1) day_of_year,
　　　 generate_series(0, 359) area;

-- 计算表
SELECT year,
　　　 geometry_x,
　　　 geometry_y,
　　　 dateday,
　　　 /* -- 下面 4 行用于预览平均值的计算方式对不对
　　　 FORMAT('(%s)/%d', GROUP_CONCAT(element1, '+') OVER win5, COUNT(*) OVER win5),
　　　 FORMAT('(%s)/%d', GROUP_CONCAT(element2, '+') OVER win10, COUNT(*) OVER win10),
　　　 FORMAT('(%s)/%d', GROUP_CONCAT(element3, '+') OVER win15, COUNT(*) OVER win15),
　　　 FORMAT('(%s)/%d', GROUP_CONCAT(element4, '+') OVER win5, COUNT(*) OVER win5)
　　　 */
　　　 AVG(element1) OVER win5,
　　　 AVG(element2) OVER win10,
　　　 AVG(element3) OVER win15,
　　　 AVG(element4) OVER win5
FROM data
WINDOW win AS (PARTITION BY year, geometry_x, geometry_y ORDER BY dateday),
　　　 win5 AS (win ROWS 4 PRECEDING),
　　　 win10 AS (win ROWS 9 PRECEDING),
　　　 win15 AS (win ROWS 14 PRECEDING);
```

@wxf666 ok ，我参考下，谢谢

@mmm159357456 写漏了。。使用方式应该要将结果转成 csv ，再重定向至文件：

```shell
sqlite3.exe -csv data.db < main.sql > result.csv
```

@mmm159357456 这些都是单线程计算。

如果你是 8 核 CPU ，那可以同时计算 8 张表。

那么 40 张表总共只需不到 1 小时即可完成。



如果你自己转数据（即，用不到 generate_series 表值函数），可以直接在 Python 里用 sqlite 标准库。开个多进程，刷刷刷~

@specter119 请教一下，像 60 楼那样的数据（ 2600W 行数据），spark 计算 4 个不同的滑窗，需要多久？总共要多少内存？

（升级 python 版本，听说 3.11 变快了

@mmm159357456 看了#56 的代码，循环都是在构造参数组合吧？直接用 itertools 排列组合一下这几个列表，生成一个 list ，然后用 itertupple 循环会快很多

至于循环里的计算部分，没仔细看，不过一是尽量矢量化操作，二是用并发+lambda 处理，实在还是慢只能 c 或者 rust 了

@winglight2016 我试试看
@zxCoder 好的

@mmm159357456 楼主最后还用了啥方法？大概用时多久？占多少内存？

@wxf666 还没时间调，但是昨天晚上用了下 groupby.transform(rolling)，直接卡住

@mmm159357456 我好奇问一下，为啥你不愿意放出原始问题呢？

不怕问成 xy problem ，束缚大家的看问题的角度和解决思路么。。

- 比如，有回 换 Python 其他写法、上协程 /多线程 /多进程、升级 Python 、换 C/C++/Rust 提升三次 for 速度的，

- 有剔除重复数据、剪枝来减少 for 数量空间的

- 还有零星几个回复是改变 pandas 运算方法，改变数据存储结构使得能顺序读取的


万一，根本不用三次 for 呢？（比如，如果真的只是计算滑窗数据的话，真的不用三层 for 。另外，个人觉得，既然你用了 pandas ，就该少让 python 掺和进来，多用 pandas 的方法去整体计算 dataframe ）

万一，换种数据存储结构，就能高效读取数据和计算呢？（比如，不用随机读，减少 groupby 、sort 、join 了）

万一，有数学大佬能推出个啥神奇公式，能 O(1) 解决问题了呢？

@wxf666 简单点讲就是数据涉密啊，简单描述没什么问题，直接公开那是不能的

@mmm159357456 像 #48 楼、#52 、#60 那样，编个数据不就好了。。

只要给出的解决方案也能通用到你原始数据上，目的不就达到了。。