Перетасовка ненулевых элементов каждой строки в массиве – Python / NumPy

Вы можете использовать не- numpy.random.permutation с явным ненулевым индексированием:

 >>> X = np.array([[2,3,1,0], [0,0,2,1]]) >>> for i in range(len(X)): ... idx = np.nonzero(X[i]) ... X[i][idx] = np.random.permutation(X[i][idx]) ... >>> X array([[3, 2, 1, 0], [0, 0, 2, 1]]) 

Кажется, я нашел три лайнера?

 i, j = np.nonzero(a.astype(bool)) k = np.argsort(i + np.random.rand(i.size)) a[i,j] = a[i,j[k]] 

Как и было обещано, это четвертый день щедрого периода, вот моя попытка векторизованного решения. Ниже описываются следующие шаги:

• Для облегчения ссылок назовем массив ввода как a . Создавайте уникальные индексы для каждой строки, которая охватывает диапазон длины строки. Для этого мы можем просто генерировать случайные числа той же формы, что и входной массив, и получать индексы argsort вдоль каждой строки, которые были бы этими уникальными индексами. Эта идея была изучена ранее в this post .

• Индекс в каждую строку входного массива с этими индексами в виде индексов столбцов. Таким образом, здесь нам понадобится advanced-indexing . Теперь это дает нам массив с перетасовкой каждой строки. Назовем это b .

• Поскольку перетасовка ограничена для каждой строки, если мы просто используем логическое индексирование: b[b!=0] , мы получим ненулевые элементы, которые будут перетасованы, а также будут ограничены длинами не-нулей в строке. Это связано с тем, что элементы в массиве NumPy хранятся в строчном порядке, поэтому при булевом индексировании он должен был выбрать перетасованные ненулевые элементы в каждой строке, прежде чем переходить к следующей строке. Опять же, если мы будем использовать логическое индексирование аналогично для a , т. Е. A a[a!=0] , мы бы так же получили ненулевые элементы в каждой строке, прежде чем переходить на следующую строку, и они будут в их первоначальном порядке. Итак, последним шагом было бы просто захватить маскированные элементы b[b!=0] и назначить в замаскированные места a[a!=0] .

Таким образом, реализация, охватывающая вышеупомянутые три этапа, будет заключаться в том,

 m,n = a.shape rand_idx = np.random.rand(m,n).argsort(axis=1) #step1 b = a[np.arange(m)[:,None], rand_idx] #step2 a[a!=0] = b[b!=0] #step3 

Примерный шаг за шагом может сделать вещи более ясными –

 In [50]: a # Input array Out[50]: array([[ 8, 5, 0, -4], [ 0, 6, 0, 3], [ 8, 5, 0, -4]]) In [51]: m,n = a.shape # Store shape information # Unique indices per row that covers the range for row length In [52]: rand_idx = np.random.rand(m,n).argsort(axis=1) In [53]: rand_idx Out[53]: array([[0, 2, 3, 1], [1, 0, 3, 2], [2, 3, 0, 1]]) # Get corresponding indexed array In [54]: b = a[np.arange(m)[:,None], rand_idx] # Do a check on the shuffling being restricted to per row In [55]: a[a!=0] Out[55]: array([ 8, 5, -4, 6, 3, 8, 5, -4]) In [56]: b[b!=0] Out[56]: array([ 8, -4, 5, 6, 3, -4, 8, 5]) # Finally do the assignment based on masking on a and b In [57]: a[a!=0] = b[b!=0] In [58]: a # Final verification on desired result Out[58]: array([[ 8, -4, 0, 5], [ 0, 6, 0, 3], [-4, 8, 0, 5]]) 

Бенчмаркинг для векторизованных решений

Мы стремимся к анализу векторизованных решений в этой статье. Теперь, векторизация пытается избежать цикла, который мы будем перебирать через каждую строку и делать перетасовку. Таким образом, настройка для входного массива включает большее количество строк.

