Ric*_*nix 29 python recursion dictionary python-2.7
假设我有一个像这样的多级字典
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,而访问字典的标准方式是这样的
foo = mydict['first']['second']['third']['fourth']
需要541ns.如果可能的话,我正在寻找将其修剪到800ns范围的方法.
谢谢
cs9*_*s95 12
真的只有一个解决方案.重建你的字典.但只做一次.
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}
从此处开始,每次访问都是恒定的时间.
现在,只需使用即可访问您的价值new_dict['first.second.third.fourth'].应该适用于任何不包含自引用的任意嵌套字典.
请注意,每个解决方案都有其公平的权衡,这也不例外.除非你在数据上发出数百万条查询,否则预处理是一种可接受的开销,那就是这样.使用其他解决方案,您只是回避问题而不是解决它 - 这是处理字典的结构.OTOH,如果你要做到这一点,一旦在许多这样类似的数据结构,它是没有意义的预处理只是一个单一的查询,在这种情况下,你可能更喜欢另一种解决方案.
tde*_*ney 11
通过使用缓存来分割字符串,我将代码收紧了一段时间,但性能提升了20%,但是性能提升了20%.如果您多次使用相同的规格,那只会产生影响.以下是示例实现和要测试的配置文件脚本.
test.py
mydict = {
'first': {
'second': {
'third': {
'fourth': 'the end'
}
}
}
}
# original
def get_entry(dict, keyspec):
keys = keyspec.split('.')
result = dict[keys[0]]
for key in keys[1:]:
result = result[key]
return result
# tighten up code
def get_entry_2(mydict, keyspec):
for key in keyspec.split('.'):
mydict = mydict[key]
return mydict
# use a cache
cache = {}
def get_entry_3(mydict, keyspec):
global cache
try:
spec = cache[keyspec]
except KeyError:
spec = tuple(keyspec.split('.'))
cache[keyspec] = spec
for key in spec:
mydict = mydict[key]
return mydict
if __name__ == "__main__":
test = get_entry(mydict, 'first.second.third.fourth')
print(test)
profile.py
from timeit import timeit
print("original get_entry")
print(timeit("get_entry(mydict, 'first.second.third.fourth')",
setup="from test import get_entry, mydict"))
print("get_entry_2 with tighter code")
print(timeit("get_entry_2(mydict, 'first.second.third.fourth')",
setup="from test import get_entry_2, mydict"))
print("get_entry_3 with cache of split spec")
print(timeit("get_entry_3(mydict, 'first.second.third.fourth')",
setup="from test import get_entry_3, mydict"))
print("just splitting a spec")
print(timeit("x.split('.')", setup="x='first.second.third.fourth'"))
我机器上的时间是
original get_entry
4.148535753000033
get_entry_2 with tighter code
3.2986323120003362
get_entry_3 with cache of split spec
1.3073233439990872
just splitting a spec
1.0949148639992927
请注意,拆分规范对于此功能来说是相对昂贵的操作.这就是缓存有帮助的原因.
use*_*203 10
我更新了如何使用点"答案"的答案.访问字典成员？使用初始转换,然后将用于嵌套字典:
您可以使用以下类来允许字典的点索引:
class dotdict(dict):
"""dot.notation access to dictionary attributes"""
__getattr__ = dict.get
__setattr__ = dict.__setitem__
__delattr__ = dict.__delitem__
但是,如果所有嵌套字典也是类型,则仅支持嵌套dotdict.这就是以下辅助函数的用武之地:
def dct_to_dotdct(d):
if isinstance(d, dict):
d = dotdict({k: dct_to_dotdct(v) for k, v in d.items()})
return d
此函数必须在嵌套字典上运行一次,然后可以使用点索引对结果进行索引.
这里有些例子:
In [13]: mydict
Out[13]: {'first': {'second': {'third': {'fourth': 'the end'}}}}
In [14]: mydict = dct_to_dotdct(mydict)
In [15]: mydict.first.second
Out[15]: {'third': {'fourth': 'the end'}}
In [16]: mydict.first.second.third.fourth
Out[16]: 'the end'
关于性能的说明:与标准字典访问相比,这个答案很慢,我只是想提供一个实际上对字典使用"点访问"的选项.
这是一个类似于chrisz的解决方案,但你不需要事先做任何事情.:
class dictDotter(dict):
def __getattr__(self,key):
val = self[key]
return val if type(val) != dict else dictDotter(val)
,只是x=dictDotter(originalDict)会让你有任意点得到(`x.first.second ...).我会注意到它的速度是chrisz解决方案的两倍,而且速度是你的速度的9倍(在我的机器上,大约是).
所以,如果你坚持做这项工作,@ tdelaney似乎提供了唯一真正的性能提升.
另一种选择比你拥有的更好(就运行时而言):
class dictObjecter:
def __init__(self,adict):
for k,v in adict.items():
self.__dict__[k] = v
if type(v) == dict: self.__dict__[k] = dictObjecter(v)
这将使你的dict中出现一个物体,所以点符号通常是正常的.这样可以将运行时间提高到你所拥有的3倍,所以不坏,但代价是要超越你的dict,并用其他东西替换它.
这是总测试代码:
from timeit import timeit
class dictObjecter:
def __init__(self,adict):
for k,v in adict.items():
self.__dict__[k] = v
if type(v) == dict: self.__dict__[k] = dictObjecter(v)
class dictDotter(dict):
def __getattr__(self,key):
val = self[key]
return val if type(val) != dict else dictDotter(val)
def get_entry(dict, keyspec):
keys = keyspec.split('.')
result = dict[keys[0]]
for key in keys[1:]:
result = result[key]
return result
class dotdict(dict):
"""dot.notation access to dictionary attributes"""
__getattr__ = dict.get
__setattr__ = dict.__setitem__
__delattr__ = dict.__delitem__
def dct_to_dotdct(d):
if isinstance(d, dict):
d = dotdict({k: dct_to_dotdct(v) for k, v in d.items()})
return d
x = {'a':{'b':{'c':{'d':1}}}}
y = dictDotter(x)
z = dct_to_dotdct(x)
w = dictObjecter(x)
print('{:15} : {}'.format('dict dotter',timeit('y.a.b.c.d',globals=locals(),number=1000)))
print('{:15} : {}'.format('dot dict',timeit('z.a.b.c.d',globals=locals(),number=1000)))
print('{:15} : {}'.format('dict objecter',timeit('w.a.b.c.d',globals=locals(),number=1000)))
print('{:15} : {}'.format('original',timeit("get_entry(x,'a.b.c.d')",globals=locals(),number=1000)))
print('{:15} : {:.20f}'.format('best ref',timeit("x['a']['b']['c']['d']",globals=locals(),number=1000)))
我提供了最后一次常规查找作为最佳参考.Windows Ubuntu子系统上的结果:
dict dotter : 0.0035500000003594323
dot dict : 0.0017939999997906853
dict objecter : 0.00021699999979318818
original : 0.0006629999998040148
best ref : 0.00007999999979801942
因此,客观化的字典是常规字典查找的3倍 - 所以如果速度很重要,为什么要这样呢？