在Python中进行配对查找的良好数据结构是什么？

Question

由 paigh-key 我的意思是两个键，作为一个映射到单个值的一对。

F.EX我可以使用一组字符串作为键，我可以通过迭代搜索，尽管我想知道它是一种更好的方法来构造数据并根据一个或两个键之一找到对。

d = {
    {"a", "b"}: "a-b relationship",
    {"c", "d"}: "c-d relationship",
    {"e", "f"}: "e-f relationship"
}

# single key
query = "a"
match = [v for k, v in d.items() if query in k]

# both keys
query = {"a", "b"}
match = [v for k, v in d.items() if query == k]

Answer 1

最简单的版本将仅使用 >作为键：

my_dict = {
    frozenset({"a", "b"}): "a-b relationship",
    frozenset({"c", "d"}): "c-d relationship",
    frozenset({"e", "f"}): "e-f relationship"
}

# both keys
my_dict[frozenset({"a", "b"})]
'a-b relationship'

# single key
[v for k, v in my_dict.items() if "a" in k]
['a-b relationship']

但是您也可能想尝试自己制作自己的dict类似于 collections.abc ：

import collections.abc as abc

class pair_dict(abc.MutableMapping):

    def __init__(self):
        self._pairs = {}
        self._singles = {}
        super().__init__()

    def __getitem__(self, key):
        if isinstance(key, abc.Iterable) and not isinstance(key, str):
            return self._pairs[frozenset(key)]
        return set(self._singles[key].values())

    def __setitem__(self, key, value):
        if isinstance(key, abc.Iterable) and not isinstance(key, str):
            key = frozenset(key)
            self._pairs[key] = value
            for k in key:
                self._singles.setdefault(k, {})[key] = value
        else:
            raise ValueError('key must be an iterable, not just a string')

    def __delitem__(self, key):
        if isinstance(key, abc.Iterable) and not isinstance(key, str):
            key = frozenset(key)
            del self._pairs[key]
            for k in key:
                del self._singles.setdefault(k, {})[key]
        else:
            raise ValueError('key must be an iterable, not just a string')

    def __iter__(self):
        return iter(self._pairs)

    def __len__(self):
        return len(self._pairs)

然后，您可以将类用于两个目的：

d = pair_dict()
d[('a', 'b')] = 'AB'
d[('b', 'c')] = 'BC'
d[('a', 'c')] = 'AC'

list(d.items())
[(frozenset({'a', 'b'}), 'AB'),
 (frozenset({'b', 'c'}), 'BC'),
 (frozenset({'a', 'c'}), 'AC')]

d[('a', 'b')]
'AB'

d['a']
{'AB', 'AC'}

collections.abc a list of which methods you have to override for each abstract base class (abc) it provides

您还需要添加其他便利方法，例如__ epr __和/或__ str __，如果您将其用作公共面向公共的类。

注意：我使用了一个单独的内部dict和的dict> dict的dict ，用于。这使单个查找的速度更快，但要付出少量的额外内存使用，并使项目设置较慢。调整您的用例。 =）

Answer 2

这是一个建议，编写您的addKeypair函数以覆盖d [（a，b）] = v的行为。

def addKeyPair(d, a, b, v):
    d[(a,b)] = v
    d[(b,a)] = v
    d.setdefault(a, []).append(v)
    d.setdefault(b, []).append(v)

d = {}
for a,b in ('ab', 'bc', 'ca'):
    addKeyPair(d, a, b, a+b)

print(d)
# {('a', 'b'): 'ab', ('b', 'a'): 'ab', 'a': ['ab', 'ca'],
#  'b': ['ab', 'bc'], ('b', 'c'): 'bc', ('c', 'b'): 'bc',
#  'c': ['bc', 'ca'], ('c', 'a'): 'ca', ('a', 'c'): 'ca'}

print(d[('a', 'b')])
# ab

print(d[('b', 'a')])
# ab

print(d['a'])
# ['ab', 'ca']