Vectorisation de fonctionnement d'index pour une matrice scipy.sparse

Question

Le code suivant fonctionne trop lentement, même si tout semble être vectorisé.

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]

Le problème semble être que l'opération d'indexation est réalisé sous forme d'une fonction de python, et invoquant des résultats d'A[i,j] à la sortie de profilage suivant

         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 savoir, la fonction python _get_single_element est appelée 100000 fois ce qui est vraiment inefficace. Pourquoi est-ce pas mis en œuvre dans le plus pur C? Quelqu'un sait-il d'un moyen de contourner cette limitation, et en accélérant le code ci-dessus? Dois-je utiliser un type de matrice creuse différente?

Answer 1

Vous pouvez utiliser A.diagonal() pour récupérer la diagonale beaucoup plus rapidement (0,0009 secondes contre 3,8 secondes sur ma machine). Toutefois, si vous voulez faire l'indexation qui est alors arbitraire une question plus compliquée parce que vous n'utilisez pas des tranches tant que la liste des indices. La fonction _get_single_element est appelée 100000 fois parce qu'il vient à travers les itérateurs itérer (i et j) que vous a été transmis. Une tranche serait A [30: 60,10] ou quelque chose de semblable à cela.

En outre, je voudrais utiliser csr_matrix(eye(n,n)) pour faire la même matrice que vous avez fait avec itérateurs pour simplifier les choses.

Mise à jour:

Ok, puisque votre question est vraiment d'être en mesure d'accéder à beaucoup d'éléments aléatoires rapidement, je vais répondre à vos questions du mieux que je peux.

• Pourquoi pas mis en œuvre dans le plus pur C?

La réponse est simple: personne n'a eu l'occasion de lui. Il y a encore beaucoup de travail à faire dans le domaine des modules de matrice clairsemée Scipy de ce que je l'ai vu. Une partie qui est mis en œuvre en C est les conversions entre les différents formats de matrice clairsemée.

• Quelqu'un sait-il d'un moyen de contourner cette limitation, et en accélérant le code ci-dessus?

Vous pouvez essayer réellement plonger dans les modules de matrice rares et en essayant de les accélérer. Je l'ai fait et a été en mesure d'obtenir le temps d'arrêt à moins d'un tiers de l'original en essayant votre code ci-dessus pour les accès aléatoires à l'aide de matrices rse. Je devais accéder directement _get_single_element et élaguer le code de manière significative à faire, y compris en prenant des contrôles liés.

Cependant, il est encore plus rapide d'utiliser un lil_matrix (bien que plus lent pour initialiser la matrice), mais je devais faire Accessing avec une compréhension de la liste parce que les matrices lil ne sont pas la configuration pour le type d'indexation que vous faites. En utilisant une compréhension de la liste pour la csr_matrix laisse encore la façon dont lil méthode de la matrice avant par la voie. En fin de compte, la matrice lil est plus rapide pour accéder à des éléments aléatoires car il n'est pas compressé.

Utilisation du lil_matrix dans sa forme originale fonctionne dans environ un cinquième du temps du code que vous avez énumérés ci-dessus. Si je prends quelques contrôles liés et appeler la méthode _get1 de lil_matrix () directement, je peux apporter le temps plus bas environ 7% du temps d'origine. Pour plus de clarté qui est une accélération de 3,4-3,8 secondes à environ 0,261 secondes.

Enfin, j'ai essayé de faire ma propre fonction qui accède directement aux données de la matrice lil et évite les appels de fonctions répétées. Le temps pour cela était d'environ 0,136 secondes. Cela n'a pas profité des données triées qui est une autre optimisation potentielle (en particulier si vous accédez à un grand nombre d'éléments qui sont sur les mêmes lignes).

Si vous voulez plus vite que cela, alors vous devrez écrire votre propre implémentation de matrice creuse de code C probablement.

• devrais-je utiliser un type de matrice creuse différente?

Eh bien, je suggère la matrice lil si votre intention est d'accéder à beaucoup d'éléments, mais tout dépend de ce que vous devez faire. Avez-vous besoin aussi de multiplier les matrices par exemple? Rappelez-vous que le changement entre les matrices peut au moins parfois (dans certaines circonstances) être assez rapide pour ne pas exclure le passage à un format de matrice différente pour faire différentes opérations.

Si vous n'avez pas besoin de faire réellement faire des opérations d'algèbre sur votre matrice, alors peut-être vous devriez juste utiliser un defaultdict ou quelque chose de similaire. Le danger avec defaultdicts est que chaque fois qu'un élément est demandé qui ne sont pas dans le dict, il définit cet élément par défaut et les stocke pour que pourrait être problématique.

Answer 2

Je pense que _get_single_element n'est appelée lorsque le DTYPE par défaut de « objet » est utilisé. Avez-vous essayé fournir un DTYPE, comme csr_matrix((data, (i,j)), dtype=int32)