Подходы –

 def app1(a): # @Daniel F's soln i, j = np.nonzero(a.astype(bool)) k = np.argsort(i + np.random.rand(i.size)) a[i,j] = a[i,j[k]] return a def app2(x): # @kazemakase's soln r, c = np.where(x != 0) n = c.size perm = np.random.permutation(n) i = np.argsort(perm + r * n) x[r, c] = x[r, c[i]] return x def app3(a): # @Divakar's soln m,n = a.shape rand_idx = np.random.rand(m,n).argsort(axis=1) b = a[np.arange(m)[:,None], rand_idx] a[a!=0] = b[b!=0] return a from scipy.ndimage.measurements import labeled_comprehension def app4(a): # @FabienP's soln def func(array, idx): r[idx] = np.random.permutation(array) return True labels, idx = nz = a.nonzero() r = a[nz] labeled_comprehension(a[nz], labels + 1, np.unique(labels + 1),\ func, int, 0, pass_positions=True) a[nz] = r return a 

Процедура сравнительного анализа №1

Для справедливого бенчмаркинга было разумным использовать образец OP и просто складывать их как больше строк, чтобы получить больший набор данных. Таким образом, с этой установкой мы могли бы создать два случая с наборами данных на 2 миллиона и 20 миллионов строк.

Случай №1: Большой набор данных с 2*1000,000 строк

 In [174]: a = np.array([[2,3,1,0],[0,0,2,1]]) In [175]: a = np.vstack([a]*1000000) In [176]: %timeit app1(a) ...: %timeit app2(a) ...: %timeit app3(a) ...: %timeit app4(a) ...: 1 loop, best of 3: 264 ms per loop 1 loop, best of 3: 422 ms per loop 1 loop, best of 3: 254 ms per loop 1 loop, best of 3: 14.3 s per loop 

Случай №2: более крупный набор данных с 2*10,000,000 строк

 In [177]: a = np.array([[2,3,1,0],[0,0,2,1]]) In [178]: a = np.vstack([a]*10000000) # app4 skipped here as it was slower on the previous smaller dataset In [179]: %timeit app1(a) ...: %timeit app2(a) ...: %timeit app3(a) ...: 1 loop, best of 3: 2.86 s per loop 1 loop, best of 3: 4.62 s per loop 1 loop, best of 3: 2.55 s per loop 

Процедура бенчмаркинга №2: Обширная

Чтобы охватить все случаи различной доли ненулей во входном массиве, мы рассмотрим некоторые обширные сценарии бенчмаркинга. Кроме того, поскольку app4 казался намного медленнее, чем другие, для более тщательной проверки мы пропускаем этот раздел в этом разделе.

Вспомогательная функция для настройки входного массива:

 def in_data(n_col, nnz_ratio): # max no. of elems that my system can handle, ie stretching it to limits. # The idea is to use this to decide the number of rows and always use # max. possible dataset size num_elem = 10000000 n_row = num_elem//n_col a = np.zeros((n_row, n_col),dtype=int) L = int(round(a.size*nnz_ratio)) a.ravel()[np.random.choice(a.size, L, replace=0)] = np.random.randint(1,6,L) return a 

Основной сценарий синхронизации и графика (использует магические функции IPython, поэтому нужно запустить opon-копирование и вставку на консоль IPython) –

 import matplotlib.pyplot as plt # Setup input params nnz_ratios = np.array([0.2, 0.4, 0.6, 0.8]) n_cols = np.array([4, 5, 8, 10, 15, 20, 25, 50]) init_arr1 = np.zeros((len(nnz_ratios), len(n_cols) )) init_arr2 = np.zeros((len(nnz_ratios), len(n_cols) )) init_arr3 = np.zeros((len(nnz_ratios), len(n_cols) )) timings = {app1:init_arr1, app2:init_arr2, app3:init_arr3} for i,nnz_ratio in enumerate(nnz_ratios): for j,n_col in enumerate(n_cols): a = in_data(n_col, nnz_ratio=nnz_ratio) for func in timings: res = %timeit -oq func(a) timings[func][i,j] = res.best print func.__name__, i, j, res.best fig = plt.figure(1) colors = ['b','k','r'] for i in range(len(nnz_ratios)): ax = plt.subplot(2,2,i+1) for f,func in enumerate(timings): ax.plot(n_cols, [time for time in timings[func][i]], label=str(func.__name__), color=colors[f]) ax.set_xlabel('No. of cols') ax.set_ylabel('time [seconds]') ax.grid(which='both') ax.legend() plt.tight_layout() plt.title('Percentage non-zeros : '+str(int(100*nnz_ratios[i])) + '%') plt.subplots_adjust(wspace=0.2, hspace=0.2) 

