探究原始数据顺序对全遍历效率的影响
在构建测试数据生成器时，我发现一个有趣的现象：对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))。这有助于进一步理解性能差异的根源，即内存访问模式对性能的影响远大于排序算法本身。 关键在于理解内存访问局部性原理，以及如何利用它来优化代码性能。
以上就是对原始数据进行排序会显着增加全遍历的生成时间？的详细内容，更多请关注php中文网其它相关文章！
微信扫一扫打赏
支付宝扫一扫打赏
