np.shuffle намного медленнее, чем np.random.choice

Question

У меня есть массив формы (N, 3), и я хотел бы случайным образом перемешать строки.N составляет порядка 100 000.

Я обнаружил, что np.random.shuffle является узким местом моего приложения.Я попытался заменить shuffle вызовом np.random.choice и испытал ускорение в 10 раз.Что тут происходит?Почему так быстро вызывать np.random.choice?Создает ли версия np.random.choice равномерно распределенный случайный порядок?

import timeit

task_choice = '''
N = 100000
x = np.zeros((N, 3))
inds = np.random.choice(N, N, replace=False)
x[np.arange(N), :] = x[inds, :]
'''

task_shuffle = '''
N = 100000
x = np.zeros((N, 3))
np.random.shuffle(x)
'''

task_permute = '''
N = 100000
x = np.zeros((N, 3))
x = np.random.permutation(x)
'''

setup = 'import numpy as np'

timeit.timeit(task_choice, setup=setup, number=10)
>>> 0.11108078400138766

timeit.timeit(task_shuffle, setup=setup, number=10)
>>> 1.0411593900062144

timeit.timeit(task_permute, setup=setup, number=10)
>>> 1.1140159380011028

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

task_ind_permute = '''
N = 100000
x = np.zeros((N, 3))
inds = np.random.permutation(N)
x[np.arange(N), :] = x[inds, :]
'''

Answer 1

permutation и shuffle связаны, фактически permutation звонки shuffle под капотом !!

Причина, по которой shuffle медленнее, чем permutation для многомерного массива, заключается в том, что permutation нужно только shuffle индекс по первой оси. Таким образом, становится частным случаем shuffle массива 1d (1-й блок if-else).

Этот частный случай также объяснен в источнике:

# We trick gcc into providing a specialized implementation for
# the most common case, yielding a ~33% performance improvement.
# Note that apparently, only one branch can ever be specialized.

Для shuffle, с другой стороны, многомерная операция ndarray требует буфера возврата, создание этого буфера, особенно когда измерение относительно большое, становится дорогим. Кроме того, мы больше не можем использовать упомянутый выше трюк, который помогает в 1d случае.

С replace=False и использованием choice для генерации нового массива того же размера, choice и permutation одинаковы, см. здесь . Дополнительное время может потребоваться из-за затрат времени на создание промежуточных индексных массивов.

Answer 2

Здесь вы сравниваете очень массивы разных размеров. В вашем первом примере, хотя вы создаете массив нулей, вы просто используете random.choice(100000, 100000), который вытягивает 100000 случайных значений между 1-100000. Во втором примере вы перетасовываете массив (100000, 3).

>>> x.shape
(100000, 3)
>>> np.random.choice(N, N, replace=False).shape
(100000,)

Сроки на более эквивалентных образцах:

In [979]: %timeit np.random.choice(N, N, replace=False)
2.6 ms ± 201 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [980]: x = np.arange(100000)

In [981]: %timeit np.random.shuffle(x)
2.29 ms ± 67.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [982]: x.shape == np.random.choice(N, N, replace=False).shape
Out[982]: True