磁盘 space - Python 字典与列表

Question

我被要求创建一个倒排索引并以多种方式（压缩和不压缩）保存它的二进制文件。

长话短说，我注意到使用 dict 表示比转换为 list 需要更少的磁盘空间 space。

样本：

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)

如果您检查两个文件的大小，您会发现其中的差异。

所以，我愿意知道它们有何不同以及为何不同。任何额外的信息将不胜感激

Answer 1

dic_list 列表包含 个对象。您有一个元组的外部列表，每个元组都是一个键值对。每个值都是另一个列表。这些元组是您需要更多 space.

的原因

字典pickle 格式不必使用元组对象来存储键值对；预先知道字典由一系列对组成，因此您可以直接序列化每个此类对的键和值，而无需包装元组对象的开销。

您可以使用 pickletools module; 分析 pickle 数据；使用只有一个键值的更简单的字典，您已经可以看到区别：

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

如果您认为 EMPTY_DICT + SETITEM 等同于 EMPTY_LIST + APPEND，那么该流中唯一真正的区别在于添加了 TUPLE2 / MEMOIZE 一对操作码。正是这些操作码占用了额外的 space.

Answer 2

dict 可以原生处理键值对，而 list 必须使用单独的容器。

您的 dict 是 Dict[K, V] 的直接表示 - 对加上一些结构。由于该结构仅是运行时的，因此可以忽略存储。

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

您的 list 使用对的助手，导致 List[Tuple[K,V]] - 对加上包装器。由于需要包装器来重建对，因此不能忽略存储。

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

您也可以在 pickle dump 中检查它。 list 转储包含附加元组的标记。

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>

虽然周围的 dict 和 list 都存储为对序列，但对的存储方式不同。对于dict，只有key、value和stop平放。对于 list，每对需要一个额外的 tuple。

磁盘 space - Python 字典与列表

Disk space - Python dictionary vs list

python

dictionary

list

pickle

python-3.x