python - functions - Eficiente Numpy construcción de matriz 2D de matriz 1D

numpy python 3.6 windows

Question

Tengo una matriz como esta:

A = array([1,2,3,4,5,6,7,8,9,10])

Y estoy tratando de obtener una matriz como esta:

B = array([[1,2,3],
          [2,3,4],
          [3,4,5],
          [4,5,6]])

Donde cada fila (de un ancho arbitrario fijo) se desplaza en uno. La matriz de A tiene 10k registros y estoy tratando de encontrar una manera eficiente de hacerlo en Numpy. Actualmente estoy usando vstack y un bucle for que es lento. ¿Hay una manera mas rápida?

Editar:

width = 3 # fixed arbitrary width
length = 10000 # length of A which I wish to use
B = A[0:length + 1]
for i in range (1, length):
    B = np.vstack((B, A[i, i + width + 1]))

Answer 1

¿Qué enfoque estás usando?

import numpy as np
A = np.array([1,2,3,4,5,6,7,8,9,10])
width = 3

np.vstack([A[i:i-len(A)+width] for i in xrange(len(A)-width)])
# needs 26.3µs

np.vstack([A[i:i-width] for i in xrange(width)]).T
# needs 13.2µs

Si su ancho es relativamente bajo (3) y tiene una A grande (10000 elementos), la diferencia es aún más importante: 32.4ms para el primero y 44μs para el segundo.

Answer 2

Creo que esto podría ser más rápido que el bucle, cuando el ancho se fija en un número bajo ...

import numpy
a = numpy.array([1,2,3,4,5,6])
b = numpy.reshape(a, (numpy.shape(a)[0],1))
b = numpy.concatenate((b, numpy.roll(b,-1,0), numpy.roll(b,-2,0)), 1)
b = b[0:(numpy.shape(a)[0]/2) + 1,:]

EDITAR Claramente, las soluciones que usan zancadas son superiores a esto, con la única gran desventaja de que aún no están bien documentadas ...

Answer 3

De hecho, hay una forma aún más eficiente de hacerlo ... La desventaja de usar vstack , etc., es que estás haciendo una copia de la matriz.

Por cierto, esto es efectivamente idéntico a la respuesta de @ Paul, pero estoy publicando esto solo para explicar las cosas con un poco más de detalle ...

Hay una forma de hacerlo con solo vistas para que no haya memoria duplicada.

Estoy tomando prestado directamente de la publicación de Erik Rigtorp a la discusión numpy , que a su vez, lo tomó prestado del Bottleneck de Keith Goodman (¡lo cual es bastante útil!).

El truco básico es manipular directamente los pasos del conjunto (para matrices unidimensionales):

import numpy as np

def rolling(a, window):
    shape = (a.size - window + 1, window)
    strides = (a.itemsize, a.itemsize)
    return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)

a = np.arange(10)
print rolling(a, 3)

Donde a es su matriz de entrada y window es la longitud de la ventana que desea (3, en su caso).

Esto produce:

[[0 1 2]
 [1 2 3]
 [2 3 4]
 [3 4 5]
 [4 5 6]
 [5 6 7]
 [6 7 8]
 [7 8 9]]

Sin embargo, no hay absolutamente ninguna duplicación de memoria entre la a original y la matriz devuelta. Esto significa que es rápido y escala mucho mejor que otras opciones.

Por ejemplo (usando a = np.arange(100000) y window=3 ):

%timeit np.vstack([a[i:i-window] for i in xrange(window)]).T
1000 loops, best of 3: 256 us per loop

%timeit rolling(a, window)
100000 loops, best of 3: 12 us per loop

Si generalizamos esto en una "ventana rodante" a lo largo del último eje para una matriz N-dimensional, obtenemos la función "ventana móvil" de Erik Rigtorp:

import numpy as np

def rolling_window(a, window):
   """
   Make an ndarray with a rolling window of the last dimension

   Parameters
   ----------
   a : array_like
       Array to add rolling window to
   window : int
       Size of rolling window

   Returns
   -------
   Array that is a view of the original array with a added dimension
   of size w.

   Examples
   --------
   >>> x=np.arange(10).reshape((2,5))
   >>> rolling_window(x, 3)
   array([[[0, 1, 2], [1, 2, 3], [2, 3, 4]],
          [[5, 6, 7], [6, 7, 8], [7, 8, 9]]])

   Calculate rolling mean of last dimension:
   >>> np.mean(rolling_window(x, 3), -1)
   array([[ 1.,  2.,  3.],
          [ 6.,  7.,  8.]])

   """
   if window < 1:
       raise ValueError, "`window` must be at least 1."
   if window > a.shape[-1]:
       raise ValueError, "`window` is too long."
   shape = a.shape[:-1] + (a.shape[-1] - window + 1, window)
   strides = a.strides + (a.strides[-1],)
   return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)

Entonces, veamos qué está pasando aquí ... Manipular los strides una serie puede parecer un poco mágico, pero una vez que entiendes lo que está pasando, no es para nada. Los pasos de una matriz numpy describen el tamaño en bytes de los pasos que se deben seguir para incrementar un valor a lo largo de un eje dado. Por lo tanto, en el caso de una matriz unidimensional de flotantes de 64 bits, la longitud de cada elemento es de 8 bytes y x.strides es (8,) .

x = np.arange(9)
print x.strides

Ahora, si reformamos esto en una matriz 2D, 3x3, los pasos serán (3 * 8, 8) , ya que tendríamos que saltar 24 bytes para incrementar un paso a lo largo del primer eje, y 8 bytes para incrementar un paso a lo largo el segundo eje.

y = x.reshape(3,3)
print y.strides

