0

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'}}
csismylife
  • 71
  • 10

2 Answers2

1

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.

Baris Ozensel
  • 433
  • 1
  • 3
  • 11
  • 1
    `232` is the size of the outer dictionary (tbh on my PC i get `240`, but that's not important). But with `trie_dict` you are creating _seven_ `dict`s, with `normal_dict` just four – gimix Apr 16 '22 at 17:25
  • "Only the memory consumption directly attributed to the object is accounted for, not the memory consumption of objects it refers to" how can I know the "memory consumption of objects it refers to ?" and also if they both have the same size, what's the point of having a trie dict ? – csismylife Apr 17 '22 at 06:40
  • 1
    Is it possible to check the following https://stackoverflow.com/questions/449560/how-do-i-determine-the-size-of-an-object-in-python/59228005#59228005 ? In addition, if there is a performance issue, the 'pickle' library should also help. You can configure as 'import pickle' and 'print(len(pickle.dumps(trie_dict)))'. See more detail via https://docs.python.org/3/library/pickle.html . Thanks. – Baris Ozensel Apr 17 '22 at 08:17
1

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
gimix
  • 3,431
  • 2
  • 5
  • 21