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

Я обрабатываю текст и мне нужно хранить большие последовательности хэшируемых объектов - иногда строки, иногда кортежи слов и т. д. Я думал об использовании хеш-функции для предоставления простого класса хранения и извлечения, но с моим первым подходом это возможно, что один хэш-ключ может разрешаться более чем в один элемент. Учитывая, что я добавляю функцию 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.


python hashable duplication
person bmacnaughton    schedule 23.08.2013    source источник
comment
По какой-то конкретной причине вы не просто используете набор Python?   -  person Peter DeGlopper    schedule 23.08.2013
comment
@PeterDeGlopper: вы можете проверить, находится ли объект в наборе, но вы не можете эффективно получить копию объекта из набора.   -  person user2357112 supports Monica    schedule 23.08.2013
comment
Тем не менее, я не уверен, требует ли вопрос этой функциональности. Сначала я интерпретировал это как интернирование строк, и в этом случае вы хотели бы иметь возможность эффективно извлекать каноническую копию объекта, но теперь я не уверен.   -  person user2357112 supports Monica    schedule 23.08.2013
comment
@user2357112 user2357112 Верно, хотя я не вижу требования для этого в вопросе (и хотя я могу придумать случаи, когда это может иметь значение, я не могу придумать ни одного хорошего варианта использования). В любом случае, если вам это нужно, вы можете просто использовать словарь и сохранить канонический объект как значение.   -  person    schedule 23.08.2013
comment
@delnan: Мне кажется, что OP хочет сохранить последовательность больших хэшируемых объектов, некоторые из которых могут быть равными, и хочет использовать только одну копию одинаковых объектов. Для этого потребуется возможность получить каноническую копию. Тем не менее, это, вероятно, преждевременная оптимизация.   -  person user2357112 supports Monica    schedule 23.08.2013
comment
Существует несколько стратегий коллизий для хеш-таблиц с большим количеством примеров кода. На самом деле, где-то в ActiveState есть рецепт хеш-таблицы на чистом Python с точно такой же стратегией коллизий, что и в реализациях CPython 2.something dict и set. Но сделать это, очевидно, будет точно так же, как просто использовать dict или set, за исключением того, что это намного медленнее и сложнее, что является довольно хорошим аргументом в пользу использования dict или set в зависимости от ситуации…   -  person abarnert    schedule 24.08.2013
comment
каждый ключ на самом деле является отдельной копией объекта big_hashable, если вы не канонизируете их.   -  person user2357112 supports Monica    schedule 24.08.2013
comment
Спасибо. Я понимаю вашу точку зрения - я не следовал ей до сих пор.   -  person bmacnaughton    schedule 24.08.2013

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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 для строк.

person user2357112 supports Monica    schedule 23.08.2013
comment
Поясню вопрос и причину. Я извиняюсь за то, что не был более ясным для начала. - person bmacnaughton; 24.08.2013
comment
класс Interner отвечает на мой вопрос. Спасибо. - person bmacnaughton; 24.08.2013