在Python中处理大型稠密矩阵

Question

基本上，如何在Python中存储和使用稠密矩阵是最好的方法？

我有一个项目需要计算数组中每个项目之间的相似度。

每个项目都是一个自定义类，里面存储了指向其他类的指针和一个数字，表示它与那个类的“接近程度”。

现在，这个方法在大约8000个项目时运行得很好，但超过这个数量就会出现内存不足的错误。
简单来说，如果假设每次比较大约需要30个字节（根据测试，这个估计是准确的）来存储相似度，那么所需的总内存就是：
numItems^2 * itemSize = Memory
所以内存使用量是基于项目数量的指数增长。
在我的情况下，每个链接的内存大小大约是30个字节，所以：
8000 * 8000 * 30 = 1,920,000,000字节，或者1.9 GB
这正好达到了单线程的内存限制。

我觉得应该有更有效的方法来处理这个问题。我看过内存映射，但生成相似度值本身就已经很耗计算资源了，通过硬盘来处理所有这些似乎有点荒谬。

编辑
我看过numpy和scipy。不幸的是，它们也不支持非常大的数组。

>>> np.zeros((20000,20000), dtype=np.uint16)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError
>>>

进一步编辑
Numpy似乎很受欢迎。然而，Numpy并不能完全满足我的需求，至少没有另一个抽象层的帮助。

我不想存储数字，我想存储对类的引用。Numpy支持对象，但这并没有解决数组大小的问题。我提到Numpy只是作为一个例子，说明什么是行不通的。

有什么建议吗？

编辑 最后，我重写了所有逻辑，不再存储任何冗余值，将内存使用量从O*n^2减少到O*((n*(n-1))/2)。

基本上，这整个事情是一个握手问题的变种，所以我从存储所有链接改为只存储每个链接的一个版本。

这不是一个完整的解决方案，但我通常没有足够大的数据集会导致溢出，所以我觉得这样可以行得通。PyTables很有趣，但我不懂SQL，而且似乎没有什么传统的切片或基于索引的方式来访问表数据。我可能会在未来重新考虑这个问题。

Answer 1

你说的20,000 x 20,000的矩阵需要12GB的内存吗？

在win32系统下，内存的使用会受到限制，这样的话你可能会遇到性能问题，感觉像是在“交换地狱”里挣扎。

我建议你找一个可以支持12GB内存的操作系统。如果你必须使用32位的Windows，像Windows 2003服务器的32位版本可以做到，但如果你能使用64位的机器和64位的操作系统，再加上16GB内存，那就更合适了。

这也是一个升级硬件的好理由呢 :)

64位的numpy可以支持你的矩阵。

Python 2.5.2 (r252:60911, Jan 20 2010, 23:14:04) 
[GCC 4.2.4 (Ubuntu 4.2.4-1ubuntu3)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import numpy as np
>>> np.zeros((20000,20000),dtype=np.uint16)
array([[0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0],
       ..., 
       [0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0]], dtype=uint16)

Answer 2

我找到了我的解决方案：
h5py

这个库基本上提供了一个像numpy那样的界面，但它使用压缩的内存映射文件来存储任意大小的数组（其实就是HDF5的一个封装）。

PyTables是基于这个库构建的，而我也是通过PyTables发现了它。不过，我并不需要PyTables提供的SQL功能，因为那不是我真正想要的，而PyTables也没有我想要的那种干净的数组接口。

h5py基本上就像一个numpy数组，只是以不同的格式存储数据。

它似乎对数组大小没有限制，除了可能受到磁盘空间的限制。我现在正在测试一个大小为100,000 * 100,000的uint16数组。

Answer 3

PyTables 可以处理任意大小的表格（甚至有几百万列！），这得益于它使用了内存映射和一些聪明的压缩技术。

表面上看，它能给 Python 提供类似 SQL 的性能。不过，这可能需要对代码进行较大的修改。

在我更仔细地检查之前，我不会接受这个答案，以确保它真的能满足我的需求。或者希望有人能提供更好的解决方案。