为什么Python处理已排序列表的耗时比未排序列表更长？

这个问题挺有意思的，我来帮你拆解一下背后的原因～

先把你的测试代码和运行结果放出来，方便大家理解场景：

测试代码 #

import cProfile, random, copy
def foo(lIn):
    return [i*i for i in lIn]
lIn = [random.random() for i in range(1000000)]
lIn1 = copy.copy(lIn)
lIn2 = sorted(lIn1)
cProfile.run('foo(lIn)')
cProfile.run('foo(lIn2)')

运行结果 #

3次函数调用，耗时0.075秒
按标准名称排序
ncalls  tottime  percall  cumtime  percall  filename:lineno(function)
1      0.005    0.005    0.075    0.075    :1()
1      0.070    0.070    0.070    0.070    test.py:716(foo)
1      0.000    0.000    0.000    0.000    {method 'disable' of '_lsprof.Profiler' objects...}

（注：默认你排序后的列表实际耗时比原列表更长，和你描述的现象一致）

你观察到的这个反直觉现象，核心原因是CPU缓存命中率的差异，而这和Python列表的底层存储逻辑密切相关：

• Python的普通列表本质是对象引用的数组——每个元素并不是直接存储浮点数的数值，而是指向内存中实际float对象的指针。
• 你用列表推导生成原列表lIn时，这些float对象是连续创建的，所以它们在内存中的地址是连续（或接近连续）的。当遍历原列表计算平方时，CPU可以一次性把连续的内存块加载到高速缓存里，后续访问元素时大多能命中缓存，执行效率自然很高。
• 而调用sorted()对列表排序时，它只会重新排列列表里的引用指针，让指针按浮点数的大小顺序排列。这时候，这些指针指向的float对象在内存中的位置就变成分散、不连续的了。遍历排序后的列表时，CPU每次访问元素都要跳转到内存的不同位置，频繁出现「缓存未命中（cache miss）」，不得不从速度慢得多的主存中加载数据，最终导致耗时明显增加。

你可以做个小验证，打印原列表和排序后列表中元素的内存地址，就能看到差异：

print([id(i) for i in lIn[:10]])  # 地址连续递增
print([id(i) for i in lIn2[:10]]) # 地址杂乱无章

另外补充一个小知识点：如果用的是存储原始数值的数组（比如numpy的ndarray），排序后的数组内存是连续的，这时候处理排序后的数组反而会更快——因为连续的数值访问能让CPU缓存命中率更高。但Python普通列表的引用存储方式，刚好导致了和我们直觉相反的结果。

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