Как сгенерировать рандомизированный список из последовательности чисел?

Question

Я хочу, чтобы функция генерировала список длины n, содержащий арифметику c последовательность чисел от 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]

В настоящее время он у меня есть, поэтому он генерирует последовательность чисел в одном l oop и случайном порядке в другом, следующим образом:

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> 1 000 000). Есть ли лучший способ написать этот код, или даже лучше, есть ли функция, которая может выполнить эту задачу для меня?

Answer 1

@ HeapOverflow предложил заменить второй l oop на функцию перемешивания:

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

, что на порядок быстрее, чем раньше. Из прошлого опыта я подозреваю, что функция pop в списках довольно медленная и была основным узким местом во втором l oop.

Answer 2

Во-первых, я хотел бы отметить, что главная причина плохой производительности вашего кода заключается в следующей строке:

myList.append(setList.pop(index))

Сложность времени list.pop в середине списка примерно O(n), так как щелчок из середины списка заставляет Python перемещать кучу памяти. Это делает net сложность 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

---

Для полноты вы можете go с векторизованным решением 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