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

Question

我在编写一段测试数据的生成代码，但我发现一个奇怪的现象

import random
import json
import tqdm
import sys
import humanize

num = 100000
test_data_num = 0

test_strings = []
print('生成随机字符串...')
for i in tqdm.tqdm(range(num * 10)):
    test_strings.append(''.join(
        [random.choice('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ')
         for _ in range(random.randint(3, 10))]))
test_strings = tuple(test_strings)  # 这一行
print('随机字符串生成完毕，大小为:',
      humanize.naturalsize(sys.getsizeof(test_strings)))
data: list = []
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('测试数据生成完毕，大小为:',
      humanize.naturalsize(sys.getsizeof(data)))
json.dump({'num': num, 'test_strings': test_strings, 'data': data}, open(f'test_data_{test_data_num}.json', 'w'))

如果把test_strings = tuple(test_strings)替换成test_strings = tuple(sorted(test_strings)),那生成测试数据的部分耗时会增加为原来的2倍多（从2.5h变成了5.5h）。这是什么情况？（是生成测试代码的部分，不是排序，而且排序本身并没有消耗太多时间）
理论上来将生成部分的核心代码是{j for j in test_strings if j.startswith(test_data_str)}，无论是排序还是不排序，时间复杂度应该都是O(n)才对啊。
对于这段代码，我有其他方式优化了，但我还是想知道这是啥情况。
替换前的测试：

生成随机字符串...
100%|██████████| 1000000/1000000 [00:02<00:00, 347291.67it/s]
随机字符串生成完毕，大小为: 8.0 MB
开始生成测试数据...
  0%|          | 23/100000 [00:01<2:22:16, 11.71it/s]

替换后的测试：

生成随机字符串...
100%|██████████| 1000000/1000000 [00:02<00:00, 351700.63it/s]
随机字符串生成完毕，大小为: 8.0 MB
开始生成测试数据...
  0%|          | 22/100000 [00:04<5:49:42,  4.76it/s]

我测试过把那一行的tuple换成list，效果一样

Answer 1

这是个值得研究的问题，我测试下来，这个现象和排序无关，可能和这个大型字符串数组的寻址效率有关。

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