python：生成整数分区 [英] python: Generating integer partitions

问题描述

我需要生成给定整数的所有分区。 br>
我发现Jerome Kelleher提出的这种算法是最有效的算法：

I need to generate all the partitions of a given integer.
I found this algorithm by Jerome Kelleher for which it is stated to be the most efficient one:

def accelAsc(n):
    a = [0 for i in range(n + 1)]
    k = 1
    a[0] = 0
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2*x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield a[:k + 2]
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield a[:k + 1]

引用： http：//homepages.e d.ac.uk/jkellehe/partitions.php

顺便说一句，效率不高。对于像 40 这样的输入，它会冻结几乎整个系统几秒钟，然后给出输出。

By the way, it is not quite efficient. For an input like 40 it freezes nearly my whole system for few seconds before giving its output.

如果这是一种递归算法，我会尝试使用缓存功能或提高其效率的东西来修饰它，但那样的话我不知道该怎么做。

If it was a recursive algorithm I would try to decorate it with a caching function or something to improve its efficiency, but being like that I can't figure out what to do.

您对如何加快此算法有一些建议吗？还是可以建议我另外一个，或者以其他方式从头开始制作另一个？

Do you have some suggestions about how to speed up this algorithm? Or can you suggest me another one, or a different approach to make another one from scratch?

推荐答案

如果要使用对于相同的输入重复使用此函数，仍然值得缓存返回值（如果要在单独的运行中使用它，则可以将结果存储在文件中。）

If you are going to use this function repeatedly for the same inputs, it could still be worth caching the return values (if you are going to use it across separate runs, you could store the results in a file).

如果找不到更快的算法，则应该可以通过将代码移到C扩展中来加快一个或两个数量级的速度（使用 cython ），或者使用 PyPy ） >而不是CPython（PyPy有其缺点-它尚不支持Python 3或某些常用的库，例如numpy和scipy）。

If you can't find a significantly faster algorithm, then it should be possible to speed this up by an order of magnitude or two by moving the code into a C extension (this is probably easiest using cython), or alternatively by using PyPy instead of CPython (PyPy has its downsides - it does not yet support Python 3, or some commonly-used libraries like numpy and scipy).

，因为python是动态类型的，所以解释器可能会花费大部分时间检查变量的类型-就所有解释者所知，其中一个操作可以将 x 转换为字符串，在这种情况下，诸如 x + y 突然会有不同的含义。 Cython通过允许您将变量静态声明为整数来解决此问题，而PyPy具有及时编译器，可最大程度地减少冗余类型检查。

The reason for this is, since python is dynamically typed, the interpreter is probably spending most of its time checking the types of the variables - for all the interpreter knows, one of the operations could turn x into a string, in which case expressions like x + y would suddenly have very different meanings. Cython gets around this problem by allowing you to statically declare the variables as integers, while PyPy has a just-in-time compiler which minimises redundant type checks.

这篇关于python：生成整数分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！