普通字典和 trie 字典在节省内存方面有什么区别吗？

Question

trie 和普通字典在节省内存方面有什么区别 space 吗？如果是，有什么方法可以计算和衡量它们的差异吗？比如他们的区别是多少位或字节。

下面是这两种字典的示例：

trie_dict = {'f': {'o': {'o': {'t': {'value':'to walk with'},                                            
                               'l': {'value':'to teach'},
                               'd':{'value': 'to eat'}}}}}


normal_dict =  {'foot': {'value': 'to walk with'},
                'fool': {'value': 'to teach'},
                'food': {'value': 'to eat'}}

Answer 1

您是否尝试过 sys.getsizeof() 获取对象的大小？

import sys

trie_dict = {'f': {'o': {'o': {'t': {'value':'to walk with'},                                            
                               'l': {'value':'to teach'},
                               'd':{'value': 'to eat'}}}}}


normal_dict =  {'foot': {'value': 'to walk with'},
                'fool': {'value': 'to teach'},
                'food': {'value': 'to eat'}}

print(sys.getsizeof(trie_dict))
print(sys.getsizeof(normal_dict))

两个打印输出的结果都是232。

sys.getsizeof() :

Return 对象的大小（以字节为单位）。该对象可以是任何类型的对象。所有 built-in 对象都将 return 正确结果，但这不一定适用于 third-party 扩展，因为它是特定于实现的。

仅考虑直接归因于对象的内存消耗，而不考虑其引用的对象的内存消耗。

如果给定，如果对象不提供检索大小的方法，则默认为 returned。否则将引发 TypeError。

getsizeof() 调用对象的 sizeof 方法，如果对象由垃圾收集器管理，则会增加额外的垃圾收集器开销。

Answer 2

这是我尝试更好地评估对象的总大小（仅限 dict 和 str）：

def rec_size_of(obj):
    current = 0
    if isinstance(obj, dict):
        current += getsizeof(obj)
        for k,v in obj.items():
            current += getsizeof(k)
            current += rec_size_of(v)
    elif isinstance(obj, str):
        current += getsizeof(obj)
    return current

rec_size_of(trie_dict)       
2315

rec_size_of(normal_dict)         
1454

普通字典和 trie 字典在节省内存方面有什么区别吗？

is there any difference regarding the saving memory between a normal dictionary and a trie dictionary?

python

memory

dictionary

structure

trie