Stockage d'une grande quantité de données booléennes en python

Question

J'ai besoin de stocker des données de matrice sparse. La taille des données est de 10^6 10^4 colonnes. Dans chaque colonne, je stocke un vecteur de 0 sauf pour quelques valeurs où c'est true.

Ensuite, j'ai besoin de faire la somme sur les colonnes de chaque matrice, et de multiplier chaque ligne par un scalaire. J'ai essayé avec des dictionnaires, mais ils échouent quand j'ai besoin de faire la somme et de multiplier.

Que utiliseriez-vous?

PS. numpy.zeros est trop petit.

Answer 1

Que diriez-vous de deux dictionnaires? En supposant que c'est la matrice (x pour True):

   0  1  2  3  4  5  6  7
0  x     x        x
1     x
2                       x
3              x
4
5
6        x        x
7

Vous auriez seulement besoin de stocker

rows = {0: [0, 2, 5], 1: [1], 2: [7], 3: [4], 6: [2, 5]}

Vous pourriez facilement transformer cela en

columns = {0: [0], 1: [1], 2: [0, 6], 4: [3], 5: [0, 6], 7: [2]}

en utilisant quelque chose comme

columns = {}
for row in rows:
    for column in rows[row]:
        columns.setdefault(column, []).append(row)

et ensuite additionner sur les colonnes (sum(1 for x in column[2])) ou sur les lignes et multiplier le résultat par ce que vous voulez.

Answer 2

Comme d'autres l'ont mentionné, vous devriez consulter scipy.sparse:

http://docs.scipy.org/doc/scipy/reference/sparse.html

Il existe plusieurs formats optimisés pour diverses opérations parcimonieuses, y compris la multiplication scalaire et la sommation.

Par exemple:

import scipy.sparse
import numpy as np

rows = np.array([1,100,1000])
cols = np.array([100,99,1474])
vals = np.ones_like(rows)

A = scipy.sparse.coo_matrix((vals,(rows,cols)),shape=(int(1E6),int(1E6)),dtype=np.bool)

Ensuite, pour multiplier par un scalaire et prendre une somme:

B = 3*A
B.sum() # 9

Answer 3

En fonction de vos besoins, il existe littéralement des centaines de méthodes pour le faire. L'entrée sur les matrices creuses sur Wikipedia est un bon point de départ pour trouver une méthode qui s'applique spécifiquement à vos besoins.

À titre d'exemple extrêmement simple, vous pourriez utiliser une classe Dictionnaire de clés comme ceci :

class SparseDOK(dict):

    def __init__(self):
        pass

    def __setitem__(self, key, value):
        if value in[0, 0.0, False, None]:
            dict.__setitem__(self, key, False)
            dict.__delitem__(self, key)
        else:
            dict.__setitem__(self, key, True)

    def __getitem__(self, key):    
        try: 
            return dict.__getitem__(self, key)
        except KeyError: 
            return False

>>> dok=SparseDOK()
>>> dok[10,20]=55
>>> print dok
{(10, 20): True}
>>> print dok[10,20]
True
>>> print dok[55,300]      
False
>>> dok[10,20]=False
>>> print dok[10,20]
False

Chaque entrée dans une 'matrice' arbitraire est supposée être fausse, sauf si elle est spécifiquement définie à Vrai. Vous devriez ajouter des contrôles d'erreur, mais cela sera très compact et rapide.

L'avantage de construire un Dictionnaire de Clés est une construction très efficace de la structure de données. Vous n'avez besoin de passer qu'une seule fois par les données originales et vous pouvez facilement ajouter ou supprimer des données. L'inconvénient est un traitement moins interactif de la matrice une fois que vous l'avez construite.

Étant donné que les clés du dictionnaire sont des tuples, il est trivial d'ajouter les indices par ligne ou par colonne. Puisque l'ensemble de la matrice devrait être traité après sa construction pour cela, nous pouvons simplement construire un dictionnaire avec la somme ou le produit désiré une fois, puis nous référencer à ce dictionnaire de données traitées.

>>> dok[10,20]=True
>>> dok[10,2000]=True
>>> dok[11,2000]=True
>>> dok[35000,2000]=True
>>> dok[10,35000]=True
>>> print dok
{(11, 2000): True, (10, 2000): True, (35000, 2000): True, (10, 20): True, (10, 35000): True}
cols={}
for tup in dok.keys():
    if tup[1] not in cols:
        cols[tup[1]]=1
    else:
        cols[tup[1]]+=1    

>>> print cols
{2000: 3, 35000: 1, 20: 1}

Maintenant, vous pouvez vous référer à la clé de colonne dans cols pour la somme des lignes par colonne. Il est trivial d'ajouter un produit, etc. Souvenez-vous simplement que vous devez recalculer les sommes / produits si le DOK original est édité ou modifié. Vous pourriez garder un total cumulé si vous anticipez que le DOK changerait souvent après sa création initiale.

Si vos besoins sont plus complexes, envisagez d'utiliser SciPy ou Pysparse. Comme vous pouvez le constater, il existe 7 formats de matrices creuses différents dans SciPy. Ne réinventez pas quelque chose que d'autres ont déjà fait mieux...