Cfrgtkky

I was asked to create an inverted index and save its binary in multiple ways (with and without compression).

Long story short, I noticed that using a dict representation takes much less disk space than transforming into a list.

Sample:

dic = {

    'w1': [1,2,3,4,5,6],

    'w2': [2,3,4,5,6],

    'w3': [3,4,5,6],

    'w4': [4,5,6]

}



dic_list = list(dic.items())



import pickle



with open('dic.pickle', 'wb') as handle:

    pickle.dump(dic, handle, protocol=pickle.HIGHEST_PROTOCOL)



with open('dic_list.pickle', 'wb') as handle:

    pickle.dump(dic_list, handle, protocol=pickle.HIGHEST_PROTOCOL)

If you check both files sizes, you will notice the difference.

So, I am willing to know how and why they are different. Any additional information would be much appreciated

The dic_list list consists of more objects. You have an outer list of tuples, each tuple a key-value pair. Each value is another list. Those tuples are the reason you need more space.

The dictionary pickle format doesn't have to use tuple objects to store key-value pairs; it is already known up front that a dictionary consists of a series of pairs, so you can serialise key and value per such pair directly without the overhead of a wrapping tuple object.

You can analyse pickle data with the pickletools module; using a simpler dictionary with just one key-value, you can see the difference already:

>>> import pickle, pickletools

>>> pickletools.dis(pickle.dumps({'foo': 42}, protocol=pickle.HIGHEST_PROTOCOL))

    0: x80 PROTO      4

    2: x95 FRAME      12

   11: }    EMPTY_DICT

   12: x94 MEMOIZE    (as 0)

   13: x8c SHORT_BINUNICODE 'foo'

   18: x94 MEMOIZE    (as 1)

   19: K    BININT1    42

   21: s    SETITEM

   22: .    STOP

highest protocol among opcodes = 4

>>> pickletools.dis(pickle.dumps(list({'foo': 42}.items()), protocol=pickle.HIGHEST_PROTOCOL))

    0: x80 PROTO      4

    2: x95 FRAME      14

   11: ]    EMPTY_LIST

   12: x94 MEMOIZE    (as 0)

   13: x8c SHORT_BINUNICODE 'foo'

   18: x94 MEMOIZE    (as 1)

   19: K    BININT1    42

   21: x86 TUPLE2

   22: x94 MEMOIZE    (as 2)

   23: a    APPEND

   24: .    STOP

If you consider EMPTY_DICT + SETITEM to be the equivalent of EMPTY_LIST + APPEND, then the only real difference in that stream in the addition of the TUPLE2 / MEMOIZE pair of opcodes. It's those opcodes that take the extra space.

A dict can natively handle key-value pairs, while a list must use a separate container.

Your dict is a straightforward representation of Dict[K, V] - pairs plus some structure. Since the structure is runtime only, it can be ignored for storage.

{'a': 1, 'b': 2}

Your list uses a helper for pairs, resulting in List[Tuple[K,V]] - pairs plus wrapper. Since the wrapper is needed to reconstruct the pairs, it cannot be ignored for storage.

[('a', 1), ('b', 2)]

You can also inspect this in the pickle dump. The list dump contains markers for the additional tuples.

pickle.dumps({'a': 1, 'b': 2}, protocol=0)

(dp0  # <new dict>

  Va  # string a

 p1

  I1  # integer 1

 sVb  # <setitem key/value>, string b

 p2

  I2  # integer 2

 s.   # <setitem key/value>



pickle.dumps(list({'a': 1, 'b': 2}.items()), protocol=0)

(lp0    # <new list>

  (Va   # <marker>, string a

  p1

   I1   # integer 1

  tp2   # <make tuple>

 a(Vb   # <append>, <marker>, string b

  p3

   I2   # integer 2

  tp4   # <make tuple>

 a.     # <append>

While the surrounding dict and list are both stored as a sequence of pairs, the pairs are stored differently. For the dict, only key, value and stop are stored flatly. For the list, an additional tuple is needed for each pair.