探究原始数据顺序对全遍历效率的影响
在构建测试数据生成器时，我发现一个有趣的现象：对test_strings进行排序后，数据生成时间显著增加。这令人费解，因为理论上，无论数据是否排序，时间复杂度都应为O(n)。
以下是我的代码：
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) # 原代码
test_strings = tuple(sorted(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.5小时激增到5.5小时。排序本身耗时并不多，因此这并非排序导致的。
经过测试和分析，我发现问题并非排序本身，而是与大型字符串数组的内存访问效率有关：
-
并非排序导致: 无论使用
sorted()、random.shuffle()，还是random.sample()打乱顺序，都会导致遍历速度变慢。关键在于破坏了原始数据的内存地址连续性。 -
与迭代内部操作无关: 即使将内部循环替换为空循环，
for j in test_strings: pass，仍然能观察到顺序变化带来的性能差异。
我的推测如下：
-
初始状态:
test_strings中的字符串在创建时按顺序添加到列表中，因此它们的内存地址大致连续。 -
CPU缓存命中: CPU缓存利用内存地址连续性来提高访问速度。当访问顺序与内存地址顺序一致时，缓存命中率高，访问速度快；反之，缓存命中率低，需要频繁访问主存，速度慢。
-
页面调度:
test_strings可能跨越多个内存页。当内存地址连续时，页面调度次数少；当顺序被打乱后，页面调度次数增多，导致性能下降。
为了验证推测，可以尝试反向排序test_strings：test_strings = tuple(reversed(test_strings))。这有助于进一步理解性能差异的根源，即内存访问模式对性能的影响远大于排序算法本身。 关键在于理解内存访问局部性原理，以及如何利用它来优化代码性能。
