Cree una matriz numpy con múltiples rangos de índice personalizados sin bucle explícito

En Numpy, ¿hay una forma en pythonic de crear array3 con rangos personalizados desde array1 y array2 sin un bucle? La solución simple de iterar sobre los rangos funciona, pero como mis arreglos se ejecutan en millones de elementos, estoy buscando una solución más eficiente (quizás azúcar sintáctica también)

Por ej.,

array1 = np.array([10, 65, 200]) array2 = np.array([14, 70, 204]) array3 = np.concatenate([np.arange(array1[i], array2[i]) for i in np.arange(0,len(array1))]) print array3 

resultado: [10,11,12,13,65,66,67,68,69,200,201,202,203] .

Enfoque prospectivo

Voy a ir hacia atrás sobre cómo abordar este problema.

Tome la muestra enumerada en la pregunta. Tenemos –

 array1 = np.array([10, 65, 200]) array2 = np.array([14, 70, 204]) 

Ahora, mira el resultado deseado –

 result: [10,11,12,13,65,66,67,68,69,200,201,202,203] 

Calculemos las longitudes de los grupos, ya que estaríamos necesitando aquellos para explicar el enfoque de la solución a continuación.

 In [58]: lens = array2 - array1 In [59]: lens Out[59]: array([4, 5, 4]) 

La idea es utilizar la matriz inicializada de 1 , que cuando se sum de forma acumulativa en toda la longitud, nos da el resultado deseado. Esta sum acumulativa sería el último paso para nuestra solución. ¿Por qué se inicializa 1? Bueno, porque tenemos una matriz que aumenta en pasos de 1 , excepto en lugares específicos donde tenemos cambios correspondientes a los nuevos grupos que ingresan.

Ahora, dado que cumsum sería el último paso, entonces el paso anterior debería darnos algo como:

 array([ 10, 1, 1, 1, 52, 1, 1, 1, 1, 131, 1, 1, 1]) 

Como se mencionó anteriormente, está lleno de [10,52,131] en lugares específicos. Ese 10 parece estar llegando desde el primer elemento en array1 , pero ¿qué pasa con el rest? El segundo 52 entró como 65-13 (mirando el result ) y en él 13 entró en el grupo que comenzó con 10 y corrió debido a la longitud del primer grupo 4 . Por lo tanto, si hacemos 65 - 10 - 4 , obtendremos 51 y luego agregaremos 1 para acomodar el límite, tendríamos 52 , que es el valor de cambio deseado. Del mismo modo, obtendríamos 131 .

Por lo tanto, esos shifting-values podrían ser calculados, como tal –

 In [62]: np.diff(array1) - lens[:-1]+1 Out[62]: array([ 52, 131]) 

A continuación, para obtener esos shifting-places donde ocurren esos cambios, podemos simplemente hacer un resumen acumulativo de las longitudes de los grupos.

 In [65]: lens[:-1].cumsum() Out[65]: array([4, 9]) 

Para completar, necesitamos añadir previamente 0 con el conjunto de shifting-places de shifting-places y array1[0] para shifting-values .

Por lo tanto, estamos listos para presentar nuestro enfoque en un formato paso a paso.


Volviendo a poner las piezas.

1] Obtener longitudes de cada grupo:

 lens = array2 - array1 

2] Obtenga los índices en los que se producen los cambios y los valores que se colocarán en la matriz inicializada de 1 :

 shift_idx = np.hstack((0,lens[:-1].cumsum())) shift_vals = np.hstack((array1[0],np.diff(array1) - lens[:-1]+1)) 

3] La matriz de ID inicializada de la Configuración 1 para insertar esos valores en los índices listados en el paso anterior:

 id_arr = np.ones(lens.sum(),dtype=array1.dtype) id_arr[shift_idx] = shift_vals 

4] Finalmente, haga una sum acumulativa en la matriz de ID:

 output = id_arr.cumsum() 

Listados en un formato de función, tendríamos –

 def using_ones_cumsum(array1, array2): lens = array2 - array1 shift_idx = np.hstack((0,lens[:-1].cumsum())) shift_vals = np.hstack((array1[0],np.diff(array1) - lens[:-1]+1)) id_arr = np.ones(lens.sum(),dtype=array1.dtype) id_arr[shift_idx] = shift_vals return id_arr.cumsum() 

¡Y también funciona en rangos superpuestos!

 In [67]: array1 = np.array([10, 11, 200]) ...: array2 = np.array([14, 18, 204]) ...: In [68]: using_ones_cumsum(array1, array2) Out[68]: array([ 10, 11, 12, 13, 11, 12, 13, 14, 15, 16, 17, 200, 201, 202, 203]) 

