Симметричный словарь, где d [a] [b] == d [b] [a]

Question

У меня есть алгоритм в Python, который создает меры для пар значений, где m(v1, v2) == m(v2, v1) (т.е. это симметрично).У меня была идея написать словарь словарей, в котором эти значения хранятся с эффективным использованием памяти, чтобы их можно было легко найти с ключами в любом порядке.Мне нравится наследовать от вещей, и в идеале я хотел бы написать symmetric_dict, где s_d[v1][v2] всегда равно s_d[v2][v1], вероятно, проверяя, какое из v больше в соответствии с каким-либо отношением порядка, а затем переключая ихвокруг, так что меньший элемент один всегда упоминается первым.т. е. при вызове s_d[5][2] = 4, диктат диктов перевернет их так, что они фактически будут храниться как s_d[2][5] = 4, так и для извлечения данных.Я также очень открыт для лучшей структуры данных, но я бы предпочел реализацию с отношением «is-a» чему-то, что просто использует dict и предварительно обрабатывает некоторые аргументы функции.

Answer 1

Вы могли бы использовать frozenset в качестве ключа для своего диктанта:

>>> s_d = {}
>>> s_d[frozenset([5,2])] = 4
>>> s_d[frozenset([2,5])]
4

Было бы довольно просто написать подкласс dict, который принял бы итерации в качестве ключааргументы, а затем превращаются затем в frozenset при сохранении значений:

class SymDict(dict):
    def __getitem__(self, key):
        return dict.__getitem__(self, frozenset(key))

    def __setitem__(self, key, value):
        dict.__setitem__(self, frozenset(key), value)

, что дает вам:

>>> s_d = SymDict()
>>> s_d[5,2] = 4
>>> s_d[2,5]
4

Answer 2

Выполнение с вложенной индексацией, как показано, будет чрезвычайно трудным.Вместо этого лучше использовать кортеж в качестве ключа.Таким образом, можно отсортировать кортеж и получить доступ к инкапсулированному dict значению.

d[2, 5] = 4
print d[5, 2]

Answer 3

Улучшение в решении Джастина Пила, вам нужно добавить __delitem__ и __contains__ методы для работы нескольких словарных операций. Итак, для полноты

class SymDict(dict):
    def __getitem__(self, key):
        return dict.__getitem__(self, key if key[0] < key[1] else (key[1],key[0]))

    def __setitem__(self, key, value):
        dict.__setitem__(self, key if key[0] < key[1] else (key[1],key[0]), value)

    def __delitem__(self, key):
        return dict.__delitem__(self, key if key[0] < key[1] else (key[1],key[0]))

    def __contains__(self, key):
        return dict.__contains__(self, key if key[0] < key[1] else (key[1],key[0]))

Итак,

>>> s_d = SymDict()
>>> s_d[2,5] = 4
>>> s_d[5,2]
4
>>> (5,2) in s_d
True
>>> del s_d[5,2]
>>> s_d
{}

Хотя я не уверен, охватывает ли это все основы, но этого было достаточно для моего собственного кода.

Answer 4

Вот немного другой подход, который выглядит многообещающим.Хотя класс SymDict не является подклассом dict, он в основном ведет себя как один, и в нем задействован только один частный словарь.Я думаю, что одной интересной особенностью является тот факт, что он сохраняет естественный синтаксис поиска [][], который, как вы, казалось, хотите.

class SymDict(object):
    def __init__(self, *args, **kwrds):
        self._mapping = _SubSymDict(*args, **kwrds)
    def __getitem__(self, key1):
        self._mapping.set_key1(key1)
        return self._mapping
    def __setitem__(self, key1, value):
        raise NotImplementedError
    def __str__(self):
        return '_mapping: ' + self._mapping.__str__()
    def __getattr__(self, name):
        return getattr(self._mapping, name)

class _SubSymDict(dict):
    def __init__(self, *args, **kwrds):
        dict.__init__(self, *args, **kwrds)
    def set_key1(self, key1):
        self.key1 = key1
    def __getitem__(self, key2):
        return dict.__getitem__(self, frozenset((self.key1, key2)))
    def __setitem__(self, key2, value):
        dict.__setitem__(self, frozenset((self.key1, key2)), value)

symdict = SymDict()
symdict[2][4] = 24
symdict[4][2] = 42

print 'symdict[2][4]:', symdict[2][4]
# symdict[2][4]: 42
print 'symdict[4][2]:', symdict[4][2]
# symdict[4][2]: 42
print 'symdict:', symdict
# symdict: _mapping: {frozenset([2, 4]): 42}

print symdict.keys()
# [frozenset([2, 4])]

Answer 5

Так же, как альтернатива морозилке Дейва Уэбба, почему бы не сделать SymDict, как показано ниже:

class SymDict(dict):
    def __getitem__(self, key):
        return dict.__getitem__(self, key if key[0] < key[1] else (key[1],key[0]))

    def __setitem__(self, key, value):
        dict.__setitem__(self, key if key[0] < key[1] else (key[1],key[0]), value)

При быстром тестировании это более чем на 10% быстрее для получения и настройки предметов, чем при использовании Frozenset. Во всяком случае, просто другая идея. Тем не менее, он менее адаптивен, чем frozenset, так как он действительно настроен для использования только с кортежами длины 2. Насколько я могу судить из OP, здесь, похоже, нет проблемы.

Answer 6

Я бы извлек функцию для большей читабельности (для ответа Патварили)

class SymDict(dict):
def __getitem__(self, key):
    return dict.__getitem__(self, self.symm(key))

def __setitem__(self, key, value):
    dict.__setitem__(self, self.symm(key), value)

def __delitem__(self, key):
    return dict.__delitem__(self, self.symm(key))

def __contains__(self, key):
    return dict.__contains__(self, self.symm(key))


@staticmethod
def symm(key):
    return key if key[0] < key[1] else (key[1], key[0]).

Answer 7

Очевидной альтернативой является использование кортежа (v1,v2) в качестве ключа в едином стандарте dict и вставка (v1,v2) и (v2,v1) в словарь, заставляя их ссылаться на один и тот же объект справа.