为什么对原始数据进行排序会显着增加全遍历的生成时间？-Python教程-PHP中文网

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

花韻仙語

发布： 2025-03-18 11:04:01

原创

775人浏览过

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

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

在构建测试数据生成器时，我发现一个有趣的现象：对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中文网其它相关文章！