Prueba de tiempo de ejecución

@unutbu's flatnonzero based solution enfoque propuesto con el otro enfoque vectorizado en @unutbu's flatnonzero based solution en @unutbu's flatnonzero based solution , que ya demostró ser mucho mejor que el enfoque descabellado:

 In [38]: array1, array2 = (np.random.choice(range(1, 11), size=10**4, replace=True) ...: .cumsum().reshape(2, -1, order='F')) In [39]: %timeit using_flatnonzero(array1, array2) 1000 loops, best of 3: 889 µs per loop In [40]: %timeit using_ones_cumsum(array1, array2) 1000 loops, best of 3: 235 µs per loop 

¡Mejora!

Ahora, codewise a NumPy no le gusta añadir. Por lo tanto, esas llamadas np.hstack podrían evitarse para una versión ligeramente mejorada como se indica a continuación:

 def get_ranges_arr(starts,ends): counts = ends - starts counts_csum = counts.cumsum() id_arr = np.ones(counts_csum[-1],dtype=int) id_arr[0] = starts[0] id_arr[counts_csum[:-1]] = starts[1:] - ends[:-1] + 1 return id_arr.cumsum() 

Vamos a compararlo con nuestro enfoque original –

 In [151]: array1,array2 = (np.random.choice(range(1, 11),size=10**4, replace=True)\ ...: .cumsum().reshape(2, -1, order='F')) In [152]: %timeit using_ones_cumsum(array1, array2) 1000 loops, best of 3: 276 µs per loop In [153]: %timeit get_ranges_arr(array1, array2) 10000 loops, best of 3: 193 µs per loop 

Por lo tanto, tenemos un aumento de rendimiento del 30% allí!

Suponiendo que los rangos no se superpongan, puede crear una máscara que no sea cero donde el índice se encuentre entre los rangos especificados por array1 y array2 y luego usar np.flatnonzero para obtener una matriz de índices: la array3 :

 import numpy as np array1 = np.array([10, 65, 200]) array2 = np.array([14, 70, 204]) first, last = array1.min(), array2.max() array3 = np.zeros(last-first+1, dtype='i1') array3[array1-first] = 1 array3[array2-first] = -1 array3 = np.flatnonzero(array3.cumsum())+first print(array3) 

rendimientos

 [ 10 11 12 13 65 66 67 68 69 200 201 202 203] 

Para grandes len(array1) , using_flatnonzero puede ser significativamente más rápido que using_loop :

 def using_flatnonzero(array1, array2): first, last = array1.min(), array2.max() array3 = np.zeros(last-first+1, dtype='i1') array3[array1-first] = 1 array3[array2-first] = -1 return np.flatnonzero(array3.cumsum())+first def using_loop(array1, array2): return np.concatenate([np.arange(array1[i], array2[i]) for i in np.arange(0,len(array1))]) array1, array2 = (np.random.choice(range(1, 11), size=10**4, replace=True) .cumsum().reshape(2, -1, order='F')) assert np.allclose(using_flatnonzero(array1, array2), using_loop(array1, array2)) 

 In [260]: %timeit using_loop(array1, array2) 100 loops, best of 3: 9.36 ms per loop In [261]: %timeit using_flatnonzero(array1, array2) 1000 loops, best of 3: 564 µs per loop 

Si los rangos se superponen, using_loop devolverá un array3 que contiene duplicados. using_flatnonzero devuelve una matriz sin duplicados.


Explicación : Veamos un pequeño ejemplo con

 array1 = np.array([10, 65, 200]) array2 = np.array([14, 70, 204]) 

El objective es construir una matriz que se parece a la goal , a continuación. Los 1 están ubicados en valores de índice [ 10, 11, 12, 13, 65, 66, 67, 68, 69, 200, 201, 202, 203] (es decir, array3 ):

 In [306]: goal Out[306]: array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], dtype=int8) 

Una vez que tengamos la matriz de goal , array3 se puede obtener con una llamada a np.flatnonzero :

 In [307]: np.flatnonzero(goal) Out[307]: array([ 10, 11, 12, 13, 65, 66, 67, 68, 69, 200, 201, 202, 203]) 

goal tiene la misma longitud que array2.max() :

 In [308]: array2.max() Out[308]: 204 In [309]: goal.shape Out[309]: (204,) 

