探究range(n)数对生成性能差异及最优列表推导式实现

问题背景 #

需要生成0至n-1的所有无序数对（例如n=4时，数对为[(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)]），现有三种生成方式：

• list(combinations(range(n), 2))
• [(i, j) for i, j in combinations(range(n), 2)]
• [(i, j) for i in range(n) for j in range(i+1, n)]

当n=1000时，基准测试结果如下：

• 44.1 ms ± 0.2 ms f_combinations_pure（对应第一种方式）
• 57.7 ms ± 0.3 ms f_combinations（对应第二种方式）
• 66.6 ms ± 0.1 ms f_ranges（对应第三种方式）

注：实际需求是用i、j执行处理（如截取子串）而非仅存储数对，因此第一种方式不纳入核心对比。

提出的问题 #

1. 为何双重循环实现（f_ranges）比基于combinations的列表推导式（f_combinations）更慢？从循环次数和赋值逻辑看前者理应更快，实际却相反，原因是什么？
2. 请给出可生成相同数对列表的最快列表推导式实现方案，用于公平对比。

问题解答 #

1. 双重循环更慢的核心原因 #

itertools.combinations是Python标准库中用C语言实现的函数，它的核心数对生成逻辑完全在C层面执行，绕过了Python解释器的字节码处理开销。而f_ranges的嵌套循环是纯Python级别的，每一次for迭代都要经过Python解释器的解析、执行，哪怕循环次数相同，单步执行成本也比C实现高得多。

另外，f_ranges中每次内层循环都要创建新的range(i+1, n)对象，会产生额外的对象创建和销毁开销；而combinations内部直接对原始的range(n)序列处理，避免了重复创建range对象的成本。这些细节累加起来，就导致纯Python嵌套循环的性能不如基于C实现的combinations方案。

2. 最快的列表推导式实现方案 #

如果限定用列表推导式，最优方案就是[(i, j) for i, j in combinations(range(n), 2)]——它借助C实现的combinations完成核心数对生成，只在Python层面做元组包装，这是纯Python循环无法超越的。

如果必须完全不依赖itertools，可以尝试减少内层range对象的重复创建，但性能依然无法追上combinations方案，比如：

r = range(n)
[(i, j) for i in r for j in r[i+1:]]

不过实际测试中，这个版本和原f_ranges性能差距很小，本质上还是Python级别的循环，无法突破解释器的性能瓶颈。

内容的提问来源于stack exchange，提问作者Kelly Bundy