is there any difference regarding the saving memory between a normal dictionary and a trie dictionar-CodePudding

is there any difference regarding saving memory space between a trie and a normal dictionary ? if yes, is there any way to count and measure their difference ? like how many bites or bytes is their difference.

here is an example of these two types of dictionaries :

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'}}

CodePudding user response：

Have you tried the sys.getsizeof() to get size of an object?

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))

The result is 232 for both print output.

sys.getsizeof() :

Return the size of an object in bytes. The object can be any type of object. All built-in objects will return correct results, but this does not have to hold true for third-party extensions as it is implementation specific.

Only the memory consumption directly attributed to the object is accounted for, not the memory consumption of objects it refers to.

If given, default will be returned if the object does not provide means to retrieve the size. Otherwise a TypeError will be raised.

getsizeof() calls the object’s sizeof method and adds an additional garbage collector overhead if the object is managed by the garbage collector.

CodePudding user response：

This is my attempt at a better evaluation of the total size of an object (dict and str only):

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