-6

在下面给出一个元组：

({15: None}, 
{7: None}, 
{2: None, 3: None, 4: None, 7: None, 13: None, 15: None}, 
{13: None}, 
{4: None}, 
{7: None}, 
{15: None}, 
{15: None, 4: None, 13: None, 7: None}, 
{15: None, 4: None, 7: None}, 
{7: None}, 
{4: None}, 
{4: None}, 
{4: None, 7: None}, 
{4: None})

算法：

for tail in xrange(len(tupe_above), -1, -1):
   for _ in tuple_above[tail].iteritems():
      for head in xrange(0, tail):         
         if _[0] in head:
            print 'got one ...'

问题：

在我的脑海中强烈的感觉，必须有一种方法可以在线性时间内完成这项工作（假设使用更高层的字典），任何人都可以给我一个建议吗？谢谢。

4

2 回答 2

1

我会尽力理解你的问题。你是否试图从这个元组中找到所有dict包含给定键（如）的 s ？18

我认为最符合 Pythonic 的解决方案是：

def getDictsWithKey(dictTuple, key):
    return [d for d in dictTuple if key in d]
于 2013-09-16T01:55:31.917 回答
1

我不确定我是否理解你的“职位描述”，但我认为你想要这个：

def find_matches(tuple_of_dicts, key_to_find):
    return [d for d in tuple_of_dicts if key_to_find in d]

所以：

>>> tuple_of_dicts = ({18: None}, {10: None}, {16: None, 18: None, 5: None, 6: None, 7: None, 10: None}, {16: None}, {7: None}, {10: None}, {18: None}, {16: None, 10: None, 18: None, 7: None}, {10: None, 18: None, 7: None}, {10: None}, {7: None}, {7: None}, {10: None, 7: None}, {7: None})
>>> find_matches(tuple_of_dicts, 18)
[{18: None},
 {5: None, 6: None, 7: None, 10: None, 16: None, 18: None},
 {18: None},
 {7: None, 10: None, 16: None, 18: None},
 {7: None, 10: None, 18: None}]

这在线性时间内有效。如果你的元组有 N 个字典，每个平均有 M 个成员，你遍历元组，为每次迭代做一个恒定时间的字典查找，总共 O(N)。

但是，如果您要进行大量此类搜索，您甚至可以做得比线性时间更好。

诀窍是（听起来您可能已经怀疑）构建一个索引字典，将每个键映射到它所在的字典的索引，或者只是映射到字典本身。例如：

>>> dict_of_dicts = {}
>>> for d in tuple_of_dicts:
...     for key in d:
...         dict_of_dicts.setdefault(key, []).append(d)
>>> def find_matches(dict_of_dicts, key_to_find):
...     return dict_of_dicts[key_to_find]

这需要 O(N*M) 时间来完成设置工作，并构建一个 O(N*M) 空间的字典，* 但它是每次搜索的简单 O(1) 字典查找。因此，只要您执行的搜索次数超过 M 次，并且您能负担得起额外的空间，这就是巨大的收益。

* 准确地说：如果你有 L 个不同的键，总共 M 个键，你在一个字典中进行 N*M 查找，N*M/L 添加到字典中，N*M 追加到 M/L 长度的列表中. 由于列表追加是摊销的常数时间，即 O(N*M + N*M/L + N*M) = O(N*M) 设置时间。同时，dict是O(N*L)空间，每个成员是一个长度为O(M/L)的列表，所以列表使用的总空间是O(N*L * M/L) = O( N*M)，字典及其列表的总空间为 O(N*L + N*M) = O(N*M)。最后，搜索只是对值进行哈希处理，在 dict 中查找，并返回对 M/L 长度列表的引用，所有这些都是恒定时间的操作，因此每次搜索都是 O(1)。

于 2013-09-16T01:55:49.683 回答