如何生成数字序列的随机列表？

Question

我想要一个函数来生成一个长度为n的列表，其中包含一个0到1之间的算术数字序列，但以随机顺序排列

例如，对于函数

def randSequence(n):
    ...
    return myList

randSequence(10)

返回

[0.5, 0.3, 0.9, 0.8, 0.6, 0.2, 0.4, 0.0, 0.1, 0.7]

及

randSequence(5)

返回

[0.4, 0.0, 0.2, 0.8, 0.6]

目前，我有它，它在一个循环中生成数字序列，并在另一个循环中随机化，如下所示：

def randSequence(n):
    step = 1 / n
    setList = []
    myList = []
    for i in range(n):
        setList.append(i * step)
    for i in range(n):
        index = random.randint(0, len(setList) - 1)
        myList.append(setList.pop(index))
    return myList

不幸的是，这个解决方案速度很慢，特别是对于大数字（如n>；1000000）。有没有更好的方法来编写这段代码，或者更好，有没有一个函数可以帮我完成这项任务

Answer 1

首先，我想指出，代码性能差的主要原因是这一行：

myList.append(setList.pop(index))

列表中间的时间复杂性list.pop大约为O(n)，因为从列表中间弹出会迫使Python移动大量内存。这使得网络的复杂性O(n^2)。您可以通过就地更改来大幅提高性能，例如：

def randSequenceInplace(n):
    'a.k.a. Fisher-Yates'
    step = 1 / n
    lst = [step * i for i in range(n)]
    for i in range(n-1):
        index = random.randint(i, n - 1)
        lst[i], lst[index] = lst[index], lst[i]
        # myList.append(setList.pop(index))
    return lst

---

为了完整性，您可以使用向量化的numpy解决方案，或者使用前面提到的random.shuffle来获得更好的性能。时间：

n = 10**6
%time randSequence(n)
# CPU times: user 1min 22s, sys: 33 ms, total: 1min 22s
# Wall time: 1min 22s
%time randSequenceInplace(n)
# CPU times: user 1.33 s, sys: 1.91 ms, total: 1.33 s
# Wall time: 1.33 s
%timeit np.random.permutation(n) / n
# 10 loops, best of 3: 22.4 ms per loop

Answer 2

@HeapOverflow建议将第二个循环替换为shuffle函数：

def randSequence(n):
    step = 1 / n
    myList = []
    for i in range(n):
        myList.append(i * step)
    random.shuffle(myList)
    return myList

这比以前快了一个数量级。根据过去的经验，我怀疑列表上的pop函数相当慢，是第二个循环中的主要瓶颈