Выходные данные –

Наблюдения:

• Подходы # 1, # 2 делают argsort для ненулевых элементов во всем массиве ввода. Таким образом, он работает лучше с меньшим процентом ненулевых значений.

• Подход № 3 создает случайные числа той же формы, что и входной массив, а затем получает индексы argsort каждой строки. Таким образом, для заданного количества не нулей во входе тайминга для него более крутые, чем первые два подхода.

Вывод :

Подход №1, кажется, довольно хорошо работает до отметки 60%, отличной от нуля. Для большего количества ненулевых элементов, и если длина строк мала, подход # 3, кажется, работает прилично.

Я придумал это:

 nz = a.nonzero() # Get nonzero indexes a[nz] = np.random.permutation(a[nz]) # Shuffle nonzero values with mask 

Что выглядит проще (и немного быстрее?), Чем другие предлагаемые решения.

EDIT: новая версия, которая не смешивает строки

  labels, *idx = nz = a.nonzero() # get masks a[nz] = np.concatenate([np.random.permutation(a[nz][labels == i]) # permute values for i in np.unique(labels)]) # for each label 

Если в качестве меток используется первый массив a.nonzero() (индексы ненулевых значений в axis0). Это трюк, который не смешивает строки.

Затем np.random.permutation применяется a[a.nonzero()] для каждой «метки» независимо.

Предположительно scipy.ndimage.measurements.labeled_comprehension можно использовать здесь, поскольку он, похоже, терпит неудачу с np.random.permutation .

И я наконец увидел, что он очень похож на предложенный @randomir. Во всяком случае, это было просто для того, чтобы заставить его работать.

EDIT2:

Наконец, он работал с scipy.ndimage.measurements.labeled_comprehension

 def shuffle_rows(a): def func(array, idx): r[idx] = np.random.permutation(array) return True labels, *idx = nz = a.nonzero() r = a[nz] labeled_comprehension(a[nz], labels + 1, np.unique(labels + 1), func, int, 0, pass_positions=True) a[nz] = r return a 

Где:

1. func() перетасовывает ненулевые значения
2. labeled_comprehension применяет func() label-wise

Это заменяет предыдущий цикл for и будет быстрее на массивах со многими строками.

Это одна возможность для векторизованного решения:

 r, c = np.where(x > 0) n = c.size perm = np.random.permutation(n) i = np.argsort(perm + r * n) x[r, c] = x[r, c[i]] 

Задача в векторизации этой проблемы заключается в том, что np.random.permutation дает только плоские индексы, которые перетасовывают элементы массива по строкам. Сортировка перестановочных значений с добавленным смещением гарантирует, что перетасовка между строками не произойдет.

Вот ваш два лайнера без необходимости установки numpy.

 from random import random def shuffle_nonzeros(input_list): ''' returns a list with the non-zero values shuffled ''' shuffled_nonzero = iter(sorted((i for i in input_list if i!=0), key=lambda k: random())) print([i for i in (i if i==0 else next(shuffled_nonzero) for i in input_list)]) 

если вам не нравится один лайнер, вы можете сделать это генератором с

 def shuffle_nonzeros(input_list): ''' generator that yields a list with the non-zero values shuffled ''' random_nonzero_values = iter(sorted((i for i in input_list if i!=0), key=lambda k: random())) for i in iterable: if i==0: yield i else: yield next(random_nonzero_values) 

или если вы хотите, чтобы в качестве вывода был выбран список, и не хотелось бы использовать однострочное понимание

 def shuffle_nonzeros(input_list): ''' returns a list with the non-zero values shuffled ''' out = [] random_nonzero_values = iter(sorted((i for i in input_list if i!=0), key=lambda k: random())) for i in iterable: if i==0: out.append(i) else: out.append(next(random_nonzero_values)) return out