有没有办法使用O（1）中的一个键获取值时间

我正在为应用程序建模数据，并决定选择字典作为我的数据结构。但数据中的每一行都有多个键。所以，我创建了多个键映射字典的每一行，是这样的：有没有办法使用O（1）中的一个键获取值时间

>>> multiKeyDict = {} 
>>> multiKeyDict[('key1','key2','key3')] = 'value1' 
>>> multiKeyDict.get(('key1','key2','key3')) 
'value1'

现在我必须与为O key1（1）时间检索所有的值。从我的研究，我知道我能做到：

使用this包来完成这项工作，但不知道这是否是O（1）
搜索键作为这里建议：https://stackoverflow.com/a/18453567/4085019

我也打开任何更好的数据结构，而不是使用字典。

来源

2017-03-09 PseudoAj

没有，没有。 –

您提到的软件包会将键列表映射到相同的值。如果我正确理解你的问题，你想要更多某种层次结构？ –

为什么不制作2个字典？ 1如'{ 'KEY1'：[ 'VALUE1'， '值2']}'和一个像'{ '值1'：[ 'KEY1'， 'KEY2']}' –

您没有多个密钥。就Python字典而言，只有一个键，一个元组对象。除了O（N）线性时间之外，您不能搜索元组的元素。

如果你的钥匙都是独一无二的，只需要添加每个键单独：

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)

现在找了一个键为您提供了一套所有关键参考值。

如果您需要也可以组合键，那么您可以添加其他引用与这些组合。关键值配对相对便宜，都只是参考。键和值对象本身不重复。

来源

2017-03-09 14:51:56

'key1'可能有多个值，我不想将值映射到每个键，因为它不会随数据扩展 – PseudoAj

@PseudoAj：那么您没有适合散列表的数据，并且卡住了通过线性搜索这个数据结构。这同样适用于你找到的'multi_key_dict'包。 –

是的，这也是我的感觉...... – PseudoAj

另一种可能性是对共享关键组件的行对象列表建立索引。如果共享任何特定键值的行数很少，这将非常有效。（假设行对象有键访问为row.key1,row.key2等，这不是一个非常相关的细节）。未经测试的代码：

index = {} 
for row in rows: 
    index.setdefault(row.key1, []).append(row) 
    index.setdefault(row.key2, []).append(row) 
    index.setdefault(row.key3, []).append(row)

，然后查找匹配，比如说行，key2和key3

candidates = index[ key2] 
if len(index[key3]) < len(candidates): 
    candidates = index[key3] # use key3 if it offers a better distribution 
results = [] 
for cand in candidates: 
    if cand.key2 == key2 and cand.key3 == key3: # full test is necessary! 
     results.append(cand)

来源

2017-03-09 15:24:22 nigel222

有没有办法使用O（1）中的一个键获取值时间

回答

相关问题