multiplicar - que es un array en python

La conversión de la matriz NumPy a un conjunto lleva demasiado tiempo

Question

Estoy tratando de ejecutar lo siguiente

from numpy import *
x = array([[3,2,3],[711,4,104],.........,[4,4,782,7845]])  # large nparray
for item in x:
    set(item)

y lleva mucho tiempo en comparación con:

x = array([[3,2,3],[711,4,104],.........,[4,4,782,7845]])  # large nparray
for item in x:
    item.tolist()

¿Por qué tarda mucho más tiempo convertir una matriz NumPy en un set que en una list ? Quiero decir, básicamente ambos tienen complejidad O(n) ?

Answer 1

TL; DR: set basa en el protocolo de iteración de Pythons, pero iterar en las matrices es una operación bastante lenta. tolist() puede evitar la iteración python y, por lo tanto, es más rápido.

Para comprender la razón por la cual las iteraciones sobre las matrices son lentas, necesita saber cómo se almacenan en la memoria los objetos, las listas y las matrices (numpy) de Python.

Un objeto Python tiene algunas propiedades de contabilidad (recuento de referencia + enlace a su clase, ...) y el valor que representa, por ejemplo, el número entero de ten = 10 podría verse así:

┌─────┐          ┌──────┐
│ ten │          │ int  │
├─────┤          ├──────┤
│  ────────────> │  10  │
└─────┘          └──────┘

El objeto izquierdo es lo que usa en el intérprete de Python como la variable ten y el objeto correcto (instancia) es lo que realmente representa el número entero.

Una list es solo una colección de objetos "guardados", por ejemplo mylist = [1, 2, 3] guardaría así:

┌────────┐                ┌───────────┐
│ mylist │                │   list    │
├────────┤                ├───────────┤
│    ───────────────────> │ 0 | 1 | 2 │   <--- these are indices (not values)
└────────┘                └─│───│───│─┘
                            │   │   │
                            │   │   │
                   ┌────────┘   │   └────────┐
                   │            │            │
                   │            │            │
                ┌─────┐      ┌─────┐      ┌─────┐
                │ int │      │ int │      │ int │
                ├─────┤      ├─────┤      ├─────┤
                │  1  │      │  2  │      │  3  │
                └─────┘      └─────┘      └─────┘

Esta vez, la lista hace referencia a los enteros 1 , 2 y 3 y mylist solo hace referencia a la instancia de la list .

Pero una matriz myarray = np.array([1, 2, 3]) no necesita objetos de Python para los elementos:

┌─────────┐          ┌───────────┐
│ myarray │          │   array   │
├─────────┤          ├───────────┤
│    ──────────────> │ 1 | 2 | 3 │
└─────────┘          └───────────┘

Los valores 1 , 2 y 3 se almacenan directamente en el objeto de la array .

Con esta información puedo explicar por qué una iteración (Python) sobre una array es más lenta en comparación con una iteración sobre una list :

Cada vez que accede al siguiente elemento de una list la list simplemente devuelve el objeto que es bastante rápido porque el elemento ya existe como objeto python (solo necesita aumentar el recuento de referencias en uno). Por otro lado, cuando quiere el siguiente elemento de una array , necesita crear una nueva "caja" para el valor con todas las cosas de contabilidad antes de que se devuelva. Uno para cada elemento en su matriz:

first item     second item      third item
 ┌─────┐         ┌─────┐          ┌─────┐
 │ int │         │ int │          │ int │
 ├─────┤         ├─────┤          ├─────┤
 │  1  │         │  2  │          │  3  │
 └─────┘         └─────┘          └─────┘

La "creación de estos cuadros" es lenta y, por lo tanto, la razón principal por la que iterar sobre las matrices es mucho más lenta que iterar sobre listas / tuplas / conjuntos / diccionarios que almacenan los valores y su cuadro:

import numpy as np
arr = np.arange(100000)
lst = list(range(100000))

def iterateover(obj):
    for item in obj:
        pass

%timeit iterateover(arr)
# 20.2 ms ± 155 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit iterateover(lst)
# 3.96 ms ± 26.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Los constructores normales set , list , ... simplemente harán una iteración sobre el objeto.

Una cosa que no puedo responder definitivamente es por qué tolist es más rápido. Supongo que es porque no necesita llamar a la función de "boxeo" para cada elemento, sino que lo hace sobre la marcha. Pero eso es solo una suposición porque al final cada valor debe estar en un "cuadro de Python" en una lista de Python, por lo que no hay mucho trabajo que tolist pueda evitar. Pero una cosa que sé con certeza es que list(array) es más lenta que array.tolist() :

arr = np.arange(100000)

%timeit list(arr)
# 20 ms ± 114 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit arr.tolist()
# 10.3 ms ± 253 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Cada uno de estos tiene una complejidad de tiempo de ejecución O(n) pero los factores constantes son muy diferentes.

