Python：减少字典的内存使用

Question

我正在尝试将一些文件加载到内存中。这些文件具有以下三种格式之一：

• string TAB int
• string TAB float
• int TAB float

实际上，它们是ngram静态文件，如果这有助于解决问题。例如：

i_love TAB 10
love_you TAB 12

目前，我正在进行的伪代码是

loadData(file):
     data = {}
     for line in file:
        first, second = line.split('\t')
        data[first] = int(second) #or float(second)

     return data

令我惊讶的是，尽管磁盘中文件的总大小约为21 mb，但加载到内存中的进程占用了120-180 mb的内存！（整个Python应用程序没有将任何其他数据加载到内存中）。

这些文件不到10个，它们中大部分会保持在50-80k行左右，除了一个目前有数百万行的文件。

因此，我想要请教一种可以减少内存消耗的技术/数据结构：

• 有关压缩技术的任何建议？
• 如果我仍然使用字典，有没有办法减少内存消耗？是否可以像Java中的字典一样设置“负载因子”？
• 如果您有其他数据结构，我也愿意牺牲一些速度来减少内存。然而，这是一个时间敏感的应用程序，一旦用户输入他们的查询，我认为返回结果需要不超过几秒钟。关于这一点，我仍然很惊讶谷歌如何如此快速地进行谷歌翻译：他们必须使用了许多技术+大量服务器的计算能力吧？

非常感谢。期待您的建议。

- Paul Hoang

---

数据中是否有任何重复的内容（键或值）？如果有，您可以使用对相同对象的引用来节省空间。 - Gabe

那120-180MB的内存中有多少是解释器本身的？ - Platinum Azure

@PlatinumAzure 有什么建议可以帮我找到答案吗？谢谢。 - Paul Hoang

@JoelCornett：OP的伪代码意味着每个文件将被加载到单独的字典中，这将允许它们共享键。 - Gabe

你可以使用Guppy/Heapy来查找Python模块的内存分配情况。(http://guppy-pe.sourceforge.net/) - Adam Lewis

Answer 1

我无法提供完整的策略来改善内存占用，但我认为分析哪些内容占用了大量内存可能会有所帮助。

如果你查看Python实现的字典（这是相对直接实现哈希表的实现）以及内置字符串和整数数据类型的实现，例如这里（特别是object.h、intobject.h、stringobject.h和dictobject.h，以及../Objects中相应的*.c文件），你就可以比较准确地计算出预期的空间需求：

1. 整数是固定大小的对象，即它包含一个引用计数、一个类型指针和实际的整数，在32位系统上通常至少需要12个字节，在64位系统上需要24个字节，不考虑可能因对齐而丢失的额外空间。

2. 字符串对象是可变大小的，这意味着它包含

• 引用计数

• 类型指针

• 大小信息

• 用于惰性计算哈希码的空间

• 状态信息（例如用于interned字符串）

• 指向动态内容的指针

  总共在32位系统上至少需要24个字节或64位系统上需要60个字节，不包括字符串本身的空间。

1. 字典本身由许多桶组成，每个桶都包含

• 当前存储对象的哈希码（由于使用了冲突解决策略，这可能无法预测桶的位置）

• 键对象的指针

一个指向值对象的指针。

在32位系统上至少需要12字节，在64位系统上至少需要24字节。

字典开始时有8个空桶(bucket)，当其容量达到时，通过翻倍扩容方式来调整大小。

我进行了一项测试，使用了一个由46,461个唯一字符串（337,670字节串联字符串大小）组成的列表，每个字符串都与一个整数相关联。这类似于您的设置，在32位机器上进行。根据上面的计算，我预计该程序的最小内存占用量为：

• 46,461 * (24+12) 字节 = 1.6 MB（字符串/整数组合）
• 337,670 字节 = 0.3 MB（字符串内容）
• 65,536 * 12 字节 = 1.6 MB（哈希桶）（扩容13次后）

总共2.65 MB。（对于64位系统，相应的计算结果为5.5 MB。）

运行Python解释器idle时，根据ps工具显示其内存占用为4.6 MB。因此，创建完字典后的总期望内存消耗大约为4.6 + 2.65 = 7.25 MB。 在我的测试中，真正的内存占用（根据ps工具）是7.6 MB。 我想额外的约0.35MB是由Python的内存分配策略（如内存区域等）产生的开销。

当然，许多人现在会指出，我使用ps来测量内存占用是不准确的，并且我对32位和64位系统上指针类型和整数大小的假设可能在许多特定系统上是错误的。可以理解这种说法。

但是，我认为主要结论是以下几点：

• Python的字典实现消耗了相当少的内存。
• 但是由于引用计数、预计算哈希码等，许多整数和特别是字符串对象所占用的空间比起一开始想象的要大得多。
• 只要使用Python并且想要将字符串和整数表示为单独的对象，几乎没有办法避免内存开销，至少我不知道如何做到这一点。
• 可以值得寻找（或自己实现）一个Python-C扩展，该扩展以C指针（而不是Python对象）为键和值实现哈希。我不知道它是否存在，但我相信它可以实现，并且可以将内存占用量减少一半以上。

- jogojapan

---

@Paul Hoang，我应该把它解释得更清楚：从8个条目开始，调整大小（倍增）13次，得到8 *（2 ^ 13）= 65,536。仅调整大小12次，可得32768，因此我假设对于46461个条目，它至少会最小限度地调整大小13次。 - jogojapan

@Gabe：但是它们只被存储在256个内存地址中；之后，它们就像任何其他对象一样被分配。 - javawizard

好的分析。我正在运行64位，并发现sys.getsizeof('') == 37，而不是60字节。你从哪里得出的60字节？ - RussellStewart

@user2237635 对sys.getsizeof()进行测试是个好主意——我当时没这么做。我写这篇文章的时候可能用的是Python 2.5，那时候还没有getsizeof函数。不管怎样，我的数据是基于阅读源代码并对像int、short等基本类型的大小进行假设得出的，这当然取决于平台。此外，Python类型的实现随着时间的推移也发生了变化。在我的当前64位系统上使用getsizeof进行测试显示，在Python 2.7.5和Python 3.3之间，""和b""的大小差异为5字节。 - jogojapan

因此，对于当前的Python版本，当然取决于平台和系统，您将获得不同的数字。但是60似乎确实很大 - 我可能错误地计算了一些数据成员的大小。 - jogojapan

Answer 2

1) SQLite内存数据库听起来是个不错的解决方案，一旦加载数据，它将让您更轻松地查询数据，这是一种享受。

