数据排序对全遍历性能的意外影响
在构建测试数据生成器时，我观察到一个有趣的现象：对原始数据排序后，数据生成时间显著增加。这与预期的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)) # 排序
# random.shuffle(test_strings) # 打乱顺序
# test_strings = random.sample(test_strings, len(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) 替换为排序或打乱顺序操作（如 tuple(sorted(test_strings))、random.shuffle(test_strings) 或 random.sample），生成时间从2.5小时飙升至5.5小时。即使简单地将 tuple 替换为 list 也会导致时间增加。
性能分析与推测
-
排序并非罪魁祸首: 实验表明，问题并非排序本身，而是破坏了原始数据的内存地址连续性。排序、打乱或随机采样都会导致性能下降。
-
迭代操作无关: 即使将迭代内部操作简化为
pass，性能差异依然显著。 -
内存寻址效率: 我推测性能瓶颈在于内存访问效率。初始状态下，
test_strings中的字符串地址相对连续，有利于 CPU 缓存命中。排序或打乱后，地址变得离散，导致缓存失效率上升，频繁访问主内存，从而拖慢速度。 这可能也涉及到分页机制，顺序访问更少地触发页面置换。
为了验证缓存命中率的影响，可以尝试将 test_strings 反转：
test_strings = list(reversed(test_strings))
观察反转操作是否也会影响性能。 这些实验结果表明，数据在内存中的布局对全遍历性能有显著影响，这与CPU缓存和内存分页机制密切相关。
