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]
它的迭代速度非常慢。。。没有任何解决方案。如何解决这个问题?
如果我正确理解问题,那么这可以与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毫秒。
只计算一次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]