如何在Python中制作2**20个元素的几乎排序列表

Question

N=2**20我们构建列表，使A[i+1]=A[i]+random_value在[1，5]之间然后我们将N//20个元素移动到随机位置

到目前为止我的代码：

import random
N = pow(2, 20)
almostSortedArray = list(range(N))
elementsToShuffle = random.sample(range(N), k=N//20)
for i in elementsToShuffle:
j = random.choice([x for x in range(len(almostSortedArray)) if x not in elementsToShuffle])
almostSortedArray[i], almostSortedArray[j] = almostSortedArray[j], almostSortedArray[i]

它的迭代速度非常慢。。。没有任何解决方案。如何解决这个问题？

Answer 1

如果我正确理解问题，那么这可以与NumPy:一起使用

import numpy as np
from numpy.random import default_rng
N = 2**20
# Seed the random number generator
rng = default_rng()
diff = rng.integers(1, 6, size=N)
# Create an array with elements differing 1-5 for each next element
a = np.cumsum(diff)
# Create a set of random, but unique, indices
indices = rng.choice(np.arange(N), size=N//20, replace=False)
# Grab the corresponding values
values = a[indices]
# Shuffle the indices
rng.shuffle(indices)
# And set the values back into a, with the shuffled indices
a[indices] = values

作为参考，在我六岁的Macbook上，这花了大约25毫秒。

调用

a_sorted = np.sort(a)

大约需要20毫秒。

Answer 2

只计算一次j选项的池，并使用集合。然后它是线性时间，而不是三次。

import random
N = 2 ** 20
almostSortedArray = list(range(N))
elementsToShuffle = random.sample(range(N), k=N//20)
others = list(set(range(N)) - set(elementsToShuffle))
for i in elementsToShuffle:
j = random.choice(others)
almostSortedArray[i], almostSortedArray[j] = almostSortedArray[j], almostSortedArray[i]