我正在为应用程序建模数据,并决定选择字典作为我的数据结构。但是数据中的每一行都有多个键。所以我创建了一个字典,其中包含映射每一行的多个键,例如:
>>> multiKeyDict = {}
>>> multiKeyDict[('key1','key2','key3')] = 'value1'
>>> multiKeyDict.get(('key1','key2','key3'))
'value1'
现在我必须在 O(1) 时间内使用 key1 检索所有值。根据我的研究,我知道我可以做到:
- 使用this包来完成工作但不确定它是否是 O(1)
- 按照此处的建议搜索 key :https://stackoverflow.com/a/18453567/4085019
我也愿意接受任何更好的数据结构而不是使用字典。
请您参考如下方法:
您没有多个 key 。就Python字典而言,只有一个键,一个元组对象。除了 O(N) 线性时间之外,您无法搜索元组的组成部分。
如果您的 key 是唯一的,只需单独添加每个 key :
multiKeyDict['key1'] = multiKeyDict['key2'] = multiKeyDict['key3'] = 'value1'
现在您有 3 个键都引用一个值。此处不复制值对象,仅复制对它的引用。
您找到的 multi_key_dict 包使用中间映射将给定的组成键映射到复合键,然后再映射到值。这也为您提供了 O(1) 搜索,具有相同的限制,即每个构成键必须是唯一的。
如果您的键不是唯一的,那么您需要将每个键映射到另一个容器,然后保存值,例如一个集合:
for key in ('key1', 'key2', 'key3):
multiKeyDict.setdefault(key, set()).add(value)
现在查找一个键会为您提供该键引用的所有值的集合。
如果您也需要能够组合键,那么您可以为这些组合添加额外的引用。键值对比较便宜,都是引用。键和值对象本身不重复。
