¿Sumar de manera eficiente una matriz numpy pequeña, transmitida a través de una matriz numpy descomunal?

Question

Quiero calcular una suma de peso indexada en una gran matriz numerada booleana (1,000,000 x 3,000). La gran matriz booleana cambia con poca frecuencia, pero los pesos vienen en tiempo de consulta, y necesito respuestas muy rápido, sin copiar toda la matriz grande, o expandir la matriz de pesas pequeñas al tamaño de la matriz grande.

El resultado debe ser una matriz con 1,000,000 entradas, cada una con la suma de las entradas de la matriz de ponderaciones correspondientes a los valores True de esa fila.

Analicé el uso de matrices enmascaradas, pero parecen requerir la construcción de una matriz de pesos del tamaño de mi matriz booleana grande.

El código siguiente muestra los resultados correctos, pero no puedo permitirme esa copia durante el paso de multiplicar. La multiplicación ni siquiera es necesaria, ya que la matriz de valores es booleana, pero al menos maneja la difusión correctamente.

Soy nuevo en numpy, y me encanta, pero estoy a punto de renunciar a él por este problema en particular. Aprendí lo suficiente para saber que me quedé lejos de cualquier cosa que se repita en python.

Mi próximo paso será escribir esta rutina en C (que tiene el añadido beneficio de dejar a salvar la memoria mediante el uso de los bits en lugar de bytes, por el camino.)

A menos que uno de ustedes gurús numpy me puede salvar de cython?

from numpy import array, multiply, sum 

# Construct an example values array, alternating True and False. 
# This represents four records of three attributes each: 
# array([[False, True, False], 
#   [ True, False, True], 
#   [False, True, False], 
#   [ True, False, True]], dtype=bool) 
values = array([(x % 2) for x in range(12)], dtype=bool).reshape((4,3)) 

# Construct example weights, one for each attribute: 
# array([1, 2, 3]) 
weights = array(range(1, 4)) 

# Create expensive NEW array with the weights for the True attributes. 
# Broadcast the weights array into the values array. 
# array([[0, 2, 0], 
#   [1, 0, 3], 
#   [0, 2, 0], 
#   [1, 0, 3]]) 
weighted = multiply(values, weights) 

# Add up the weights: 
# array([2, 4, 2, 4]) 
answers = sum(weighted, axis=1) 

print answers 

# Rejected masked_array solution is too expensive (and oddly inverts 
# the results): 
masked = numpy.ma.array([[1,2,3]] * 4, mask=values) 

Answer 1

El producto de punto (o producto interno) es lo que desea. Te permite tomar una matriz del tamaño m×n y un vector de longitud n y multiplicarlas juntas, produciendo un vector de longitud m, donde cada entrada es la suma ponderada de una fila de la matriz con las entradas del vector de como pesos.

Numpy implementa esto como array1.dot(array2) (o numpy.dot(array1, array2) en versiones anteriores). ej .:

from numpy import array 

values = array([(x % 2) for x in range(12)], dtype=bool).reshape((4,3)) 

weights = array(range(1, 4)) 

answers = values.dot(weights) 
print answers 
# output: [ 2 4 2 4 ] 

(Debe referencia esto, sin embargo, el uso de la timeit module.)

Answer 2

¿Esto funcionaría para usted?

a = np.array([sum(row * weights) for row in values]) 

Esto utiliza para resumir sum() inmediatamente los row * weights valores, por lo que no necesita la memoria para almacenar todos los valores intermedios. Entonces la lista de comprensión recoge todos los valores.

Dijiste que querías evitar todo lo que "gira en Python". Esto al menos hace el bucle con las tripas de C de Python, en lugar de un ciclo de Python explícito, pero no puede ser tan rápido como una solución de NumPy porque usa C o Fortran compilados.

Answer 3

No creo que necesita numpy para algo así. Y 1000000 por 3000 es una gran variedad; esto no cabe en tu memoria RAM, muy probablemente.

lo haría de esta manera:

Digamos que los datos están originalmente en un archivo de texto:

False,True,False 
True,False,True 
False,True,False 
True,False,True 

Mi código:

weight = range(1,4)  
dicto = {'True':1, 'False':0} 

with open ('my_data.txt') as fin: 

    a = sum(sum(dicto[ele]*w for ele,w in zip(line.strip().split(','),weight)) for line in fin) 

Resultado:

>>> a 
12 

EDITAR:

Creo que leí un poco la pregunta la primera vez, y resumí todo junto. Aquí está la solución que da la solución exacta que la OP es después:

weight = range(1,4) 
dicto = {'True':1, 'False':0} 

with open ('my_data.txt') as fin: 

    a = [sum(dicto[ele]*w for ele,w in zip(line.strip().split(','),weight)) for line in fin] 

Resultado:

>>> a 
[2, 4, 2, 4] 

Answer 4

Parece probable que la respuesta dbaupp 's es la correcta. Pero solo por el bien de la diversidad, aquí hay otra solución que ahorra memoria. Esto funcionará incluso para las operaciones que no tienen un equivalente numpy incorporado.

>>> values = numpy.array([(x % 2) for x in range(12)], dtype=bool).reshape((4,3)) 
>>> weights = numpy.array(range(1, 4)) 
>>> weights_stretched = numpy.lib.stride_tricks.as_strided(weights, (4, 3), (0, 8)) 

numpy.lib.stride_tricks.as_strided es una pequeña y maravillosa función! Le permite especificar shape y strides valores que permiten que una matriz pequeña imite una matriz mucho más grande. Observe - no hay realmente cuatro filas aquí; sólo se ve de esa manera:

>>> weights_stretched[0][0] = 4 
>>> weights_stretched 
array([[4, 2, 3], 
     [4, 2, 3], 
     [4, 2, 3], 
     [4, 2, 3]]) 

Así que en lugar de pasar una enorme variedad de MaskedArray, puede pasar una más pequeña. (Pero como ya habrás notado, el enmascaramiento numpy funciona de la manera opuesta a la esperada; máscaras de verdad, en lugar de revelar, por lo que tendrás que almacenar tu values invertido.) Como puedes ver, MaskedArray no copia ningún datos; simplemente refleja lo que está en weights_stretched:

>>> masked = numpy.ma.MaskedArray(weights_stretched, numpy.logical_not(values)) 
>>> weights_stretched[0][0] = 1 
>>> masked 
masked_array(data = 
[[-- 2 --] 
[1 -- 3] 
[-- 2 --] 
[1 -- 3]], 
     mask = 
[[ True False True] 
[False True False] 
[ True False True] 
[False True False]], 
     fill_value=999999) 

Ahora sólo lo puede transmitir a resumir:

>>> sum(masked, axis=1) 
masked_array(data = [2 4 2 4], 
     mask = [False False False False], 
     fill_value=999999) 

I Benchmarked numpy.dot y lo de arriba contra una variedad 1.000.000 x 30. Este es el resultado de un MacBook Pro relativamente moderno (numpy.dot es dot1; mío es dot2):

>>> %timeit dot1(values, weights) 
1 loops, best of 3: 194 ms per loop 
>>> %timeit dot2(values, weights) 
1 loops, best of 3: 459 ms per loop 

Como se puede ver, la solución integrada numpy es más rápido. Pero vale la pena saber stride_tricks independientemente, así que me voy de esto.