Python词典中的散列

Question

我有一个非常大的矩阵，我计划用Python存储为一个字典列表。矩阵大部分是0，我想知道字典中的哈希函数是否会为每一行存储前导空间。例如，如果我初始化一个100000 x 100000的矩阵，但每行只有大约1000个条目存储实际元素，对于第50000行，我有48500到50500的条目，Python会创建一个50500或2000大小的字典吗？此外，如果前者是真的，我有没有办法在Python当前的dictionary类中进行优化，或者我需要创建自己的dictionary类？你知道吗

作为我代码的一个例子，我有：

class DictArray:

    def __init__(self, width, height):
        self.Width = width
        self.Height = height
        self.Data = [0 for _ in range(self.Height) ]

    def __getitem__(self, k):
        if (self.Data[ k[0] ] == 0):
            return 0
        elif (k[1] in self.Data[ k[0] ]):
            return self.Data[ k[0] ][ k[1] ]
        else:
            return 0

    def __setitem__(self, k, value):
        if (self.Data[ k[0] ] == 0):
            self.Data[ k[0] ] = { k[1] : value }
        else:
            self.Data[ k[0] ][ k[1] ] = value

Answer 1

如果您有一个稀疏矩阵，您可能会尝试使用字典，其中键是（row，col）元组（或者其他一些快速获取行和列的方法）。你知道吗

例如

# assume get_matrix(i,j) gives your (i,j)th element
m = {}
for i in xrange(0,100000):
    for j in xrange(0,100000):
        t = get_matrix(i,j)
        if t:
            m[(i,j)] = t

关于字典性能，假设它具有对数搜索复杂度，您还可以查看它将占用多少内存。根据您使用的机器类型，10K条目之类的条目可能有效，但1000K条目之类的条目可能无效。你知道吗

（但使用numpy或scipy可能是更好的选择）

Answer 2

字典的大小将根据您存储在其中的键的数量而定。你知道吗

如果您有2000个键（每个键都有一个(x, y)坐标，也许？）然后它的大小可以容纳2000个键（再加上一点开销，以促进未来的增长，而无需调整大小）。你知道吗

但是，如果要为矩阵中的所有10^10元素创建键（比如说，除了2000个元素以外的所有元素都引用了None），那么就有一个包含100亿个键的字典，它的大小也会相应地调整。你知道吗

使用字典构建稀疏矩阵非常简单：

class DictArray:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self._data = {}

    def _validate_coords(self, x, y):
        if not (0 <= x < self.width and 0 <= y < self.height):
            raise IndexError((x, y))

    def __getitem__(self, x_y):
        self._validate_coords(*x_y)
        return self._data.get(x_y, 0)

    def __setitem__(self, x_y, value):
        self._validate_coords(*x_y)
        if value == 0:
            try:
                del self._data[x_y]
            except KeyError:
                pass
        else:
            self._data[x_y] = value

演示：

>>> da = DictArray(10, 10)
>>> da[0, 0] = 42
>>> da[0, 4] = 81
>>> len(da._data)
2
>>> da[0, 4] = 0
>>> len(da._data)
1
>>> da._data
{(0, 0): 42}
>>> da[0, 0]
42
>>> da[0, 4]
0

不过，我强烈建议您考虑一下SciPy或NumPy，以完成这么大的任务。它们为这类任务提供了专用的数据结构，如^{} module中的数据结构。你知道吗