0

我基本上是在寻找可能对此有意见的其他人的一些反馈。以下内容不完全是我正在处理的内容，但示例代码确实重现了该问题。

我有一个幂集生成器，如果我发送的基本列表传入，它会返回所有排列。我需要对生成的集合进行排序（在我的真实情况下，返回的集合是具有我想要排序的值的元组，下面的示例演示了没有它的问题）

问题是当我在电源组生成器上使用 sorted() 时，它会增加内存使用量。我意识到 2^50 是一个非常大的数字，但是没有排序的内存使用量是相当平坦的，所以我想知道是否有更好的方法可以在一两分钟内对大量集合进行排序而不会耗尽内存。这是在带有 Python 2.6.5 的 Ubuntu 上运行的。（在这种情况下也需要）

def gen_powerset(seq):
    if len(seq) <= 1:
        yield seq
        yield []
    else:
        for i in gen_powerset(seq[1:]):
            yield [seq[0]]+i
            yield i

def main():
    initialSet = range(50)
    powerset = sorted(gen_powerset(initialSet))
    for i in powerset:
        print i

if __name__ == "__main__":
    main()

免责声明：如果您尝试运行此示例，请注意您的内存使用情况。如果样本接近 90%，请按 Ctrl-C，因为您的操作系统将开始将内存交换到磁盘。如果样本仍在运行，您的磁盘负载将飙升并真正减慢速度，从而很难首先杀死样本。

4

3 回答 3

4

如果没有sorted，您永远不需要一次存储超过 1 或 2 个值——它们会根据需要进行计算，因为您使用的是生成器 ( yield)。不幸的是，在不了解整个列表的情况下，没有好的方法可以对列表进行排序（除非您查看了所有项目以确保您拥有的项目是最小的，否则您无法从排序中产生一个值）。

当然，如果你有 2 个排序的子列表，你可以懒惰地合并它们，这样你就可以构建一个排序，它不会基于合并排序将所有内容一次存储在内存中，但在一般情况下它会非常低效。

于 2013-04-16T19:50:20.393 回答
2

内存使用率较高的原因sorted是它必须一次将所有项目加载到内存中。由于您编写了一个生成器，它一次只产生一个元素，并且您使用它的方式一次只使用一个值，因此 Python 不需要同时保留所有项目。但是如果没有所有这些，您就无法对它们进行排序。

只要您进行排序，您就无法解决这个问题，因为排序必须使所有元素都可用。

解决此问题的唯一方法是重写您的 powerset 生成器以按您想要的顺序生成项目。这可能会也可能不会，具体取决于您想要的订单。

于 2013-04-16T19:50:31.640 回答
2

您使用的生成器在消耗之前一次只创建一个值，这非常节省内存。该sorted函数需要将其转换为列表，以便它一次全部驻留在内存中。没有办法解决它。

于 2013-04-16T19:50:56.787 回答