python: создание целочисленных разделов

Если вы собираетесь использовать эту функцию повторно для одних и тех же входных данных, возможно, стоит кэшировать возвращаемые значения (если вы собираетесь использовать ее для отдельных запусков, вы можете сохранить результаты в файле).

Если вы не можете найти значительно более быстрый алгоритм, то его можно ускорить на порядок или два, переместив код в расширение C (это, вероятно, проще всего использовать с помощью cython) или с помощью PyPy вместо CPython (У PyPy есть свои недостатки — он еще не поддерживает Python 3 или некоторые часто используемые библиотеки, такие как numpy и scipy).

Причина этого в том, что, поскольку python динамически типизирован, интерпретатор, вероятно, тратит большую часть своего времени на проверку типов переменных - насколько известно интерпретатору, одна из операций может превратить x в строку, и в этом случае выражения вроде x + y внезапно будет иметь совсем другое значение. Cython решает эту проблему, позволяя вам статически объявлять переменные как целые числа, в то время как PyPy имеет просто -своевременный компилятор, который сводит к минимуму избыточные проверки типов.

Для генерирования композиций напрямую вы можете использовать следующий алгоритм:

def ruleGen(n, m, sigma):
    """
    Generates all interpart restricted compositions of n with first part
    >= m using restriction function sigma. See Kelleher 2006, 'Encoding
    partitions as ascending compositions' chapters 3 and 4 for details.
    """
    a = [0 for i in range(n + 1)]
    k = 1
    a[0] = m - 1
    a[1] = n - m + 1
    while k != 0:
        x = a[k - 1] + 1
        y = a[k] - 1
        k -= 1
        while sigma(x) <= y:
            a[k] = x
            x = sigma(x)
            y -= x
            k += 1
        a[k] = x + y
        yield a[:k + 1]

Этот алгоритм является очень общим и может генерировать разделы и композиции многих различных типов. Для вашего случая используйте

ruleGen(n, 1, lambda x: 1)

для создания всех неограниченных композиций. Третий аргумент известен как функция ограничения и описывает требуемый тип композиции/раздела. Этот метод эффективен, так как количество усилий, необходимых для создания каждой композиции, является постоянным при усреднении всех созданных композиций. Если вы хотите сделать это немного быстрее в python, то легко заменить функцию sigma на 1.

Здесь также стоит отметить, что для любого алгоритма с постоянным амортизированным временем то, что вы фактически делаете с сгенерированными объектами, почти наверняка будет преобладать в стоимости их создания. Например, если вы храните все разделы в списке, то время, затраченное на управление памятью для этого большого списка, будет намного больше, чем время, затраченное на создание разделов.

Скажем, по какой-то причине вы хотите взять произведение каждого раздела. Если подойти к этому наивно, то задействованная обработка линейна по количеству частей, тогда как стоимость генерации постоянна. Довольно сложно представить себе применение комбинаторного алгоритма генерации, в котором обработка не доминирует над стоимостью генерации. Таким образом, на практике не будет заметной разницы между использованием более простого и общего правила ruleGen с sigma(x) = x и специализированным accelAsc.

Тестирование с n = 75 я получаю:

ПиПи 1.8:

w:\>c:\pypy-1.8\pypy.exe pstst.py
1.04800009727 secs.

CPython 2.6:

w:\>python pstst.py
5.86199998856 secs.

Cython + mingw + gcc 4.6.2:

w:\pstst> python -c "import pstst;pstst.run()"
4.06399989128

Я не увидел разницы с Psyco(?)

Функция запуска:

def run():
    import time
    start = time.time()
    for p in accelAsc(75):
        pass
    print time.time() - start, 'secs.'

Если я изменю определение accelAsc для Cython, чтобы начать с:

def accelAsc(int n):
    cdef int x, y, k
    # no more changes..

Я сократил время Cython до 2,27 секунды.

Я бы сказал, что ваша проблема с производительностью где-то в другом месте.

Я не сравнивал его с другими подходами, но мне он кажется эффективным:

import time

start = time.time()
partitions = list(accelAsc(40))
print('time: {:.5f} sec'.format(time.time() - start))
print('length:', len(partitions))

Дал:

time: 0.03636 sec
length: 37338