De manera similar, una transposición es lo mismo que invertir los pasos de una matriz:

print y
y.strides = y.strides[::-1]
print y

Claramente, los pasos de una matriz y la forma de una matriz están íntimamente relacionados. Si cambiamos uno, tenemos que cambiar el otro en consecuencia, de lo contrario no tendremos una descripción válida del búfer de memoria que realmente contiene los valores de la matriz.

Por lo tanto, si desea cambiar la forma y el tamaño de una matriz simultáneamente, no puede hacerlo simplemente configurando x.strides y x.shape , incluso si las nuevas zancadas y la forma son compatibles.

Ahí es donde entra numpy.lib.as_strided . En realidad, es una función muy simple que simplemente establece los pasos y la forma de una matriz de forma simultánea.

Comprueba que los dos son compatibles, pero no que los pasos anteriores y la nueva forma sean compatibles, como sucedería si configuras los dos de forma independiente. (En realidad lo hace a través de __array_interface__ de __array_interface__ , que permite que clases arbitrarias describan un búfer de memoria como un conjunto numpy).

Por lo tanto, todo lo que hemos hecho es hacerlo de modo que los pasos adelante un elemento (8 bytes en el caso de una matriz de 64 bits) a lo largo de un eje, pero también solo pasos de 8 bytes hacia adelante a lo largo del otro eje .

En otras palabras, en el caso de un tamaño de "ventana" de 3, la matriz tiene una forma de (whatever, 3) , pero en lugar de pisar 3 * x.itemsize para la segunda dimensión, solo avanza un elemento hacia adelante , efectivamente haciendo que las filas de una nueva matriz sean una vista de "ventana móvil" dentro de la matriz original.

(Esto también significa que x.shape[0] * x.shape[1] no será lo mismo que x.size para su nueva matriz).

En cualquier caso, con suerte eso aclara un poco las cosas ...

Answer 4

Eche un vistazo a: view_as_windows .

import numpy as np
from skimage.util.shape import view_as_windows
window_shape = (4, )
aa = np.arange(1000000000) # 1 billion
bb = view_as_windows(aa, window_shape)

Alrededor de 1 segundo.

Answer 5

Esta solución no se implementa de manera eficiente mediante un ciclo de Python, ya que incluye todo tipo de control de tipo que se evita mejor cuando se trabaja con matrices numpy. Si su matriz es excepcionalmente alta, notará una gran velocidad con esto:

newshape = (4,3)
newstrides = (A.itemsize, A.itemsize)
B = numpy.lib.stride_tricks.as_strided(A, shape=newshape, strides=newstrides)

Esto le da una vista de la matriz A. Si quiere una nueva matriz, puede editar, hacer lo mismo pero con .copy() al final.

Detalles sobre los avances:

La tupla de las newstrides en este caso será (4, 4) porque la matriz tiene elementos de 4 bytes y desea continuar el paso por sus datos en pasos de elementos individuales en la dimensión i. El segundo valor ''4'' se refiere a las zancadas en la dimensión j (en una matriz 4x4 normal sería 16). Porque en este caso también desea incrementar su lectura desde el búfer en pasos de 4 bytes en la dimensión j.

Joe da una descripción agradable y detallada y deja las cosas claras cuando dice que todo lo que hace este truco es cambiar zancadas y forma simultáneamente.

Answer 6

Estoy usando una función más general similar a la de @JustInTime, pero aplicable a ndarray

def sliding_window(x, size, overlap=0):
    step = size - overlap # in npts
    nwin = (x.shape[-1]-size)//step + 1
    shape = x.shape[:-1] + (nwin, size)
    strides = x.strides[:-1] + (step*x.strides[-1], x.strides[-1])
    return stride_tricks.as_strided(x, shape=shape, strides=strides)

Un ejemplo,

x = np.arange(10)
M.sliding_window(x, 5, 3)
Out[1]: 
array([[0, 1, 2, 3, 4],
       [2, 3, 4, 5, 6],
       [4, 5, 6, 7, 8]])


x = np.arange(10).reshape((2,5))
M.sliding_window(x, 3, 1)
Out[2]: 
array([[[0, 1, 2],
        [2, 3, 4]],

       [[5, 6, 7],
        [7, 8, 9]]])

Answer 7

Solo para seguir con la respuesta de @Joe general

import numpy as np
def rolling(a, window):
    step = 2 
    shape = ( (a.size-window)/step + 1   , window)


    strides = (a.itemsize*step, a.itemsize)

    return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)

a = np.arange(10)

print rolling(a, 3)

qué salidas:

[[0 1 2]
 [2 3 4]
 [4 5 6]
 [6 7 8]]

Para generalizar aún más para el caso 2d, es decir, usarlo para la extracción de parches de una imagen

def rolling2d(a,win_h,win_w,step_h,step_w):

    h,w = a.shape
    shape = ( ((h-win_h)/step_h + 1)  * ((w-win_w)/step_w + 1) , win_h , win_w)

    strides = (step_w*a.itemsize, h*a.itemsize,a.itemsize)


    return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)

a = np.arange(36).reshape(6,6)
print a
print rolling2d (a,3,3,2,2)

qué salidas:

[[ 0  1  2  3  4  5]
 [ 6  7  8  9 10 11]
 [12 13 14 15 16 17]
 [18 19 20 21 22 23]
 [24 25 26 27 28 29]
 [30 31 32 33 34 35]]
[[[ 0  1  2]
  [ 6  7  8]
  [12 13 14]]

 [[ 2  3  4]
  [ 8  9 10]
  [14 15 16]]

 [[ 4  5  6]
  [10 11 12]
  [16 17 18]]

 [[ 6  7  8]
  [12 13 14]
  [18 19 20]]]