在Python中存储大量布尔数据

Question

在Python中存储大量布尔数据

pythonarraysnumpy

4

我需要存储稀疏矩阵数据。数据大小为10^6 10^4列。在每一列中，我存储了一个由0向量组成的向量，除了少数几个值是true。

然后我需要对每个矩阵的列求和，并将每行乘以一个标量。我尝试了使用字典，但当我需要求和和乘积时它们失败了。

你会使用什么方法呢？

PS. numpy.zeros太小了

- Intelligent-Infrastructure

4

дЅ зњ‹иї‡scipy.sparseдє†еђ—пјџhttp://docs.scipy.org/doc/scipy/reference/sparse.html - Joe Kington

1

你只是在存储这些数据吗？还是需要将其作为矩阵进行处理？你只是想要更小的内存占用，还是其他需求？你是否希望它看起来像一个列表中的列表？ - dawg

3个回答

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

- JoshAdel

我没有检查过，不过我曾经在Matlab中使用过稀疏矩阵。我首先检查了字典，它可以正常工作。 - Intelligent-Infrastructure

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种不同的稀疏矩阵格式。不要重新发明已经被其他人做得更好的东西...

- dawg

这不需要每次想要对单个列或行的值求和时都迭代整个字典吗？ - Tim Pietzcker

@Tim Pietzcker：是的，按照目前的写法，您需要遍历整个字典。将列的累加和添加到类中可能会减慢数据结构的构建，但这相当容易实现。然而，对于一般的DOK，使用元组字典的方法与SciPY相同。OP没有指定快速构建还是快速处理更重要。 DOK具有快速构建的优点。由于OP声明在数百万个假值中只有少数真值，因此这似乎是一个公平的权衡。 - dawg

@Tim Pietzcker：并不是每次都需要。cols 字典是按列计算的总和字典，因此在构建完布尔稀疏矩阵后，您只需要迭代一次即可。然后，只需引用 cols 字典以获取所有列的总和。我想，如果原始数据发生更改，您可能需要重新计算 cols，但这并没有由 OP 指定。 - the wolf

在您看来，哪种方式更快：创建一个字典还是使用scipy.sparse？ - Intelligent-Infrastructure

@智能基础设施：您需要定义“更快”吗？更快地编写？更快地构建矩阵？交互式的？更快地处理矩阵？交互式的？更快地调试？更快地安装在其他机器上？如果您只构建一次DOK，然后一次性构建派生的求和和乘积字典，那么DOK就是直接、易于调试且可能非常快速的。SciPy非常快速，非常无bug，并且许多部分都是用C编写的。SciPy有一个学习曲线，必须在目标上运行，并且有一些开销。我需要更多信息才能确定。测试它。 - dawg

@drewk，我没有像你提到的那样使用类，因为简单的函数对列求和更容易适应代码的其余部分。但是，如果我需要进一步扩展函数，例如矩阵x向量，你的调用将非常方便。 - Intelligent-Infrastructure

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tim Pietzcker · Accepted Answer

两个字典怎么样？假设这是矩阵（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])) 或者在行上求和并将结果乘以你想要的任何东西。