我对这种压缩算法很感兴趣(查看链接)
https://github.com/bright-tools/varints
问题尤其在于 Python 中字节数组对象的内存开销使得压缩毫无用处。 有没有一种解决方案只考虑编码的大小而不考虑数据结构的大小? 例如:
>>> import sys
>>> list = []
>>> sys.getsizeof(list)
64
但我会得到类似“0”的东西,而不是 64
如何避免内存开销? 请来一些吗?
最佳答案
如果您尝试创建小型数据结构,Python 不是您想要使用的语言。正如您链接的项目的自述文件所述,如果您可以将大量数据打包到单个字节数组中,则可以使用字节数组(而不是列表)来减少存储开销。但即使是字节数组(如字符串)也是有代价的:64 位 CPython 安装(即通过 x86 Linux 安装获得的标准 Python)每个字节数组至少使用 33 字节的开销。 (我说“至少”是因为 Python 无法测量内存分配开销。)如果需要的话,还有将字节流反序列化为原始对象的计算成本。
由于链接页面生成较小的对象,我得出结论,它的测试一定是在 32 位 Python 安装上完成的,可能是在 Windows 上。因此,这是减少存储使用量的一种方法。
如果你有Python3.3或更高版本(如果没有,只需安装它:-)),那么你可以使用array
模块,这可能比byte更方便数组,部分原因是您可以创建一个其元素大小为您需要的数组。请参阅the Python manual了解详情。如果您使用 b
或 B
类型修饰符构建 array.array
,则每个值将仅使用一个字节。如果使用 h
或 H
,则可以存储 16 位整数(有符号或无符号),每个整数占两个字节。 array.array
的开销是 64 个字节,就像列表一样,但实际元素要紧凑得多。
就我个人而言,我不会为这样的东西烦恼,但我认为它有它的用处。事实上,引用 README 页面低估了 Python 整数列表的存储消耗,因为它没有考虑整数本身的大小,而整数本身的大小是相当大的。
sys.getsizeof
显示的列表大小只是列表本身的大小。它不包括列表中的对象,仅包括对该对象的引用(在标准 Linux Python 安装上每个对象有 8 个字节)。它还包括列表的对象描述使用的内存,在相同的标准 Python 安装中为 64 字节。 (这是测试中显示的 64 字节。)
最后,它可能在末尾包含一些额外的空间,以便允许将项目追加到列表中,而无需重新分配和复制列表。此类额外对象的数量取决于很多因素,包括构造列表的精确方式,但似乎您可以通过使用切片复制列表来将这种特定的开销减少到零:a[:]
.
在 Python 中,整数是成熟的对象,并且它们使用的空间量令人惊讶。或者,当您考虑到 Python 整数是 bignum,因此它们没有人为的大小限制时,也许这并不奇怪。根据getsizeof
,绝对值小于 230 的整数占用 28 个字节,每增加 30 位(或部分)就多花费 4 个字节。 (事实上,您可以利用左移和右移操作相当快的事实,将一个由小整数组成的大向量按位打包到单个 bignum 中,从而从每个列表中减少更多字节。但是array.array
几乎肯定更容易。)
一些getsizeof
的实验,供引用:
>>> from sys import getsizeof
>>> # Strings occupy 48 bytes plus the length of the string plus one byte (presumably for a NUL)
>>> getsizeof("") # 48 + 0 + 1
49
>>> getsizeof("a") # 48 + 1 + 1
50
>>> getsizeof("abcdefghijklmnopqrstuvwxyz") # 48 + 26 + 1
75
>>> getsizeof("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ") # 48 + 52 + 1
101
>>> But that's not counted in the size of a list. All the lists are the same size:
>>> getsizeof([""])
72
>>> getsizeof(["a"])
72
>>> getsizeof(["abcdefghijklmnopqrstuvwxyz"])
72
>>> getsizeof(["abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"])
72
>>> # Same for a list containing a single number
>>> getsizeof([0])
72
>>> # Lists need 64 bytes plus 8 bytes per element (a pointer to the element):
>>> getsizeof([0,1])
80
>>> getsizeof([0,1,2])
88
>>> getsizeof([0,1,2,3])
96
>>> # When you append to a list, Python leaves some extra space for the next appends
>>> a = [0,1,2,3]
>>> getsizeof(a)
96
>>> # As above, 64 + 4 * 8 bytes. But when we add a single element,
>>> # we get enough room for four elements, so the next three appends
>>> # don't require more space:
>>> a.append(4)
>>> getsizeof(a)
128
>>> a.append(5)
>>> getsizeof(a)
128
>>> a.append(6)
>>> getsizeof(a)
128
>>> a.append(7)
>>> getsizeof(a)
128
>>> # When we append the 9th element, we get room for another four
>>> a.append(8)
>>> getsizeof(a)
192
您可以通过使用元组而不是列表来节省一些字节:元组与字节数组一样,是不可变的,但如果您可以忍受无法修改对象,则可以通过使用元组来节省 16 个字节列表:
>>> getsizeof( (1,2,3) )
72
>>> getsizeof( [1,2,3] )
88
关于Python和压缩算法性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53872699/