Таблица поиска для unhashable в Python - PullRequest
Новая
       15

Таблица поиска для unhashable в Python

6 голосов
/ 16 декабря 2010

Мне нужно создать отображение из объектов моего собственного пользовательского класса (производных от dict) в объекты другого пользовательского класса.На мой взгляд, есть два способа сделать это:

  1. Я могу сделать объекты объектными.Я не уверен, как бы я это сделал.Я знаю, что могу реализовать __hash__(), но я не уверен, как на самом деле вычислить хеш (который должен быть целым числом).

  2. Поскольку мои объекты можно сравнивать, я могу составить список[(myobj, myotherobj)], а затем реализует поиск, который находит кортеж, в котором первый элемент в кортеже совпадает с ключом поиска.Реализация этого тривиальна (количество объектов невелико), но я хочу избежать повторного изобретения колеса, если что-то подобное уже существует в стандартной библиотеке.

Мне кажется, что желаниепоиск неразборчивых сообщений будет распространенной проблемой, поэтому я предполагаю, что кто-то уже решил эту проблему.Любые предложения о том, как реализовать __hash()__ для объекта, похожего на диктовку, или если есть какой-то другой стандартный способ создания таблиц поиска из неразделимых?

Ответы [ 4 ]

3 голосов
/ 16 декабря 2010

Отображения с изменяемыми объектами в качестве ключей, как правило, сложны. Это действительно то, что вы хотите? Если вы считаете, что ваши объекты неизменяемы (в Python нет способа действительно обеспечить неизменность) или вы знаете, что они не будут изменены, пока они используются в качестве ключей в отображении, вы можете реализовать для них свою собственную хеш-функцию несколько путей. Например, если ваш объект имеет только хешируемые данные-члены, вы можете вернуть хэш кортежа всех членов-данных в качестве хеша объекта.

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

def __hash__(self):
    return hash(frozenset(self.iteritems()))

Это работает, только если все значения могут быть хэшируемыми. Чтобы сохранить пересчеты хешей (что будет сделано при каждом поиске), вы можете кэшировать хеш-значение и просто пересчитать его, если установлен какой-нибудь флаг dirty.

2 голосов
/ 16 декабря 2010

Кажется, что простое решение - сделать lookup[id(myobj)] = myotherobj вместо lookup[myobj] = myotherobj. Любой комментарий по этому подходу?

1 голос
/ 16 декабря 2010

Вот реализация frozendict, взятая из http://code.activestate.com/recipes/414283/:

class frozendict(dict):
    def _blocked_attribute(obj):
        raise AttributeError, "A frozendict cannot be modified."
    _blocked_attribute = property(_blocked_attribute)

    __delitem__ = __setitem__ = clear = _blocked_attribute
    pop = popitem = setdefault = update = _blocked_attribute

    def __new__(cls, *args):
        new = dict.__new__(cls)
        dict.__init__(new, *args)
        return new

    def __init__(self, *args):
        pass

    def __hash__(self):
        try:
            return self._cached_hash
        except AttributeError:
            h = self._cached_hash = hash(tuple(sorted(self.items())))
            return h

    def __repr__(self):
        return "frozendict(%s)" % dict.__repr__(self)

Я бы заменил tuple(sorted(self.items())) на frozenset(self.iteritems()), как в Spacecowboy . И рассмотрите возможность добавления __slots__ = ("_cached_hash",) в класс.

1 голос
/ 16 декабря 2010

Следующее должно работать, если вы не храните какие-либо дополнительные не подлежащие уничтожению объекты в своем пользовательском классе: 

def __hash__(self):
    return hash(self.items())
...