tutorial - Mezclar elementos distintos de cero de cada fila en una matriz: Python/NumPy

transpuesta de una matriz en python numpy

Question

Tengo una matriz que es relativamente escasa, y me gustaría revisar cada fila y mezclar solo los elementos distintos de cero.

Ejemplo de entrada:

[2,3,1,0]
[0,0,2,1]

Ejemplo de salida:

[2,1,3,0]
[0,0,1,2]

Observe cómo los ceros no han cambiado de posición.

Para barajar todos los elementos en cada fila (incluidos los ceros), puedo hacer esto:

for i in range(len(X)):
    np.random.shuffle(X[i, :])

Lo que intenté hacer entonces es esto:

for i in range(len(X)):
    np.random.shuffle(X[i, np.nonzero(X[i, :])])

Pero no tiene ningún efecto. Me he dado cuenta de que el tipo de retorno de X[i, np.nonzero(X[i, :])] es diferente de X[i, :] X[i, np.nonzero(X[i, :])] X[i, :] que podría ser la causa.

In[30]: X[i, np.nonzero(X[i, :])]
Out[30]: array([[23,  5, 29, 11, 17]])

In[31]: X[i, :]
Out[31]: array([23,  5, 29, 11, 17])

Answer 1

Benchmarking para las soluciones vectorizadas

Buscamos soluciones vectorizadas de referencia en esta publicación. Ahora, la vectorización intenta evitar el bucle que recorremos cada fila y hacemos la mezcla. Por lo tanto, la configuración de la matriz de entrada implica un mayor número de filas.

Enfoques -

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

Procedimiento de evaluación comparativa n.º 1

Para una evaluación comparativa justa, parecía razonable usar la muestra de OP y simplemente apilarlas como más filas para obtener un conjunto de datos más grande. Por lo tanto, con esa configuración podríamos crear dos casos con conjuntos de datos de 2 millones y 20 millones de filas.

Caso # 1: conjunto de datos grandes con 2*1000,000 filas

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

Caso # 2: conjunto de datos más grande con 2*10,000,000 filas

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

Procedimiento de evaluación comparativa n.º 2: extenso

Para cubrir todos los casos de porcentaje variable de no ceros en la matriz de entrada, cubrimos algunos escenarios extensivos de evaluación comparativa. Además, dado que la app4 parecía mucho más lenta que otras, para una inspección más cercana nos salteamos esa en esta sección.

Función auxiliar para configurar la matriz de entrada:

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

Secuencia de comandos principal y trazado de guiones (utiliza las funciones mágicas de IPython. Por lo tanto, debe ejecutarse para copiar y pegar en la consola 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)

Salida de tiempos -

Observaciones:

• Enfoques n. ° 1, n. ° 2 argsort en elementos distintos de cero en toda la matriz de entrada. Como tal, funciona mejor con un menor porcentaje de no ceros.

• El enfoque # 3 crea números aleatorios de la misma forma que la matriz de entrada y luego obtiene índices argsort por fila. Por lo tanto, para un número dado de no ceros en la entrada, los tiempos son más pronunciados que los primeros dos enfoques.

Conclusión

El Enfoque N. ° 1 parece estar funcionando bastante bien hasta el 60% de la marca que no es cero. Para más no ceros y si las longitudes de las filas son pequeñas, el enfoque # 3 parece estar funcionando decentemente.

Answer 2

Aquí está su dos líneas sin necesidad de instalar 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)])

Sin embargo, si no te gustan los revestimientos, puedes hacer de esto un generador con

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)

o si quiere una lista como resultado, y no le gustan las comprensiones de una línea

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

Answer 3

Como prometí, siendo este el cuarto día del período de recompensa, aquí está mi intento de una solución vectorizada. Los pasos involucrados se explican en algunos detalles a continuación:

• Para referencia fácil, llamemos a la matriz de entrada como a . Genere índices únicos por fila que cubra el rango para la longitud de fila. Para esto, simplemente podemos generar números aleatorios de la misma forma que la matriz de entrada y obtener los índices argsort largo de cada fila, que serían esos índices únicos. Esta idea ha sido explorada antes en this post .

• Indexe en cada fila de matriz de entrada con esos índices como índices de columnas. Por lo tanto, necesitaríamos advanced-indexing aquí. Ahora, esto nos da una matriz con cada fila barajada. Vamos a llamarlo b .

• Dado que la mezcla se restringe a por fila, si simplemente utilizamos boolean-indexing: b[b!=0] , obtendríamos los elementos distintos de cero que se barajan y también se restringen a longitudes de no ceros por fila. Esto se debe al hecho de que los elementos en una matriz NumPy están almacenados en orden mayor de fila, por lo que con la indexación booleana habría seleccionado elementos mezclados distintos de cero en cada fila antes de pasar a la siguiente fila. De nuevo, si usamos boolean-indexing de manera similar para a , es decir, a[a!=0] , habríamos obtenido los elementos distintos de cero en cada fila primero antes de pasar a la siguiente fila y estos estarían en su orden original. Entonces, el último paso sería simplemente tomar elementos enmascarados b[b!=0] y asignar a los lugares enmascarados a[a!=0] .

Por lo tanto, una implementación que cubra los tres pasos mencionados anteriormente sería:

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 

Un ejemplo de ejecución paso a paso podría aclarar las cosas:

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]])

Answer 4

Creo que encontré el trineo?

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

Answer 5

Esta es una posibilidad para una solución vectorizada:

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]]

El desafío de vectorizar este problema es que np.random.permutation proporciona solo índices planos, que mezclarían los elementos de la matriz en filas. La ordenación de los valores permutados con un desplazamiento agregado garantiza que no se produzca ninguna mezcla entre filas.

Answer 6

Puede usar la función numpy.random.permutation no está en el numpy.random.permutation con numpy.random.permutation explícita distinta de cero:

>>> 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]])

Answer 7

Se me ocurrió eso:

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

¿Qué aspecto más simple (y un poco más rápido?) Que otras soluciones propuestas.

EDITAR: nueva versión que no mezcla filas

 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

Donde la primera matriz de a.nonzero() (índices de valores distintos de cero en axis0) se usa como etiquetas. Este es el truco que no mezcla filas.

Entonces np.random.permutation se aplica en a[a.nonzero()] para cada "etiqueta" de forma independiente.

Supuestamente scipy.ndimage.measurements.labeled_comprehension se puede usar aquí, ya que parece fallar con np.random.permutation .

Y finalmente vi que se parece mucho a lo que @randomir propuso. De todos modos, fue solo por el desafío de hacer que funcione.

EDIT2:

Finalmente lo conseguí trabajando con 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

Dónde:

1. func() mezcla los valores distintos de cero
2. labeled_comprehension aplica func() label-wise

Esto reemplaza el ciclo for anterior y será más rápido en las matrices con muchas filas.