用于键的嵌套字典或元组？

Question

假设有一个这样的结构：

{'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）：

• 内存占用
• 插入的复杂性（考虑避免冲突的算法等...）
• 查找的复杂性

Answer 1

性能测试

我对一个嵌套字典和一个包含元组的字典进行了循环、取值和插入的测试。它们的结构都是一层深，包含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

-

从结果来看，嵌套字典通常比只有一个键的字典要快。即使直接给键字典一个元组，而不经过元组创建的步骤，插入速度仍然慢很多。看起来，额外创建一个内部字典的成本并不高。默认字典的实现可能比较快。在没有创建元组的情况下，取值的速度几乎是一样的，循环的速度也是如此。

测试是通过命令行的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]
"

Answer 2

如果你需要用所有的 key1 到 keyn 的组合来获取 value，你可以像我下面提到的那样翻转字典，这样的复杂度是 O(nk*nv)（键的数量乘以值的数量），或者使用上面提到的 tuple 方法。

假设你在插入时需要构建 tuple，而在获取值时也需要再次构建，这两者的复杂度都是 O(nk)，其中 nk 是键的数量。

如果你的嵌套层级比较深（也就是说，有很多值共享部分有序的键列表），那么使用嵌套的 dict 版本可能会更节省空间，获取值的复杂度仍然是 O(nk)，但可能会比 tuple 版本慢。

不过，插入的速度会比较慢，虽然我不能具体说明速度有多慢。你每插入一次，至少要构建一层 dict，并且要检查之前层级中是否存在 dict。

有很多关于递归 defaultdict 的方法，可以从编码的角度简化插入过程，但实际上并不会加快速度。

tuple 方法在插入时更简单也更快，但根据你的嵌套情况，可能会占用更多内存。

---

这是我在了解需求之前的原始回答

为什么不呢

{'key1' : 'value', 'key2' : 'value', .... 'keyn' : 'value' } 

这只是存储了每个位置对 value 的引用，而不是 value 本身，所以内存使用量会比嵌套的 dict 版本少，而且不会比 tuple 版本大，除非你有非常多的 value。

关于 Python 标准类型操作的时间复杂度，可以查看Python 维基。

基本上，插入或获取一个项目的平均复杂度是 O(1)。

获取一个值的所有键的平均复杂度是 O(n)：

[key for key in mydict if mydict[key] == value]

不过，如果添加键或查找所有键是常见操作，你的 dict 就需要翻转。你想要的是：

{'value': [key1, key2, ... keyn]}

这样你可以通过 mydict[value].append(newkey) 轻松添加键，通过 mydict[value] 获取所有键，这两者的平均复杂度都是 O(1)。

Answer 3

不深入细节（这些细节通常和具体实现有关，而且可能会被下一个聪明人修改字典的实现而改变）：

• 关于内存开销：每个对象都有一些额外的开销（比如引用计数和类型；一个空对象占8字节，一个空元组占28字节），但哈希表需要存储哈希值、键和值，通常会使用比当前需要的更多的桶来避免碰撞。另一方面，元组是不能调整大小的，也不会发生碰撞，也就是说，一个N元组可以简单地分配N个指针指向包含的对象，这样就完成了。这就导致了内存消耗上明显的差异。
• 关于查找和插入的复杂度（这两者在这方面是一样的）：无论是字符串还是元组，在CPython的字典实现中，碰撞的可能性相对较小，而且解决碰撞的效率很高。更多的键（因为你通过将键组合成元组来扁平化键空间）似乎会增加碰撞的可能性，但更多的键也会导致更多的桶（据我所知，当前的实现试图保持负载因子在2/3之间），这反过来又使得碰撞的可能性降低。此外，获取一个值不需要更多的哈希计算（其实只是多了一次函数调用和一些C级的异或运算来计算元组的哈希，但这几乎可以忽略不计）。

你看，性能上应该没有明显的差别，虽然内存上会有一些不同。不过，我觉得后者的差别不会太显著。一个包含一个元素的字典占140字节，一个包含十个元素的元组也占140字节（根据Python 3.2的sys.getsizeof）。所以即使是（已经不太现实，我的直觉告诉我）十层嵌套，你的差别也不过是稍微超过1KB - 如果嵌套的字典有多个项目，可能会更少（这取决于具体的负载因子）。对于一个在内存中有数百个这样的数据结构的数据处理应用来说，这个差别太大了，但大多数对象并不是那么频繁地创建。

你应该简单地问问自己，哪种模型更适合你的问题。考虑一下，使用键的元组要求你一次性拥有所有键，而使用嵌套字典则允许你逐步获取这些键。