Vectorización de operación de índice para una matriz scipy.sparse

Question

El siguiente código se ejecuta muy lentamente a pesar de que todo parece estar vectorizado.

from numpy import *
from scipy.sparse import *

n = 100000;
i = xrange(n); j = xrange(n);
data = ones(n);

A=csr_matrix((data,(i,j)));

x = A[i,j]

El problema parece ser que la operación de indexación se implementa como una función de Python, e invocando resultados A[i,j] en la salida siguiente de perfiles

         500033 function calls in 8.718 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000    7.933    0.000    8.156    0.000 csr.py:265(_get_single_element)
        1    0.271    0.271    8.705    8.705 csr.py:177(__getitem__)
(...)

A saber, la función _get_single_element pitón se llama a 100000 veces que es muy ineficiente. ¿Por qué no se esta implementado en C puro? ¿Alguien sabe de una manera de conseguir alrededor de esta limitación, y acelerando el código anterior? Debería estar utilizando un tipo de matriz dispersa diferente?

Answer 1

Puede utilizar A.diagonal() para recuperar la diagonal mucho más rápidamente (0,0009 segundos versus 3,8 segundos en mi máquina). Sin embargo, si usted quiere hacer la indexación arbitrario entonces eso es una cuestión más complicada porque no se está utilizando rebanadas tanto como una lista de índices. La función _get_single_element se está llamando 100000 veces porque simplemente iteración a través de los iteradores (iyj) que le pasan. Una rebanada sería A [30: 60,10] o algo similar a eso.

Además, me gustaría utilizar csr_matrix(eye(n,n)) para hacer la misma matriz que ha realizado con iteradores sólo por simplicidad.

Actualización:

Ok, ya que su pregunta es realmente acerca de ser capaz de acceder a una gran cantidad de elementos aleatorios de forma rápida, voy a responder a sus preguntas lo mejor que pueda.

• ¿Por qué no se esta implementado en C puro?

La respuesta es sencilla: nadie ha llegado a hacerlo. Todavía hay mucho trabajo por hacer en el área de módulos de matriz dispersa de Scipy por lo que he visto. Una parte que se implementa en C es la conversión entre diferentes formatos de matriz dispersa.

• ¿Alguien sabe de una manera de conseguir alrededor de esta limitación, y acelerando el código anterior?

Puede probar realmente sumergirse en los módulos de matrices dispersas y tratando de acelerarlos. Así lo hice y fue capaz de obtener el tiempo de inactividad a menos de un tercio del original al probar el código anterior para accesos aleatorios utilizando matrices de RSE. Tuve que acceder directamente _get_single_element y recortar significativamente el código de hacerlo incluyendo la toma de los controles enlazados.

Sin embargo, fue aún más rápido utilizar un lil_matrix (aunque más lenta para inicializar la matriz), pero tenía que hacer lo que accede a una lista por comprensión, porque las matrices lil no están configurados para el tipo de indexación que está haciendo. El uso de una lista por comprensión para el csr_matrix todavía deja el método de la matriz lil camino a seguir por el camino. En última instancia, la matriz lil es más rápido para acceder a elementos aleatorios, ya que no está comprimido.

Uso de la lil_matrix en su forma original se ejecuta en aproximadamente una quinta parte del tiempo del código que ha enumerado anteriormente. Si tomo a cabo algunas comprobaciones consolidados y llamar al método de lil_matrix _get1 () directamente, puedo llevar el tiempo de inactividad más cerca del 7% del tiempo original. Para mayor claridad que es una aceleración de 3,4-3,8 segundos a aproximadamente 0,261 segundos.

Por último, he intentado hacer mi propia función que accede directamente a los datos de la matriz lil y evita las repetidas llamadas a funciones. El tiempo para esto era de unos 0,136 segundos. Esto no tomar ventaja de que los datos sean ordenadas, que es otro potencial de optimización (en particular si se accede a una gran cantidad de elementos que están en las mismas filas).

Si quieres más rápido de lo que entonces tendrá que escribir su propio código C aplicación de matrices dispersas probablemente.

• ¿Debo utilizar un tipo de matriz dispersa diferente?

Bueno, sugieren la matriz lil si su intención es tener acceso a una gran cantidad de elementos, pero todo depende de lo que tiene que hacer. ¿También necesita multiplicar matrices, por ejemplo? Sólo recuerde que los cambios entre las matrices puede al menos algunas veces (en determinadas circunstancias) será bastante rápido por lo que no descarta cambiar a un formato de matriz diferente para hacer diferentes operaciones.

Si usted no tiene que hacer realmente hacer cualquier operación de álgebra en su matriz, entonces tal vez debería sólo tiene que utilizar un defaultdict o algo similar. El peligro con defaultdicts es que cada vez que se le pide un elemento para que no esté en el dict, se establece que el tema en el valor predeterminado y lo almacena de manera que podría ser problemático.

Answer 2

Creo _get_single_element sólo se invoca cuando se utiliza el dtype por defecto de 'objeto'. ¿Usted ha intentado proporcionar una dtype, como csr_matrix((data, (i,j)), dtype=int32)