密钥的嵌套字典或元组？

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

没有深入细节(无论如何都是高度依赖于实现的,并且可能会被下一个天才无效并调整字典实现):

• 对于内存开销:每个对象都有一些开销(例如refcount和type;空对象是8个字节,空元组是28个字节),但是哈希表需要存储哈希,键和值,并且通常使用比当前需要更多的桶.避免碰撞.另一方面,元组不能调整大小并且没有碰撞,即N元组可以简单地将N个指针分配给包含的对象并完成.这导致内存消耗的显着差异.
• 对于查找和插入复杂性(两者在这方面是相同的):无论是字符串还是元组,在CPython的dict实现中冲突都是不太可能的,并且非常有效地解决.更多的键(因为你通过组合元组中的键来平整键空间)似乎增加了碰撞的可能性,更多的键也导致更多的桶(当前实现的AFAIK试图将负载因子保持在2/3之间),反过来使碰撞不太可能发生.此外,你不需要更多的散列(好吧,还有一个函数调用和一些C级xor-for for tuple hash,但这是可行的)来得到一个值.

你看,虽然存在一些内存差异,但性能上应该没有任何明显的差异.我想,后者不会引人注目.单元素字典是140字节,十元素元组也是140字节(根据Python 3.2 sys.getsizeof).因此即使使用(已经不切实际的,我的直觉)十级嵌套,你的差异也会略微超过一KB - 如果嵌套的dicts有多个项目(取决于确切的加载因子),可能会更少.对于拥有数百个此类数据结构内存的数据运算应用程序来说,这太过分了,但大多数对象并不经常创建.

您应该问问自己哪种模型更适合您的问题.考虑到第二种方式要求您一次获得值的所有键,而第二种方法允许以递增方式获取值.