为什么对原始数据进行排序或打乱顺序会显着增加全遍历的性能时间？

数据排序对全遍历性能的意外影响

在构建测试数据生成器时，我观察到一个有趣的现象：对原始数据排序后，数据生成时间显著增加。这与预期的O(n)时间复杂度相悖。

以下是我的测试代码片段：

import randomimport jsonimport tqdmimport sysimport humanizenum = 100000test_data_num = 0test_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缓存和内存分页机制密切相关。

以上就是为什么对原始数据进行排序或打乱顺序会显着增加全遍历的性能时间？的详细内容，更多请关注范的资源库其它相关文章！

转载请注明：范的资源库 » 为什么对原始数据进行排序或打乱顺序会显着增加全遍历的性能时间？