有效地访问任意深度的词典 [英] Efficiently accessing arbitrarily deep dictionaries

问题描述

假设我有一个这样的多级字典

Suppose I have a multi-level dictionary like this

mydict = {
    'first': {
        'second': {
            'third': {
                'fourth': 'the end'
             }
         }
     }
}

我想这样访问它

test = get_entry(mydict, 'first.second.third.fourth')

到目前为止，我是

def get_entry(dict, keyspec):
    keys = keyspec.split('.')

    result = dict[keys[0]]
    for key in keys[1:]:
       result = dict[key]

    return result

有更有效的方法吗?根据％timeit，函数的运行时间为1.26us，而以这种标准方式访问字典

Are there more efficient ways to do it? According to %timeit the runtime of the function is 1.26us, while accessing the dictionary the standard way like this

foo = mydict['first']['second']['third']['fourth']

需要541ns.我正在寻找将其缩小到800ns范围的方法.

takes 541ns. I'm looking for ways to trim it to 800ns range if possible.

谢谢

推荐答案

实际上只有一种解决方案.重建您的字典.但是只做一次.

There's really only one solution. Rebuild your dictionary. But do it just once.

def recursive_flatten(mydict):
    d = {}
    for k, v in mydict.items():
        if isinstance(v, dict):
            for k2, v2 in recursive_flatten(v).items():
                d[k + '.' + k2] = v2 
        else:
            d[k] = v
    return d

In [786]: new_dict = recursive_flatten(mydict); new_dict
Out[786]: {'first.second.third.fourth': 'the end'}

(更多测试)

In [788]: recursive_flatten({'x' : {'y' : 1, 'z' : 2}, 'y' : {'a' : 5}, 'z' : 2})
Out[788]: {'x.y': 1, 'x.z': 2, 'y.a': 5, 'z': 2}

In [789]: recursive_flatten({'x' : 1, 'y' : {'x' : 234}})
Out[789]: {'x': 1, 'y.x': 234}

从这里开始，每次访问都变成恒定时间.

Every access becomes constant time from here on.

现在，只需使用new_dict['first.second.third.fourth']访问您的值.应该适用于任何不包含自引用的任意嵌套字典.

Now, just access your value using new_dict['first.second.third.fourth']. Should work for any arbitrarily nested dictionary that does not contain a self-reference.

请注意，每个解决方案都有其应有的取舍，这也不例外.除非您要对数据触发数百万个查询以使预处理是可以接受的开销，否则就是这样.使用其他解决方案，您只是回避了问题，而没有解决它，这是在处理字典的结构. OTOH，如果要对许多类似的数据结构进行一次 操作，则仅对单个查询进行预处理是没有意义的，在这种情况下，您可能更喜欢其他解决方案之一.

Note that every solution has its fair share of tradeoffs, this is no exception. Unless you're firing millions of queries at your data such that preprocessing is an acceptable overhead, then this is it. With the other solutions, you are only sidestepping the problem instead of addressing it - which is dealing with the dictionary's structure. OTOH, if you're going to do this once on many such similar data structures, it make no sense to preprocess just for a single query, in which case you may prefer one of the other solutions.

这篇关于有效地访问任意深度的词典的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！