主页 / coding / 问题 / 79595678
Accepted
SRobertJames
Asked: 2025-04-28 09:35:56 +0800 CST

如何在 Python 中存储 ID，而不必支付每个整数 28 字节的费用？

  • 772

我的 Python 代码将数百万个 ID 存储在各种数据结构中，以实现一个经典算法。运行时间还不错，但内存占用却很糟糕。

这些 id 是ints。我猜想，由于 Python 的 int 类型起始于 28 个字节，并且会不断增长，因此代价非常大。由于它们只是不透明的 id，而不是真正的数学对象，所以我只用 4 个字节就可以了。

有没有一种方法可以在 Python 中存储 ID，而不用占用全部 28 个字节？例如，我是否需要将它们同时作为字典的键和值？

注意：像 BumPy 这样的常见解决方案在这里不起作用，因为它不是一个连续的数组。它是将键和值放入一个字典中，或者放入字典的字典中，等等。

我也乐意接受其他对 int 占用内存较少的 Python 解释器。

python

1 个回答

  1. Best Answer

    您的用例是将 ID 存储为字典的键和值。但是，由于字典的键和值必须是 Python 对象，因此必须为每个键和值分配一个对象头以及一个来自字典的指针。

    为了能够真正以 4 个字节存储键和值，您必须实现一个自定义哈希表，array.array为键和值分配一个 32 位整数。由于 ID 通常不会是 0 或 2**32-1，因此您可以将它们分别用作空槽和已删除槽的标记。

    以下是线性探测的示例实现：

    from array import array

class HashTable:
    EMPTY = 0
    DELETED = (1 << 31) - 1

    def __init__(self, source=None, size=8, load_factor_threshold=0.75):
        self._size = size
        self._load_factor_threshold = load_factor_threshold
        self._count = 0
        self._keys = array('L', [self.EMPTY]) * size
        self._values = array('L', [self.EMPTY]) * size
        if source is not None:
            self.update(source)

    def _probe(self, key):
        index = hash(key) % self._size
        for _ in range(self._size):
            yield index, self._keys[index], self._values[index]
            index = (index + 1) % self._size

    def __setitem__(self, key, value):
        while self._count >= self._load_factor_threshold * self._size:
            new = HashTable(self, self._size * 2, self._load_factor_threshold)
            self._size = new._size
            self._keys = new._keys
            self._values = new._values
        for index, probed_key, probed_value in self._probe(key):
            if probed_value == self.DELETED:
                continue
            if probed_value == self.EMPTY:
                self._keys[index] = key
                self._values[index] = value
                self._count += 1
                return
            elif probed_key == key:
                self._values[index] = value
                return

    def __getitem__(self, key):
        for _, probed_key, value in self._probe(key):
            if value == self.EMPTY:
                break
            if value == self.DELETED:
                continue
            if probed_key == key:
                return value
        raise KeyError(key)

    def __delitem__(self, key):
        for index, probed_key, value in self._probe(key):
            if value == self.EMPTY:
                raise KeyError(key)
            if value == self.DELETED:
                continue
            if probed_key == key:
                self._values[index] = self.DELETED
                self._count -= 1
                return

    def items(self):
        for key, value in zip(self._keys, self._values):
            if value not in (self.EMPTY, self.DELETED):
                yield key, value

    def keys(self):
        for key, _ in self.items():
            yield key

    def values(self):
        for _, value in self.items():
            yield value

    def __iter__(self):
        yield from self.keys()

    def __len__(self):
        return self._count

    def __eq__(self, other):
        return set(self.items()) == set(other.items())

    def __contains__(self, key):
        try:
            self[key]
        except KeyError:
            return False
        return True

    def get(self, key, default=None):
        try:
            return self[key]
        except KeyError:
            return default

    def __repr__(self):
        return repr(dict(self.items()))

    def __str__(self):
        return repr(self)

    def copy(self):
        return HashTable(self, self._size, self._load_factor_threshold)

    def update(self, other):
        for key, value in other.items():
            self[key] = value

    因此pympler.asizeof，使用递归测量对象的内存占用量，您可以看到内存节省高达 90%：

    from pympler.asizeof import asizeof

d = dict(zip(range(1500000), range(1500000)))
h = HashTable(d)
print(asizeof(d)) # 179877936
print(asizeof(h)) # 16777920

    请注意，在某些平台上，类型代码'L'会导致array.array项目大小为 8 个字节而不是 4 个字节，在这种情况下您应该使用类型代码'I'。

    • 3

相关问题