假设有以下这样的一个结构：
{'key1' : { 'key2' : { .... { 'keyn' : 'value' } ... } } }
我正在使用Python，尝试确定两种不同方法的优缺点：
{'key1' : { 'key2' : { .... { 'keyn' : 'value' } ... } } } # A. nested dictionary
{('key1', 'key2', ...., 'keyn') : 'value'} # B. a dictionary with a tuple used like key
我很感兴趣知道，在以下方面（A或B）哪一个更好：
不深入细节（这些细节高度依赖于实现，可能会被下一个天才来调整字典实现所否定）：
你看，性能上不应该有任何明显的差异，尽管一些内存的差异可能会存在，但后者应该不明显。一个包含单个元素的字典是140字节，一个包含十个元素的元组也是140字节（根据 Python 3.2 sys.getsizeof）。因此，即使有（已经不现实的）十级嵌套，您仍然会有略微超过1KB的差异 - 如果嵌套字典具有多个项目，则可能更少（取决于确切的负载因子）。对于在内存中有数百个这样的数据结构的数据处理应用程序来说，这太多了，但大多数对象并不经常创建。
你应该简单地问问自己哪个模型更适合你的问题。请注意，使用键元组需要您一次性拥有所有值的键，而使用嵌套字典允许逐步到达。
我对一个嵌套字典和一个带有元组的字典进行了循环、检索和插入测试。它们只有一层，共2000.000个值。我还对已创建元组的元组字典进行了检索和插入。
这些是结果。我认为您无法将结论与标准差绑定在一起。
-
keydictinsertion: Mean +- std dev: 615 ms +- 42 ms
keydictretrieval: Mean +- std dev: 475 ms +- 77 ms
keydictlooping: Mean +- std dev: 76.2 ms +- 7.4 ms
nesteddictinsertion: Mean +- std dev: 200 ms +- 7 ms
nesteddictretrieval: Mean +- std dev: 256 ms +- 32 ms
nesteddictlooping: Mean +- std dev: 88.5 ms +- 14.4 ms
Test were the tuple was already created for the keydict
keydictinsertionprepared: Mean +- std dev: 432 ms +- 26 ms
keydictretrievalprepared: Mean +- std dev: 267 ms +- 14 ms
-
正如您所看到的，嵌套字典通常比单一键字典更快。即使直接为keydict提供元组而没有元组创建步骤，插入速度仍然要慢得多。似乎内部字典的额外创建成本并不高。Defaultdict可能有一个快速的实现。检索实际上几乎相等，当它不必创建元组时，循环也是如此。
使用命令行中的perf进行测试。脚本如下。
>>>>>>> nesteddictinsertion
python -m perf timeit -v -s "
from collections import defaultdict
" "
d = defaultdict(dict)
for i in range(2000):
for j in range(1000):
d[i][j] = 1
"
>>>>>>> nesteddictlooping
python -m perf timeit -v -s "
from collections import defaultdict
d = defaultdict(dict)
for i in range(2000):
for j in range(1000):
d[i][j] = 1
" "
for i, inner_dict in d.items():
for j, val in inner_dict.items():
i
j
val
"
>>>>>>> nesteddictretrieval
python -m perf timeit -v -s "
from collections import defaultdict
d = defaultdict(dict)
for i in range(2000):
for j in range(1000):
d[i][j] = 1
" "
for i in range(2000):
for j in range(1000):
d[i][j]
"
>>>>>>> keydictinsertion
python -m perf timeit -v -s "
from collections import defaultdict
" "
d = {}
for i in range(2000):
for j in range(1000):
d[i, j] = 1
"
>>>>>>> keydictinsertionprepared
python -m perf timeit -v -s "
from collections import defaultdict
keys = [(i, j) for i in range(2000) for j in range(1000)]
" "
d = {}
for key in keys:
d[key] = 1
"
>>>>>>> keydictlooping
python -m perf timeit -v -s "
from collections import defaultdict
d = {}
for i in range(2000):
for j in range(1000):
d[i, j] = 1
" "
for key, val in d.items():
key
val
"
>>>>>>> keydictretrieval
python -m perf timeit -v -s "
from collections import defaultdict
d = {}
for i in range(2000):
for j in range(1000):
d[i, j] = 1
" "
for i in range(2000):
for j in range(1000):
d[i, j]
"
>>>>>>> keydictretrievalprepared
python -m perf timeit -v -s "
from collections import defaultdict
d = {}
keys = [(i, j) for i in range(2000) for j in range(1000)]
for key in keys:
d[key] = 1
" "
for key in keys:
d[key]
"
key1到keyn的整个组合来获取value，您可以像我下面建议的那样翻转字典，其复杂度为O(nk*nv)(键的数量*值的数量)，或者使用上面的tuple方法。tuple，并且在需要获取值时再次构建，这两种方法都将是O(nk)，其中nk是键的数量。dict版本可能更节省空间，并且获取值仍然是O(nk)，但可能比元组版本慢。dict，并测试先前级别的dict的存在性。
有许多递归defaultdict的配方可以从编码角度简化插入，但实际上并不能加快速度。
tuple方法在插入时更简单、更快，但根据嵌套情况可能需要更多内存。
{'key1' : 'value', 'key2' : 'value', .... 'keyn' : 'value' }
[key for key in mydict if mydict[key] == value]
dict是错误的。您需要：{'value': [key1, key2, ... keyn]}
mydict[value].append(newkey)来添加键值，使用mydict[value]来获取所有键值，而且它们的平均时间复杂度都是O(1)。我编写了一个小脚本来进行测试。但它有一些限制，键由整数线性分布生成（即range(N)），我的发现如下。
在三级嵌套中，即dict[a][b][c]与dict[a,b,c]，其中每个子索引从0到99，我发现如下：
使用大值（list(x for x in range(100)）：
> memory.py nested 内存使用：1049.0 MB > memory.py flat 内存使用：1149.7 MB
使用小值（[]）：
> memory.py nested 内存使用：134.1 MB > memory.py flat 内存使用：234.8 MB
#!/usr/bin/env python3
import resource
import random
import itertools
import sys
import copy
from os.path import basename
from collections import defaultdict
# constants
index_levels = [100, 100, 100]
value_size = 100 # try values like 0
def memory_usage():
return resource.getrusage(resource.RUSAGE_SELF).ru_maxrss
_object_mold = list(x for x in range(value_size)) # performance hack
def create_object():
return copy.copy(_object_mold)
# automatically create nested dict
# http://code.activestate.com/recipes/578057-recursive-defaultdict/
f = lambda: defaultdict(f)
my_dict = defaultdict(f)
# options & usage
try:
dict_mode = sys.argv[1]
if dict_mode not in ['flat', 'nested']: # ugly hack
raise Error()
except:
print("Usage: {} [nested | flat]".format(basename(sys.argv[0])))
exit()
index_generator = [range(level) for level in index_levels]
if dict_mode == "flat":
for index in itertools.product(*index_generator):
my_dict[index] = create_object()
elif dict_mode == "nested":
for index in itertools.product(*index_generator):
sub_dict = my_dict
for sub_index in index[:-1]: # iterate into lowest dict
sub_dict = sub_dict[sub_index]
sub_dict[index[-1]] = create_object() # finally assign value
print("Memory usage: {:.1f} MB".format(memory_usage() / 1024**2))
tuple几乎肯定更好。 - agf