7

我有两个 c 的布尔稀疏方阵。从 12BM 的数据生成 80,000 x 80,000（当我使用 GB 的数据时，矩阵可能会大几个数量级）。

我想将它们相乘（这会产生一个三角矩阵 - 但是我没有得到这个，因为我不限制点积来产生一个三角矩阵）。

我想知道将它们相乘的最佳方法是什么（内存方面和速度方面） - 我将在具有 > 60GB RAM 的 m2.4xlarge AWS 实例上进行计算。出于速度原因，我更愿意将计算保留在 RAM 中。

我很欣赏 SciPy 有稀疏矩阵，h5py 也有，但两者都没有经验。

什么是最好的选择？

提前致谢

更新：布尔矩阵的稀疏性 <0.6%

4

2 回答 2

1

如果您的矩阵相对空，则可能值得将它们编码为非 False 值的数据结构。说一个描述非 False 值位置的元组列表。或者以元组为键的字典。

如果您使用例如元组列表，您可以使用列表推导来查找第二个列表中可以与第一个列表中的元素相乘的项目。

a = [(0,0), (3,7), (5,2)] # et cetera
b = ... # idem

for r, c in a:
    res = [(r, k) for j, k in b if k == j]
于 2013-12-07T15:00:46.890 回答
-1

--编辑以满足以下评论/否决者--

您在问如何快速轻松地乘以矩阵。

解决方案 1：这是一个已解决的问题：使用 numpy. 所有这些操作在 numpy 中都很容易，并且由于它们是用 C 实现的，因此速度非常快。

另见：

SciPy 和 Numpy 具有稀疏矩阵和矩阵乘法。它不使用太多内存，因为（至少如果我用 C 编写它）它可能使用链表，因此只会使用数据点总和所需的内存，加上一些开销。而且，与纯 python 解决方案相比，它几乎肯定会非常快。

解决方案 2

这里的另一个答案建议将值存储为 (x, y) 的元组，假设值是 False 除非它存在，那么它就是真的。与之替代的是带有 (x, y, value) 元组的数值矩阵。

不管：将这些相乘在时间上会很糟糕：找到元素一，决定要乘以哪个其他数组元素，然后在整个数据集中搜索该特定元组，如果存在，则将结果相乘并将结果插入结果矩阵。

解决方案 3（首选与解决方案 2，恕我直言）

我更喜欢这个，因为它更简单/更快。

用一组字典表示您的稀疏矩阵。矩阵一是一个字典，其元素位于 (x, y) 且值 v 为 (x1,y1, x2,y2 等)：

matrixDictOne = { 'x1:y1' : v1, 'x2:y2': v2, ... }
matrixDictTwo = { 'x1:y1' : v1, 'x2:y2': v2, ... }

由于 Python dict 查找是 O(1)（好吧，不是真的，可能更接近 log(n)），所以它很快。这不需要在乘法之前搜索整个第二个矩阵的数据以查找元素的存在。所以，它很快。很容易编写乘法并且易于理解表示。

解决方案4（如果你是一个贪吃惩罚的人）

使用所需大小的内存映射文件对此解决方案进行编码。使用所需大小的空值初始化文件。自己计算偏移量并在进行乘法运算时写入文件中的适当位置。Linux 有一个 VMM，它会为您分页进出，而您只需很少的开销或工作。这是非常非常大的非稀疏矩阵的解决方案，因此不适合内存。

请注意，这解决了以下抱怨者的抱怨，即它不适合内存。但是，OP 确实说sparse，这意味着很少有实际数据点分布在巨型阵列中，而 Numpy / SciPy 可以本地处理，因此很好（费米实验室的很多人经常使用 Numpy / SciPy，我相信稀疏矩阵代码已经过很好的测试）。

于 2013-12-27T21:02:39.390 回答