sqlite3.connect(':memory:')

2) 您可能需要一个命名元组 - 我相信它们比字典更轻，您可以使用点符号访问属性（我个人审美偏好）。

http://docs.python.org/dev/library/collections

3) 您可能需要查看Redis: https://github.com/andymccurdy/redis-py

它非常快速，并且会让您轻松持久化数据，这意味着您不必每次使用时都加载整个集合。

4) 字典树听起来是个好主意，但会增加一些理论上的复杂性。您可以使用Redis实现和存储它，这将进一步提高速度。

但总体而言，命名元组可能是最好的选择。

- Moshe Bildner

Answer 3

磁盘上只有字符串，当从磁盘加载到Python解释器时，解释器必须为每个字符串和每个字典创建整个结构，除了字符串本身。

无法减少字典使用的内存，但是还有其他方法来解决问题。如果您愿意为节省内存而牺牲一些速度，则应考虑从SQLite文件中存储和查询字符串，而不是将所有内容加载到内存中的字典中。

- Pedro Werneck

---

同意。如果它太大而无法放入内存中，请使用数据库。 - Francis Avila

@Pedro Werneck感谢您推荐SQLite。我已经尝试了PostGres，但速度比我期望的要慢得多。您知道使用SQLite是否比使用PostGres或MySQL更快吗？ - Paul Hoang

只有在你能够将整个数据库保留在内存中时，这才能起作用。如果你告诉SQLite使用内存而不是文件，你可能能够获得所需的速度。但并不清楚你是否会获得更好的内存使用情况。 - Gabe

SQLite比PostgreSQL和MySQL快几倍。 - Pedro Werneck

Answer 4

如果您想在Python中紧凑地存储数值数据，那么最好的解决方案可能是Numpy。Numpy（{{link1：http://numpy.org}}）使用本地C结构分配数据结构。它的大多数数据结构假定您正在存储单个数据类型，因此并非适用于所有情况（您可能需要存储null等），但它可能非常非常快，并且尽可能紧凑。许多科学都在使用它（另请参见：SciPy）。

当然，还有另一个选择：zlib，如果您有：

- 充足的CPU周期和 - 大量无法放入内存的数据

您可以将“页面”数据（任何大小）声明为数组，读取数据，将其存储在数组中，对其进行压缩，然后再读取一些数据，直到您拥有所需的所有数据。然后，遍历页面，解压缩，转换回数组，并根据需要执行操作。例如：

def arrayToBlob(self, inArray):
    a = array.array('f', inArray)
    return a.tostring()

def blobToArray(self, blob, suppressWarning=False):
    try:
        out = array.array('f', [])
        out.fromstring(blob)
    except Exception, e:
        if not suppressWarning:
            msg = "Exception: blob2array, err: %s, in: %s" % (e, blob)
            self.log.warning(msg)
            raise Exception, msg
    return out

一旦您将数据作为 blob，您可以将此 blob 传递给 zlib 并压缩数据。如果有很多重复的值，这个 blob 可以被大大压缩。

当然，它比保持所有未压缩的速度慢，但如果您无法将其全部放入内存中，则选择受限。

即使使用压缩，它也可能无法全部放入内存中，此时您可能需要将压缩页面写出为字符串或 pickles 等。

祝你好运！

- Kevin J. Rice

Answer 5

听起来像是 Trie（http://en.m.wikipedia.org/wiki/Trie）数据结构更适合您对内存效率的需求。

更新：Python 字典的内存效率已经成为一个问题，虽然由于第三方库的可用性而被拒绝加入标准库。参见：http://bugs.python.org/issue9520。

- Garrett

---

好主意！搜索速度也更快。那使用DAWG怎么样？我认为它会占用更少的内存。 - Ray

Answer 6

您可以使用blist.sorteddict替换字典，以实现对数级别的访问速度而无需增加内存开销。这非常方便，因为它的行为与字典完全相同，即它实现了所有字典方法，所以您只需要更改初始类型即可。

- ealfonso