我需要存储稀疏矩阵数据。
数据大小为10^6 10^4
列。
在每一列中,我存储了一个由0向量组成的向量,除了少数几个值是true
。
然后我需要对每个矩阵的列求和,并将每行乘以一个标量。 我尝试了使用字典,但当我需要求和和乘积时它们失败了。
你会使用什么方法呢?
PS. numpy.zeros太小了
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])
) 或者在行上求和并将结果乘以你想要的任何东西。
正如其他人所提到的,您应该查看 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
根据您的需求,有数百种方法可以实现这一点。维基百科上的稀疏矩阵条目是一个很好的起点,可以找到适用于您特定需求的方法。
作为一个极其简单的例子,您可以使用类似于键值字典的方式:
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种不同的稀疏矩阵格式。不要重新发明已经被其他人做得更好的东西...
cols
字典是按列计算的总和字典,因此在构建完布尔稀疏矩阵后,您只需要迭代一次即可。然后,只需引用 cols
字典以获取所有列的总和。我想,如果原始数据发生更改,您可能需要重新计算 cols
,但这并没有由 OP 指定。 - the wolf
scipy.sparse
дє†еђ—пјџhttp://docs.scipy.org/doc/scipy/reference/sparse.html - Joe Kington