在Python中存储大量布尔数据

Question

我需要存储稀疏矩阵的数据。数据的大小是 10^6 10^4 列。在每一列中，我存储的是一堆0，只有少数几个值是 true。

接下来，我需要对每个矩阵的列进行求和，并把每一行乘以一个标量。我试过用字典，但在求和和乘法时它们不太好用。

你会用什么方法呢？

PS. numpy.zeros 太小了。

Answer 1

根据你的需求，实际上有很多种方法可以做到这一点。维基百科上的稀疏矩阵条目是一个很好的起点，可以帮助你找到适合你需求的方法。

举个非常简单的例子，你可以使用一个键字典类，像这样：

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

在这个“矩阵”中，默认每个位置的值都是False，除非特别设置为True。你可能需要添加一些错误检查，但这个方法会非常简洁和快速。

使用键字典的好处是构建数据结构的效率很高。你只需要遍历一次原始数据，就可以轻松地添加或删除数据。缺点是，一旦构建完成后，处理矩阵的交互性会降低。

因为字典的键是元组，所以按行或列添加索引非常简单。由于在构建后需要处理整个矩阵，所以我们可以只构建一个包含所需和或积的字典，然后引用这个处理过的数据字典。

>>> 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}

现在你可以在cols中引用列键，以获取按列汇总的行和。添加乘积等操作也很简单。只要记住，如果原始的DOK被编辑或更改，你需要重新计算和/积。如果你预期DOK在创建后会频繁变化，可以保持一个运行总和。

如果你的需求更复杂，可以考虑使用SciPy或Pysparse。正如你所看到的，SciPy中有7种不同的稀疏矩阵格式。不要重复造轮子，别人已经做得更好了……

Answer 2

正如其他人提到的，你应该看看 scipy.sparse 这个模块：

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

这个模块有很多不同的格式，专门优化了各种稀疏操作，比如数值的乘法和加法。

举个例子：

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)

然后你可以通过一个数来乘，并进行求和：

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

Answer 3

两个字典怎么样？假设这是一个矩阵（用x表示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

你只需要存储

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

你可以很容易地把它转换成

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

使用类似于

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

然后可以对列进行求和（sum(1 for x in column[2])）或者对行进行求和，并把结果和你想要的东西相乘。