En su caso, comparó set() con tolist() , lo que no es una buena comparación en particular. Tendría más sentido comparar set(arr) con list(arr) o set(arr.tolist()) con arr.tolist() :

arr = np.random.randint(0, 1000, (10000, 3))

def tosets(arr):
    for line in arr:
        set(line)

def tolists(arr):
    for line in arr:
        list(line)

def tolists_method(arr):
    for line in arr:
        line.tolist()

def tosets_intermediatelist(arr):
    for line in arr:
        set(line.tolist())

%timeit tosets(arr)
# 72.2 ms ± 2.68 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit tolists(arr)
# 80.5 ms ± 2.18 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit tolists_method(arr)
# 16.3 ms ± 140 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit tosets_intermediatelist(arr)
# 38.5 ms ± 200 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Entonces, si quieres set s, es mejor que set(arr.tolist()) . Para arreglos más grandes, tendría sentido usar np.unique pero debido a que las filas solo contienen 3 elementos que serán más lentos (¡para miles de elementos, sería mucho más rápido!).

En los comentarios que preguntaste sobre numba y sí, es cierto que numba podría acelerar esto. Numba admite conjuntos tipeados (pero solo para tipos numéricos) , pero eso no significa que siempre será más rápido.

No estoy seguro de cómo numba (re) implementa s, pero como están escritos, es probable que eviten las "cajas" y almacenen los objetos dentro del set :

┌─────────┐          ┌─────────────┐
│  myset  │          │   numbaset  │
├─────────┤          ├─────────────┤
│    ──────────────> │ hash(1) | 1 │ 
└─────────┘          ├─────────────┤
                     │ hash(2) | 2 │ 
                     ├─────────────┤ 
                     │ hash(3) | 3 │ 
                     ├─────────────┤ 
                     │    -    | - │ 
                     ├─────────────┤ 
                     │    -    | - │ 
                     └─────────────┘

Los conjuntos son más complicados que los de la list porque implican hash es y slots vacíos (asumiendo direcciones abiertas como lo hace python, los slots vacíos están representados por - ). Al igual que la array NumPy, el set numba puede guardar los valores directamente. De esta manera, no necesita involucrar las "cajas" cuando convierte una matriz numpy en un conjunto numba ("rendimiento óptimo").

Por lo tanto, cuando crea el set en una función numba nopython y opera en él, tendrá una creación de conjunto muy eficiente y establecerá operaciones:

import numba as nb
@nb.njit
def tosets_numba(arr):
    for lineno in range(arr.shape[0]):
        set(arr[lineno])

tosets_numba(arr)  # warmup
%timeit tosets_numba(arr)
# 6.55 ms ± 105 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Eso es ~ 5 veces más rápido que el set(tolist()) . Pero es importante resaltar que no devolví el set s. Cuando devuelve el conjunto de una función nupy nopython a python, tiene que crear un conjunto python, que incluye "crear las casillas" para todos los valores del conjunto (eso es algo que numba está ocultando).

┌─────────┐          ┌─────────────┐               ┌─────┐
│  myset  │          │  pythonset  │               │ int │ 
├─────────┤          ├─────────────┤               ├─────┤
│    ──────────────> │ hash(1) | ──────────────>   │  1  │
└─────────┘          ├─────────────┤               └─────┘
                     │ hash(2) | ────────────┐ 
                     ├─────────────┤         │     ┌─────┐
                     │ hash(3) | ────────┐   │     │ int │ 
                     ├─────────────┤     │   └─>   ├─────┤
                     │    -    | - │     │         │  2  │
                     ├─────────────┤     │         └─────┘
                     │    -    | - │     │
                     └─────────────┘     │         ┌─────┐
                                         │         │ int │
                                         └─────>   ├─────┤
                                                   │  3  │
                                                   └─────┘

Supongo que si devuelve estos conjuntos de la función (no es realmente posible en este momento porque numba no admite listas de conjuntos actualmente) sería más lento (porque crea un conjunto numba y luego lo convierte en un conjunto de Python) o solo marginalmente más rápido (si la conversión numbaset -> pittonset es realmente muy rápida).

Personalmente, utilizaría numba para los conjuntos solo si no necesito devolverlos desde la función y realizar todas las operaciones en el conjunto dentro de la función y solo si todas las operaciones en el conjunto son compatibles con el modo nopython. En cualquier otro caso, no usaría numba aquí.

Solo una nota: from numpy import * debe evitarse, ocultas varias funciones incorporadas de python cuando haces eso ( sum , min , max , ...) y pone muchas cosas en tus globales. Es mejor usar import numpy as np . El np. frente a las llamadas de función hace que el código sea más claro y no hay mucho que escribir.