如何在Python中高效生成含2**20元素的近乎有序列表？

原代码的核心问题 #

1. 初始数组不符合需求：你用list(range(N))生成的是连续整数数组，但实际要求是每个元素等于前一个元素加1-5的随机数，这是功能错误。
2. 交换逻辑效率极低：每次循环里生成[x for x in range(len(almostSortedArray)) if x not in elementsToShuffle]，这个操作要遍历整个数组，而且x not in elementsToShuffle是线性查找，循环近5万次的话，时间开销会非常大。

优化后的实现 #

1. 正确生成近似有序数组 #

用纯Python就能高效生成，时间复杂度O(N)：

import random

N = 2 ** 20
almost_sorted = [0] * N
for i in range(1, N):
    almost_sorted[i] = almost_sorted[i-1] + random.randint(1, 5)

如果追求更快的生成速度，可以用numpy（比纯Python快3-5倍）：

import numpy as np
import random

N = 2 ** 20
# 生成1-5的随机增量
deltas = np.random.randint(1, 6, size=N-1)
# 累加得到目标数组
almost_sorted = np.cumsum(np.concatenate([[0], deltas])).tolist()

2. 高效打乱指定元素 #

核心是提前一次性处理好所有要交换的索引对，避免重复的线性查找：

shuffle_count = N // 20
# 随机选要交换的元素索引
shuffle_indices = random.sample(range(N), k=shuffle_count)
# 转成set，让查找变成O(1)
shuffle_set = set(shuffle_indices)
# 生成所有不需要交换的索引
non_shuffle_indices = [x for x in range(N) if x not in shuffle_set]
# 从非交换索引里随机选对应数量的目标索引
target_indices = random.sample(non_shuffle_indices, k=shuffle_count)
# 一一配对交换
for src, dst in zip(shuffle_indices, target_indices):
    almost_sorted[src], almost_sorted[dst] = almost_sorted[dst], almost_sorted[src]

优化效果说明 #

• 初始数组生成阶段：从错误的连续数组改成符合规则的近似有序数组，同时保证O(N)的时间复杂度。
• 交换阶段：把原来每次循环O(N)的操作改成一次性O(N)预处理，加上O(k)的交换操作（k是要交换的元素数量），整体时间复杂度从O(N*k)降到O(N+k)，对于N=1e6级别的数据，速度提升会非常明显。

内容的提问来源于stack exchange，提问作者Mozart