为什么Python中增大randint边界后遍历排序后的列表会变慢？

核心差异来自CPU缓存命中率的不同，和Python整数对象的内存分配规则、列表排序逻辑直接相关：

• 首先可以排除分支预测的影响：你代码的if-else分支无论走哪个逻辑，执行的都是完全相同的_ = 1赋值操作，分支走向不会带来执行耗时的差异。
• 小取值范围（r≤100）的场景：Python内置了全局小整数缓存池，默认缓存-5~256范围内的所有整数，这个区间的整数都是全局复用的固定对象，内存地址连续且固定。排序后的s_yes按值从小到大排列，对应访问的整数对象内存地址也是连续的，缓存命中率比乱序的s_not更高，所以此时s_yes遍历耗时略低。
• 取值范围超过256后的场景：
  1. 此时randint生成的整数不再属于小整数缓存范围，每次调用都会创建全新的整数对象，你生成s_not时是按顺序依次创建这些新整数的，所以这些整数对象的内存地址是连续分配的。s_not里的引用按生成顺序存储，遍历的时候访问整数对象的内存地址也是连续的，CPU缓存命中率极高，所以s_not的遍历耗时一直稳定在1.1s左右。
  2. 而s_yes是按整数值大小排序后的结果，排序后列表内的引用指向的整数对象内存地址被完全打乱，变成随机跳跃的状态。遍历s_yes时每次访问整数对象都要跳转到完全不相关的内存地址，CPU多级缓存基本无法命中，只能频繁从主内存拉取数据，而主内存的访问耗时是缓存的几十上百倍，所以遍历耗时大幅上升。
• 当r超过1000后耗时趋于稳定，是因为r足够大时randint生成的整数重复率已经接近0，排序后的地址随机程度达到上限，缓存命中率不会再进一步降低，所以耗时稳定在3.3s左右。

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