Início / coding / Perguntas / 79595678
Accepted
SRobertJames
Asked: 2025-04-28 09:35:56 +0800 CST

Como posso armazenar IDs em Python sem pagar o preço de 28 bytes por int?

  • 772

Meu código Python armazena milhões de IDs em várias estruturas de dados para implementar um algoritmo clássico. O tempo de execução é bom, mas o uso de memória é péssimo.

Esses IDs são ints. Presumo que, como os ints do Python começam com 28 bytes e crescem, o preço é alto. Como são apenas IDs opacos, e não objetos matemáticos propriamente ditos, eu conseguiria me virar com apenas 4 bytes para eles.

Existe uma maneira de armazenar IDs em Python sem usar os 28 bytes completos? Por exemplo, preciso colocá-los como chaves e valores em dicionários?

Observação: A solução comum de usar algo como BumPy não funcionará aqui, porque não é um array contíguo. São chaves e valores em um dicionário, dicionários de dicionários, etc.

Também estou aberto a outros interpretadores Python que consomem menos memória para ints.

python

1 respostas

  1. Best Answer

    Seu caso de uso é que IDs sejam armazenados como chaves e valores de um dicionário. Mas, como as chaves e os valores de um dicionário precisam ser objetos Python, cada um deles deve receber um cabeçalho de objeto, bem como um ponteiro do dicionário.

    Para conseguir armazenar chaves e valores com 4 bytes cada, você teria que implementar uma tabela de hash personalizada que alocasse array.arrayinteiros de 32 bits para chaves e valores. Como os IDs normalmente nunca serão 0 ou 2**32-1, você pode usá-los como sentinelas para um slot vazio e um slot excluído, respectivamente.

    Abaixo está um exemplo de implementação com sondagem linear:

    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

    de modo que com pympler.asizeof, que mede recursivamente a pegada de memória de um objeto, você pode ver que a economia de memória pode chegar a 90%:

    from pympler.asizeof import asizeof

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

    Observe que em algumas plataformas o código de tipo 'L'resulta array.arrayem um tamanho de item de 8 bytes em vez de 4 bytes. Nesse caso, você deve usar o código de tipo 'I'.

    • 3

relate perguntas