набор объектов Python с пользовательским хеш-поведением - PullRequest
Новая
       16

набор объектов Python с пользовательским хеш-поведением

0 голосов
/ 25 июня 2018

Я хотел бы использовать набор для управления коллекцией экземпляров myItem.Класс myItem имеет свою собственную хэш-функцию.Хеш этих элементов основан на некоторых, но не на всех данных в каждом элементе, для простоты в приведенном ниже примере «data» - это словарь r.Хеш учитывает 2 ключа, hk1 и hk2, и есть третий ключ 'sad', который не учитывается при вычислении хеша. 

class myItem():

    def __init__(self, r):
        # r is a dict holding information about the instance
        # of course r has to have certain keys...
        self.r = r

    def __hash__(self):
        """Override the default hash behavior"""
        return hash(tuple(sorted([self.r['hk1'],self.r['hk2']])))

    def __eq__(self,other):
        """checking equality"""
        if isinstance(other, self.__class__):
            return self.__hash__() == other.__hash__()
        return NotImplemented

    def __ne__(self, other):
        """checking inequality"""
        if isinstance(other, self.__class__):
            return not self.__eq__(other)
        return NotImplemented

    def __repr__(self):
        return str(self.r)

Ожидаемое поведение подтверждается кратким модульным тестом, приведенным ниже.. 

class testMySet(unittest.TestCase):

    def testMyItemstuff(self):

        m1 = myItem({'hk1':'val1', 'hk2': 100, 'sad': 'other stuff'})
        m2 = myItem({'hk1': 'val1', 'hk2': 100, 'sad': 'different other stuff'})

        self.assertEqual(m1, m2)
        self.assertNotEqual(m1.r['sad'], m2.r['sad'])

        s = { m1 }
        # add m2 to s
        s.add(m2)
        # same hash, m2 is not added
        self.assertEqual(len(s), 1)
        # set contains the original object, not the last one added
        self.assertNotEqual(s.pop().r['sad'], 'different other stuff')

Мой вопрос заключается в том, как я могу изменить поведение так, чтобы добавление нового объекта, хэш которого совпадает с существующим, заканчивал тем, что заменял исходный, с минимальным влиянием на производительность?

Ответы [ 2 ]

0 голосов
/ 25 июня 2018

Является ли определение вашего хеша таким способом, имеет ли смысл для вашего приложения, решать вам, но это кажется маловероятным.

В любом случае, я могу представить два варианта, которые будут «такими же быстрыми, как» набором - O (1) вместо O (n) - и их скорость зависит от реализации хэш-функции, как вы описываете:

Во-первых, сведи свой класс и создай экземпляры: 

class Item():
    def __init__(self, a, b):
        self.a = a
        self.b = b

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

    def __eq__(self,other):
        if isinstance(other, self.__class__):
            # Ignoring .b attribute
            return self.a == other.a
        else:
            return NotImplemented

    def __repr__(self):
        return "Item(%s, %s)" % (self.a, self.b)

i1 = Item(1,2)
i2 = Item(3,4)
i3 = Item(1,5)


print(i1 == i2)             # False (.a's don't match)
print(i1 == i3)             # True  (.a's match)

Метод 1: значения dict 

# Using a dict
updating_set = {}
updating_set[i1] = i1       # .values(): [Item(1, 2)]
updating_set[i2] = i2       # .values(): [Item(1, 2), Item(3, 4)]
updating_set[i3] = i3       # .values(): [Item(1, 5), Item(3, 4)]

print(list(updating_set.values()))
# [Item(1, 5), Item(3, 4)]

Способ 2. Использование подкласса набора 

# Using a set subclass
class UpdatingSet(set):
    def add(self, item):
        if item in self: super().remove(item)
        super().add(item)

uset = UpdatingSet()
uset.add(i1)                # UpdatingSet({Item(1, 2)})
uset.add(i2)                # UpdatingSet({Item(1, 2), Item(3, 4)})
uset.add(i3)                # UpdatingSet({Item(1, 5), Item(3, 4)})

Бонусный метод 3: Не требует специальной хэш-функции 

class NewItem():
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __repr__(self):
        return "Item(%s, %s)" % (self.a, self.b)

class ItemSet():
    def __init__(self):
        self.items = {}

    def add(self, item):
        item_hash = item.a
        self.items[item_hash] = item

    def values(self):
        return self.items.values()

i1 = NewItem(1,2)
i2 = NewItem(3,4)
i3 = NewItem(1,5)

iset = ItemSet()
iset.add(i1)                # .values(): [Item(1, 2)]
iset.add(i2)                # .values(): [Item(1, 2), Item(3, 4)]
iset.add(i3)                # .values(): [Item(1, 5), Item(3, 4)]

print(list(iset.values()))  # [Item(1, 5), Item(3, 4)]

Этот третий подход не требует от вас реализации хеша (который может вызвать неожиданные побочные эффекты, но имитирует процесс хеширования внутри ItemSet.add(), используя «хэш-функцию» в качестве ключа словаря.

Это, вероятно, ваша лучшая ставка, если вы действительно не хотите внедрить хэш и не знаете, каковы последствия этого решения.

0 голосов
/ 25 июня 2018

Вы можете реализовать свой собственный set производный: 

class CustomSet(set):
    def add(self, item):
        self.discard(item)
        super().add(item)

Обратите внимание, что это зависит от того факта, что, как вы показали в своем примере, два элемента сравниваются равными, если и только если их хеши сравниваются равными.

Это не то, как встроенные контейнеры на основе хеша предназначены для использования, хотя. Они используют хеши для быстрого поиска, а в случае коллизий они используют сравнение на равенство, чтобы разрешить конфликт (т. Е. Проверить, действительно ли это равенство).

Если __eq__ зависит от чего-то другого, кроме хэша, то вам также необходимо отслеживать хэши (например, в форме dict): 

class CustomSet(set):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self._hashes = {}

    def add(self, item):
        self.discard(self._hashes.get(hash(item)))
        self._hashes[hash(item)] = item
        super().add(item)

    # Similarly implement the following methods to update self._hashes:
    #   * clear
    #   * discard
    #   * pop
    #   * remove
...