生成集合的所有组合时内存不足

Question

我需要从55个数字中生成所有可能的6个数字组合。我估计这些组合一共有28,989,675种索引。我想我可能内存不够，因为我可以生成4个数字的组合，但生成更多的就不行了。我该如何解决这个问题呢？

我在使用一些我从这里的教程中借来的代码进行修改：https://www.youtube.com/watch?v=VyXDQxuIwPU

import itertools

text_file = open("comb3.txt", "w")

harmonics = [28, 33, 36, 38, 40, 43, 45, 47, 48, 50, 52, 55, 55.86, 57, 59, 60, 60.86, 61.69, 62, 63.86, 64, 65.86, 66, 66.69, 67, 69, 69.69, 70.86, 71, 71.69, 72, 74, 75.86, 76, 76.69, 77.86, 79, 81, 81.69, 82.86, 83.69, 84, 84.86, 86, 88, 88.69, 89.86, 90.69, 91, 93, 95, 95.69, 96.86, 98, 100]

combos = itertools.combinations(harmonics, 4)

usable_combos = []
for e in combos:
    usable_combos.append(e)

print usable_combos

s = str(usable_combos)

text_file.write(s)
text_file.close()

谢谢！

Answer 1

你遇到内存不足的一个原因是因为（你说得对）：55 选 6 = 28,989,675

现在，想想这到底占用多少内存。我们可以做个简单的估算，来看看这会需要多少内存：

因为你的列表使用了浮点数和整数，我们可以推算出内存消耗的上限是：

sys.getsizeof(float())

在64位机器上是24字节，而在32位机器上是16字节

而且，元组的内存占用是：56 + 8 * len(t) 字节（64位）

因此，你的计算所需的内存上限将是：

1. 28,989,675 * 6 * 24 + 28,989,675 * (56 + 8 * 6) 字节 ~ 6,856.39 MiB（64位）
2. 28,989,675 * 6 * 16 + 28,989,675 * (56 + 8 * 6) 字节 ~ 5,529.34 MiB（32位）

回想一下，Python的列表是连续存储的（为了实现O(1)的查找时间），这很可能是导致程序崩溃的原因，因为你还得考虑操作系统和其他程序在内存中占用的空间。

把这个和你提到的另一个例子比较一下：55 选 4 = 341,055 => ~ 59.85 MiB（64位） 或 ~49.44 MiB（32位） 的连续内存。这个内存量是非常合理的，所以运行起来没有问题。

编辑

原始链接（已失效）：http://deeplearning.net/software/theano/tutorial/python-memory-management.html

Answer 2

像 itertools.combinations 这样的迭代器一次只生成一部分数据，这样比较省内存。但是如果你把所有的值放到一个列表里，就需要一次性占用很多内存（顺便说一下，usable_combos = list(combos) 这个写法会替代你的 for 循环，不过你不一定要这么做）。

因为你是要把这些组合写入文件，所以可以在从迭代器获取每个组合时就直接写入文件，而不是先创建一个列表。现在，你需要它的格式像 Python 列表的 repr 吗？如果不需要，那这样做会更合理：

for combo in combos:
    text_file.write(str(combo) + "\n")

注意：由于性能测试的原因，改用了 "{}\n".format(combo)。

如果你想要像列表的 repr 那样的格式，你就需要自己加上 [ 和 ]，并用逗号代替换行符。

-更多-

根据评论中的更新，如果你在寻找特定的组合，最好是在写入文件之前就找出来，因为否则你得从文件中重新加载它们，再看一遍。如果你只会根据某些标准选择一小部分组合，提前选好会减少后面的工作量。

一般来说，你也可以考虑使用 Cython 来提高速度，而不需要学习真正的 C 语言。如果你真的想要强行处理一些超出你电脑内存限制的东西，合适大小的 EC2 实例大约每小时 20 美分。