为什么对原始数据排序会对全遍历情况产生性能影响？-灵析社区

这是个值得研究的问题，我测试下来，这个现象和排序无关，可能和这个大型字符串数组的寻址效率有关。 1. 不是sorted的原因 test_strings = tuple(test_strings) # 这一行 只要打乱原有顺序，不论是排序的，还是随机的，都会使得遍历变慢，比如： `test_strings = sorted(test_strings)` 或者 `random.shuffle(test_strings)` 或者 `test_strings = random.sample(test_strings, len(test_strings))` 2. 和迭代内的操作无关 把这段代码从 print('开始生成测试数据...') for i in tqdm.tqdm(range(num)): test_data_str = ''.join( [random.choice('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ') for _ in range(random.randint(3, 8))]) data.append((test_data_str, {j for j in test_strings if j.startswith(test_data_str)})) 改为一个空迭代： print('开始生成测试数据...') for i in tqdm.tqdm(range(num)): for j in test_strings: pass 也能明显比较出test_strings打乱原有顺序前后的效率差别 以下是我关于此例，内存寻址方面问题的一点推测，还待牛人指点： 0. 前提： test_strings中的字符串们，创建时即被append，所以内存地址大致是顺序的(堆上分配的对象) 1. CPU缓存命中 > CPU高速缓存（英语：CPU > Cache，在本文中简称缓存）是用于减少处理器访问内存所需平均时间的部件。在金字塔式存储体系中它位于自顶向下的第二层，仅次于CPU寄存 > 器。其容量远小于内存，但速度却可以接近处理器的频率。当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。如果存在（命中），则不经访问内存直接返回该数据；如果不存在（失效），则要先把内存中的相应数据载入缓存，再将其返回处理器 缓存从内存中抓取一般都是整个数据块，所以它的物理内存是连续的。如果打乱原有顺序遍历的话，将会使整个缓存块无法被利用，而不得不从内存中读取数据，而从内存读取速度是远远小于从缓存中读取数据的。 2. 分页调度 显然test_strings里所有的字符串跨了多个内存页了，但是如前提所言，内存地址还是大致连续的`for j in test_strings`遍历时，并没有频繁地页面调度。但sorted排序后，这种顺序没了，会有频繁的页面调度，这个操作是有时间消耗的，调度次数越多，遍历时间越长。 PS: 你试一试 `test_strings = list(reversed(test_strings))` 参考阅读：[https://zhuanlan.zhihu.com/p/549919985](https://link.segmentfault.com/?enc=y99tWuVHwMfkzGmJUvdwWg%3D%3D.a%2Fx3qIEyWw6ciSmMHDiEsrp6yJgyXsG3SiRDi3KQSyfoWNnVU4FC7Azn5eiXWyyz)