为什么对原始数据进行排序会显着增加全遍历的生成时间?

花韻仙語
发布: 2025-03-18 11:04:01
原创
774人浏览过

为什么对原始数据进行排序会显着增加全遍历的生成时间?

探究原始数据顺序对全遍历效率的影响

在构建测试数据生成器时,我发现一个有趣的现象:对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小时。排序本身耗时并不多,因此这并非排序导致的。

经过测试和分析,我发现问题并非排序本身,而是与大型字符串数组的内存访问效率有关:

  1. 并非排序导致: 无论使用sorted()、random.shuffle(),还是random.sample()打乱顺序,都会导致遍历速度变慢。关键在于破坏了原始数据的内存地址连续性。

  2. 与迭代内部操作无关: 即使将内部循环替换为空循环,for j in test_strings: pass,仍然能观察到顺序变化带来的性能差异。

我的推测如下:

  1. 初始状态: test_strings中的字符串在创建时按顺序添加到列表中,因此它们的内存地址大致连续。

  2. CPU缓存命中: CPU缓存利用内存地址连续性来提高访问速度。当访问顺序与内存地址顺序一致时,缓存命中率高,访问速度快;反之,缓存命中率低,需要频繁访问主存,速度慢。

  3. 页面调度: test_strings可能跨越多个内存页。当内存地址连续时,页面调度次数少;当顺序被打乱后,页面调度次数增多,导致性能下降。

为了验证推测,可以尝试反向排序test_strings:test_strings = tuple(reversed(test_strings))。这有助于进一步理解性能差异的根源,即内存访问模式对性能的影响远大于排序算法本身。 关键在于理解内存访问局部性原理,以及如何利用它来优化代码性能。

以上就是为什么对原始数据进行排序会显着增加全遍历的生成时间?的详细内容,更多请关注php中文网其它相关文章!

最佳 Windows 性能的顶级免费优化软件
最佳 Windows 性能的顶级免费优化软件

每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。

下载
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号