Есть ли другой способ избежать дублирования больших хеш-объектов?

Question

Я обрабатываю текст, и мне нужно хранить большие последовательности хешируемых объектов - иногда строки, иногда кортежи слов и т. Д. Я думал об использовании хеш-функции для обеспечения простого класса хранения и извлечения, но с моим первым подходом это Возможно, что один хэш-ключ может разрешить более одного элемента. Учитывая, что я добавляю функцию get, которая принимает возвращаемое значение add в качестве аргумента, я не могу знать, какой элемент списка вернуть.

class HashStore:
    def __init__(self):
        self.uniques = {}

    def add(self, big_hashable):
        hash_value = hash(big_hashable)
        if hash_value not in self.uniques:
            self.uniques[hash_value] = [big_hashable]
        elif big_hashable not in self.uniques[hash_value]:
            self.uniques[hash_value].append(big_hashable)

        return hash_value

Другой подход в конечном итоге гарантирует, что для каждого уникального объекта хеширования существует только одно отображение.

class SingleStore:
    def __init__(self):
        self.uniques = {}
        self.indexed = {}
        self.index = 0

    def add(self, big_hashable):
        if big_hashable not in self.uniques:
            self.index += 1
            self.uniques[big_hashable] = self.index
            self.indexed[self.index] = big_hashable

        return self.uniques[big_hashable]

Это работает и гарантирует, что возвращаемое значение add может быть использовано для возврата уникального значения. Это просто кажется немного неуклюжим. Есть ли лучший, более Pythonic способ справиться с этой ситуацией?

Я был неоднозначен относительно вопроса. Есть две проблемы - одна из них состоит в том, что у меня есть миллионы объектов, которые в настоящее время используют ключи размером от 100 до 1000 байтов каждый (вещь big_hashable). Преобразование их в целые числа позволило бы обрабатывать больше данных, чем я могу в настоящее время. Во-вторых, сохранение только одной канонической копии каждой вещи big_hashable также уменьшит использование памяти, хотя это первый вопрос, который вызывает мой вопрос, потому что каждый ключ на самом деле является отдельной копией вещи big_hashable.

Answer 1

Если вам не нужно иметь возможность эффективно извлекать каноническую копию объекта с другой копией, вы можете просто использовать набор:

s = set()
s.add(3)
s.add(3)
# s only has one 3 in it

Если вам нужно иметь возможность эффективно извлекать канонические копии объектов, не храните их по значению хеша - это будет ужасно сломано. Просто используйте hashable напрямую.

class Interner(object):
    def __init__(self):
        self._store = {}
    def canonical_object(self, thing):
        """Returns a canonical object equal to thing.

        Always returns the same result for equal things.

        """

        return self._store.setdefault(thing, thing)

С weakref модуль, вы можете улучшить это, чтобы не сохранять канонический объект, если клиентский код отпускает его, как встроенный intern Функция делает для строк.