Python/NumPy: la aplicación de una suma corriente (pero no del todo)

Question

dado son dos matrices de igual longitud, uno de datos que contiene, uno que sostienen los resultados pero inicialmente establecidos en cero, por ejemplo:

a = numpy.array([1, 0, 0, 1, 0, 1, 0, 0, 1, 1]) 
b = numpy.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) 

que había Me gusta calcular la suma de todos los subconjuntos posibles de tres elementos adyacentes en a. Si la suma es 0 o 1, los tres elementos correspondientes en b no se modifican; sólo si la suma excede de 1 son los tres elementos correspondientes en b se establece en 1, de modo que después del cálculo B se convierte en

array([0, 0, 0, 1, 1, 1, 0, 1, 1, 1]) 

Un bucle simple se hará lograr esto:

for x in range(len(a)-2): 
    if a[x:x+3].sum() > 1: 
     b[x:x+3] = 1 

Después de esto, b tiene la forma deseada.

Tengo que hacer esto para una gran cantidad de datos, por lo que la velocidad es un problema. ¿Hay una forma más rápida en NumPy para llevar a cabo la operación anterior?

(entiendo que esto es similar a una convolución, pero no exactamente igual).

Answer 1

Puede comenzar con una convolución, elegir los valores que exceden 1, y finalmente utiliza una "dilatación":

b = numpy.convolve(a, [1, 1, 1], mode="same") > 1 
b = b | numpy.r_[0, b[:-1]] | numpy.r_[b[1:], 0] 

Dado que esto evita el bucle de Python, que debería ser más rápido que su enfoque, pero no hizo sincronizaciones.

Una alternativa es utilizar una segunda convolución para dilatar:

kernel = [1, 1, 1] 
b = numpy.convolve(a, kernel, mode="same") > 1 
b = numpy.convolve(b, kernel, mode="same") > 0 

Si tiene SciPy disponibles, sin embargo, otra opción para la dilatación es

b = numpy.convolve(a, [1, 1, 1], mode="same") > 1 
b = scipy.ndimage.morphology.binary_dilation(b) 

Editar: Haciendo some timings, Encontré que esta solución parece ser la más rápida para matrices grandes:

b = numpy.convolve(a, kernel) > 1 
b[:-1] |= b[1:] # Shift and "smearing" to the *left* (smearing with b[1:] |= b[:-1] does not work) 
b[:-1] |= b[1:] # … and again! 
b = b[:-2] 

Para una matriz de un millón de entradas, fue más de 200 veces más rápido que su enfoque original en mi máquina. Como lo señala EOL en los comentarios, esta solución podría considerarse un poco frágil, ya que depende de los detalles de implementación de NumPy.

Answer 2

Puede calcular las sumas "convolución" de una manera eficiente con:

>>> a0 = a[:-2] 
>>> a1 = a[1:-1] 
>>> a2 = a[2:] 
>>> a_large_sum = a0 + a1 + a2 > 1 

Actualización de b continuación, se puede hacer de manera eficiente por escrito algo que significa "al menos uno de los tres vecinos a_large_sum valores es verdadero" : por primera vez se amplía a_large_sum gama de vuelta al mismo número de elementos como a (a la derecha, hacia la izquierda y hacia la derecha, y luego a la izquierda):

>>> a_large_sum_0 = np.hstack([a_large_sum, [False, False]]) 
>>> a_large_sum_1 = np.hstack([[False], a_large_sum, [False]]) 
>>> a_large_sum_2 = np.hstack([[False, False], a_large_sum]) 

entonces obtendrá b de una manera eficiente:

>>> b = a_large_sum_0 | a_large_sum_1 | a_large_sum_2 

Esto da como resultado que se obtiene, pero de una manera muy eficiente, a través de un apalancamiento de NumPy bucles rápidos internos.

PS: Este enfoque es esencialmente el mismo que la primera solución de Sven, pero es mucho más pedestre que el código elegante de Sven; es tan rápido, sin embargo. La segunda solución de Sven (doble convolve()) es aún más elegante, y es el doble de rápido.

Answer 3

También le gustaría echar un vistazo a NumPy's stride_tricks. Usando el ajuste de puesta de Sven (ver enlace en la respuesta de Sven), he encontrado que para la (muy) grandes matrices, esto también es una forma rápida de hacer lo que quiera (es decir, con su definición de a):

shape = (len(a)-2,3) 
strides = a.strides+a.strides 
a_strided = numpy.lib.stride_tricks.as_strided(a, shape=shape, strides=strides) 
b = np.r_[numpy.sum(a_strided, axis=-1) > 1, False, False] 
b[2:] |= b[1:-1] | b[:-2] 

Después de editar (ver comentarios a continuación) ya no es la forma más rápida.

Esto crea una vista especialmente estriada en su matriz original. Los datos en a no se copian, sino que simplemente se ven de una manera nueva. Queremos, básicamente, hacer una nueva matriz en la que el último índice contenga las sub-matrices que queremos sumar (es decir, los tres elementos que desea sumar). De esta manera, podemos sumar fácilmente al final con el último comando.

El último elemento de esta nueva forma, por tanto, tiene que haber 3, y el primer elemento será la longitud de la edad a menos 2 (porque sólo podemos resumir de la -2 nd elemento).

La lista de pasos contiene los pasos, en bytes, que necesita la nueva matriz a_strided para llegar al siguiente elemento en cada una de las dimensiones de la forma. Si establece estos valores iguales, significa que a_strided[0,1] y a_strided[1,0] serán ambos a[1], que es exactamente lo que queremos. En una matriz normal, este no sería el caso (la primera zancada sería "tamaño de primera dimensión tiempos longitud-de-matriz-primera-dimensión (= forma [0])"), pero en este caso podemos hacer un buen uso de eso.

No estoy seguro de haber explicado todo esto muy bien, pero simplemente imprima a_strided y verá cuál es el resultado y cuán fácil es la operación.