Así que podemos empezar asignando

 goal = np.zeros(array2.max()+1, dtype='i1') 

y luego rellenando 1 en las ubicaciones de índice dadas por array1 y -1’s en los índices dados por array2 :

 In [311]: goal[array1] = 1 In [312]: goal[array2] = -1 In [313]: goal Out[313]: array([ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -1], dtype=int8) 

Ahora, al aplicar cumsum (la sum acumulada) se obtiene la matriz de goal deseada:

 In [314]: goal = goal.cumsum(); goal Out[314]: array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0]) In [315]: np.flatnonzero(goal) Out[315]: array([ 10, 11, 12, 13, 65, 66, 67, 68, 69, 200, 201, 202, 203]) 

Esa es la idea principal detrás de using_flatnonzero . La resta de la first fue simplemente para guardar un poco de memoria.

¿Quieres decir esto?

 In [440]: np.r_[10:14,65:70,200:204] Out[440]: array([ 10, 11, 12, 13, 65, 66, 67, 68, 69, 200, 201, 202, 203]) 

o generalizando:

 In [454]: np.r_[tuple([slice(i,j) for i,j in zip(array1,array2)])] Out[454]: array([ 10, 11, 12, 13, 65, 66, 67, 68, 69, 200, 201, 202, 203]) 

Aunque esto implica un bucle doble, el explícito para generar los cortes y uno dentro de r_ para convertir los cortes a un arange .

  for k in range(len(key)): scalar = False if isinstance(key[k], slice): step = key[k].step start = key[k].start ... newobj = _nx.arange(start, stop, step) 

Menciono esto porque muestra que numpy desarrolladores consideran que su tipo de iteración es normal.

Espero que la cuchilla de @unutbu, si es algo obtusa (todavía no he descubierto lo que está haciendo), la solución sea su mejor oportunidad de velocidad. cumsum es una buena herramienta cuando necesita trabajar con rangos que pueden variar en longitud. Probablemente gana más cuando se trabaja con muchos rangos pequeños. No creo que funcione con rangos superpuestos.

================

np.vectorize usa np.frompyfunc . Así que esta iteración también se puede express con:

 In [467]: f=np.frompyfunc(lambda x,y: np.arange(x,y), 2,1) In [468]: f(array1,array2) Out[468]: array([array([10, 11, 12, 13]), array([65, 66, 67, 68, 69]), array([200, 201, 202, 203])], dtype=object) In [469]: timeit np.concatenate(f(array1,array2)) 100000 loops, best of 3: 17 µs per loop In [470]: timeit np.r_[tuple([slice(i,j) for i,j in zip(array1,array2)])] 10000 loops, best of 3: 65.7 µs per loop 

Con la solución vectorize de vectorize :

 In [474]: timeit result = np.concatenate(ranges(array1, array2), axis=0) 10000 loops, best of 3: 52 µs per loop 

vectorize debe realizar un trabajo adicional para permitir un uso más poderoso de la transmisión. Las velocidades relativas pueden cambiar si array1 es mucho más grande.

La solución de @unutbu no es especial con esta pequeña array1 .

 In [478]: timeit using_flatnonzero(array1,array2) 10000 loops, best of 3: 57.3 µs per loop 

La solución OP, iterativa sin mi r_ es buena.

 In [483]: timeit array3 = np.concatenate([np.arange(array1[i], array2[i]) for i in np.arange(0,len(array1))]) 10000 loops, best of 3: 24.8 µs per loop 

A menudo es el caso que con una pequeña cantidad de bucles, una comprensión de la lista es más rápida que las operaciones de numpy más numpy .

Para el caso de prueba más grande de @unutbu, mis tiempos son consistentes con los de él, con una aceleración de 17x.

===================

Para las matrices de muestras pequeñas, la solución de @Divakar es más lenta, pero para las grandes es 3 veces más rápida que la de @unutbu. Por lo tanto, tiene más de un costo de instalación, pero escala más lento.

Este es mi enfoque que combina vectorizar y concatenar :

Implementación :

 import numpy as np array1, array2 = np.array([10, 65, 200]), np.array([14, 70, 204]) ranges = np.vectorize(lambda a, b: np.arange(a, b), otypes=[np.ndarray]) result = np.concatenate(ranges(array1, array2), axis=0) print result # [ 10 11 12 13 65 66 67 68 69 200 201 202 203] 

Rendimiento :

 %timeit np.concatenate(ranges(array1, array2), axis=0) 

100000 bucles, lo mejor de 3: 13.9 µs por bucle