python - norma - ¿Cuál es la diferencia entre matrices contiguas y no contiguas?

norma de una matriz en python

Question

En el manual numpy sobre la función reshape (), dice

>>> a = np.zeros((10, 2))
# A transpose make the array non-contiguous
>>> b = a.T
# Taking a view makes it possible to modify the shape without modifying the
# initial object.
>>> c = b.view()
>>> c.shape = (20)
AttributeError: incompatible shape for a non-contiguous array

Mis preguntas son:

1. ¿Qué son arreglos continuos y no contiguos? ¿Es similar al bloque de memoria contiguo en C like ¿Qué es un bloque de memoria contiguo?
2. ¿Hay alguna diferencia de rendimiento entre estos dos? ¿Cuándo deberíamos usar uno u otro?
3. ¿Por qué la transposición hace que la matriz no sea contigua?
4. ¿Por qué c.shape = (20) arroja una forma de error incompatible shape for a non-contiguous array ?

¡Gracias por tu respuesta!

Answer 1

Tal vez este ejemplo con 12 diferentes valores de matriz ayude:

In [207]: x=np.arange(12).reshape(3,4).copy()
In [208]: x.flags
Out[208]:
C_CONTIGUOUS : True
F_CONTIGUOUS : False
OWNDATA : True
...
In [209]: x.T.flags
Out[209]:
C_CONTIGUOUS : False
F_CONTIGUOUS : True
OWNDATA : False
...

Los valores de C order están en el orden en que se generaron. Los transpuestos no son

In [212]: x.reshape(12,) # same as x.ravel()
Out[212]: array([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
In [213]: x.T.reshape(12,)
Out[213]: array([ 0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11])

Puede obtener 1d vistas de ambos

In [214]: x1=x.T
In [217]: x.shape=(12,)

la forma de x también se puede cambiar.

In [220]: x1.shape=(12,)
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
<ipython-input-220-cf2b1a308253> in <module>()
----> 1 x1.shape=(12,)
AttributeError: incompatible shape for a non-contiguous array

Pero la forma de la transposición no se puede cambiar. Los data están todavía en el orden de 0,1,2,3,4... , a los que no se puede acceder accediendo como 0,4,8... en una matriz de 1d.

Pero una copia de x1 se puede cambiar:

In [227]: x2=x1.copy()
In [228]: x2.flags
Out[228]:
C_CONTIGUOUS : True
F_CONTIGUOUS : False
OWNDATA : True
...
In [229]: x2.shape=(12,)

Ver los strides también podría ayudar. Un paso adelante es qué tan lejos (en bytes) tiene que pasar para llegar al siguiente valor. Para una matriz 2d, habrá 2 valores de zancada:

In [233]: x=np.arange(12).reshape(3,4).copy()
In [234]: x.strides
Out[234]: (16, 4)

Para llegar a la siguiente fila, paso 16 bytes, la siguiente columna solo 4.

In [235]: x1.strides
Out[235]: (4, 16)

Transpose simplemente cambia el orden de los pasos. La siguiente fila es solo de 4 bytes, es decir, el próximo número.

In [236]: x.shape=(12,)
In [237]: x.strides
Out[237]: (4,)

Cambiar la forma también cambia las zancadas: simplemente recorre el búfer 4 bytes a la vez.

In [238]: x2=x1.copy()
In [239]: x2.strides
Out[239]: (12, 4)

Aunque x2 tiene el mismo aspecto que x1 , tiene su propio búfer de datos, con los valores en un orden diferente. La siguiente columna ahora tiene 4 bytes, mientras que la siguiente fila es 12 (3 * 4).

In [240]: x2.shape=(12,)
In [241]: x2.strides
Out[241]: (4,)

Y al igual que con x , cambiar la forma a 1d reduce los pasos a (4,) .

Para x1 , con datos en el orden de 0,1,2,... , no hay un paso 1d que dé 0,4,8...

__array_interface__ es otra forma útil de mostrar información de matriz:

In [242]: x1.__array_interface__
Out[242]:
{''strides'': (4, 16),
''typestr'': ''<i4'',
''shape'': (4, 3),
''version'': 3,
''data'': (163336056, False),
''descr'': [('''', ''<i4'')]}

La dirección del búfer de datos x1 será la misma que para x , con la que comparte los datos. x2 tiene una dirección de búfer diferente.

También podría experimentar agregando un parámetro order=''F'' a los comandos copy y reshape .

Answer 2

Una matriz contigua es simplemente una matriz almacenada en un bloque continuo de memoria: para acceder al siguiente valor en la matriz, simplemente pasamos a la siguiente dirección de memoria.

Considere la matriz 2D arr = np.arange(12).reshape(3,4) . Se parece a esto:

En la memoria de la computadora, los valores de arr se almacenan así:

Esto significa que arr es una matriz contigua C porque las filas se almacenan como bloques contiguos de memoria. La siguiente dirección de memoria contiene el siguiente valor de fila en esa fila. Si queremos movernos hacia abajo en una columna, solo tenemos que saltar tres bloques (por ejemplo, saltar de 0 a 4 significa que omitimos 1,2 y 3).

La transposición de la matriz con arr.T significa que la contigüidad C se pierde porque las entradas de fila adyacentes ya no se encuentran en direcciones de memoria adyacentes. Sin embargo, arr.T es Fortran contiguo ya que las columnas están en bloques contiguos de memoria:

En términos de rendimiento, acceder a las direcciones de memoria que están una al lado de la otra suele ser más rápido que acceder a direcciones que están más "dispersas" (recuperar un valor de la RAM podría implicar que se busquen y almacenen en caché varias direcciones vecinas para la CPU). significa que las operaciones sobre matrices contiguas a menudo serán más rápidas.

Como consecuencia del diseño de memoria contigua de C, las operaciones en filas suelen ser más rápidas que las operaciones en columnas. Por ejemplo, típicamente encontrará que

np.sum(arr, axis=1) # sum the rows

es ligeramente más rápido que:

np.sum(arr, axis=0) # sum the columns

De forma similar, las operaciones en columnas serán ligeramente más rápidas para las matrices contiguas de Fortran.

Finalmente, ¿por qué no podemos aplanar la matriz contigua de Fortran asignando una nueva forma?

>>> arr2 = arr.T
>>> arr2.shape = 12
AttributeError: incompatible shape for a non-contiguous array

Para que esto sea posible, NumPy tendría que juntar las filas de arr.T así:

(La configuración del atributo de shape asume directamente el orden C, es decir, NumPy intenta realizar la operación en filas).

Esto es imposible de hacer Para cualquier eje, NumPy necesita tener una longitud de zancada constante (la cantidad de bytes para moverse) para llegar al siguiente elemento de la matriz. El arr.T de esta manera requeriría saltar hacia delante y hacia atrás en la memoria para recuperar valores consecutivos de la matriz.

Si arr2.reshape(12) lugar, NumPy copiaría los valores de arr2 en un nuevo bloque de memoria (ya que no puede devolver una vista a los datos originales para esta forma).