数据排序对全遍历性能的意外影响
在构建测试数据生成器时，我观察到一个有趣的现象：对原始数据排序后，数据生成时间显著增加。这与预期的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缓存和内存分页机制密切相关。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
