python - 二维字典或其他键顺序无关紧要的数据结构

Question

我想创建一个数据结构，可以接受一对键(字符串)并返回一个值(也可以是字符串)。无论输入 2 个键的顺序如何，我都想返回相同的值(例如，data[key1][key2] 返回与 data[key2][key1] 相同的值)。这个描述有术语/概念吗？

我目前的实现是像这样创建一个 2D 字典:

my_dict = {'key1': {'key1': None,
                    'key2': 'foo',
                    ...
                    'keyn': 'bar'},
           'key2': {'key1': 'foo',
                    'key2': None,
                    ...
                    'keyn': 'baz'},
           ...
           'keyn': {'key1': 'bar',
                    'key2': 'baz',
                    ...
                    'keyn': None}}

# Calling my_dict['key1']['key2'] and my_dict['key2']['key1'] both return 'foo', which is what I want and expect.

这对我来说似乎不对。我正在复制数据，并且在只需要 (n * (n - 1))/2 时创建 n * n 个条目。

所以，我尝试创建一个一维字典，其中键是一个元组:

my_dict = {('key1', 'key2'): 'foo'}

但这不起作用，因为调用 my_dict[('key2', 'key1')] 给我一个 KeyError

一维元组字典的一个解决方法是创建一个 try/except。

def get_value(my_dict, key1, key2):
    try:
        return my_dict[key1][key2]
    except KeyError:
        return my_dict[key2][key1]

这看起来不直观，感觉更像是解决问题的“创可贴”。

我没有测试过的一种方法是 1D 字典，其中键使用自定义类的实例，该类包含 key1 和 key2 作为属性。为了做到这一点，对象必须是不可变的和可散列的，其中散列函数将使用对象的属性并生成相同的“散列键”，而不管属性的顺序如何。我以前从未这样做过，也不知道该怎么做。这是正确的方法吗？我觉得自己很愚蠢，因为我一直没能弄清楚这个问题，因为似乎有一个简单的答案。

Answer 1

如果您希望键无论顺序如何都相等，您可以使用 frozensets 作为键，这符合您对自定义类的想法:

my_dict = {frozenset(['key1', 'key2']): 'foo'}

添加键的顺序无关紧要:

In [44]: my_dict = {frozenset(['key1', 'key2']): 'foo'}

In [45]: k = frozenset(["key1","key2"])

In [46]: k2 = frozenset(["key2","key1"])

In [47]: my_dict[k]
Out[47]: 'foo'

In [48]: my_dict[k2]
Out[48]: 'foo'

您可以在 frozenset 中拥有任意数量的值，它们仍然比较相等，使用 frozen set 对查找也很有效:

In [55]: timeit my_dict[k]
10000000 loops, best of 3: 103 ns per loop

In [56]: timeit get_value(my_dict, 'key1', 'key2')
1000000 loops, best of 3: 455 ns per loop

In [57]: timeit get_value(my_dict, 'key2', 'key1')
1000000 loops, best of 3: 455 ns per loop

即使对 frozenet 的创建和两个元素的查找进行计时也更快:

In [5]: my_dict = {frozenset(['key1', 'key2']): 'foo'}

In [6]: timeit my_dict[frozenset(["key1","key2"])]
1000000 loops, best of 3: 380 ns per loop

只需 3 个字符串，您就有 3 个!允许检查，对于 6，你有 720，所以对于超过一对的任何东西，检查每个可能的排列是不现实的或远程有效的。