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

Ответ 1

Вы можете использовать не-inplace 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]])

Ответ 2

Думаю, я нашел трехстрочный слой?

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

Ответ 3

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

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

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

• Так как перетасовка ограничена для каждой строки, если мы просто используем логическое индексирование: b[b!=0], мы получим ненулевые элементы, которые будут перетасованы, а также будут ограничены длинами не нулей в строке, Это связано с тем, что элементы в массиве NumPy хранятся в строчном порядке, поэтому при булевом индексировании он должен был выбрать перетасованные ненулевые элементы в каждой строке, прежде чем переходить к следующей строке. Опять же, если мы будем использовать булево-индексирование аналогично для 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]])

Ответ 4

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

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

Подходы -

def app1(a): # @Daniel F 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 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 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 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, i.e. 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

Основное время и построение графика script (Использует магические функции 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, по-видимому, выполняется прилично.

Ответ 5

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

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() (индексы ненулевых значений в оси 0). Это трюк, который не смешивает строки.

Затем 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

Где:

• func() перемещает ненулевые значения
• labeled_comprehension применяется func() label-wise

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

Ответ 6

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

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 дает только плоские индексы, которые перетасовывают элементы массива по строкам. Сортировка перестановочных значений с добавленным смещением гарантирует, что не происходит перетасовка между строками.

Ответ 7

Здесь два ваших лайнера, не требующих установки 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