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

Мне нужно создать все разделы данного целого числа.
Я нашел этот алгоритм Джерома Келлехера, для которого он считается самым эффективным:

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.ed.ac.uk/jkellehe/partitions.php

Кстати, это не совсем эффективно. Для входа типа 40 Он замораживает почти всю мою систему на несколько секунд, а затем выдает результат.

Если бы это был рекурсивный алгоритм, я бы попытался украсить его функцией кеширования или чем-то еще, чтобы повысить его эффективность, но я так и не могу понять, что делать.

Есть ли у вас предложения о том, как ускорить этот алгоритм? Или вы можете предложить мне другой или другой подход, чтобы сделать еще один с нуля?

Источник

4 ответа

Решение

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

Если вы не можете найти значительно более быстрый алгоритм, то должна быть возможность ускорить его на порядок или два, переместив код в расширение 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.

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

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

Источник

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

PyPy 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
Источник
Другие вопросы по тегам