探究原始数据顺序对全遍历效率的影响
在构建测试数据生成器时，我发现一个有趣的现象：对test_strings进行排序后，数据生成时间显著增加。这令人费解，因为理论上，无论数据是否排序，时间复杂度都应为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)) # 修改后的代码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))。这有助于进一步理解性能差异的根源，即内存访问模式对性能的影响远大于排序算法本身。 关键在于理解内存访问局部性原理，以及如何利用它来优化代码性能。
以上就是为什么对原始数据进行排序会显着增加全遍历的生成时间？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1359698.html
微信扫一扫 
支付宝扫一扫 
