Перестановки python itertools для степеней 2 слишком медленные

У меня очень странная проблема, и я не могу найти способ ее исправить.

Следующий код находит простое разложение n, помещает простые множители в список, затем находит все возможные вариации суммы простых множителей и распечатывает уникальные значения этого списка.

Пример: простые множители для 44 равны 2 * 2 * 11, поэтому для 44 будет распечатано

2,2+2,11,2+11,2+2+11 = 2,4,11,13,15:

Вот мой код:

import math
import sys
import itertools
from itertools import permutations

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac


def primecombo(n):
    b = []
    for i in range(1, len(primes(n))+1):
        for subset in permutations(primes(n), i):
            b.append(sum((subset)))
    a = list(set(b))
    a.sort()
    return a

сам код, кажется, работает нормально и эффективно по большей части, но по какой-то очень странной причине он становится до смешного медленным, когда вы имеете дело с любым числом, единственный простой фактор которого равен 2.

если вы попробуете напечатать primecombo (444444) или print primecombo (23452823), он напечатает результаты почти мгновенно, но если вы попробуете 2048 или 4096, он станет очень медленным.

Может ли кто-нибудь понять, почему это так, и что я могу сделать, чтобы это исправить?


python performance permutation itertools
person Anonymous    schedule 12.04.2018    source источник
comment
23452823 имеет только 7 факторов, а 2048 - 11. Поскольку получение перестановок экспоненциально, оно просто невыносимо длиннее. Кроме того, вы пересчитываете простые числа на каждой итерации, вместо этого сохраняете их в переменной.   -  person Olivier Melançon    schedule 12.04.2018
comment
Кроме того, вам не требуются перестановки простых чисел, только комбинации. Это должно значительно улучшить ваше время.   -  person Olivier Melançon    schedule 12.04.2018
comment
Спасибо, Оливье, это значительно ускорило процесс.   -  person Anonymous    schedule 12.04.2018
comment
Это можно ускорить еще больше, когда фактор присутствует несколько раз, используя счетчик факторов и повторяя его комбинации, я напишу полный ответ позже, если никто этого не сделал.   -  person Olivier Melançon    schedule 12.04.2018

Ответы (1)


arrow_upward
7
arrow_downward

Короткий ответ

Использование itertools.permutations заставляет ваш алгоритм суммировать избыточные разделы простых множителей. Использование itertools.combinations должно быть значительным улучшением, но мы все еще можем добиться большего.

Длинный ответ

Нахождение всех перестановок с помощью itertools.permutations заставляет вашу функцию primecombo выполняться за факториальное время с учетом количества факторов, худшее, чем экспоненциальное.

Давайте посмотрим на временную сложность с учетом количества факторов k. Доминирующий шаг - повторение permutations(primes(n), len(primes(n)). Существует k! перестановок, и вы суммируете каждую из них. Таким образом, временная сложность вашего алгоритма

O(k * k!)

Вот почему 2048, у которого есть 11 факторов, невыносимо длиннее, чем 23452823, у которого есть 7 факторов, для обработки.

Альтернатива

К счастью, посещение каждой перестановки не требуется. Например, если у вас есть множители 2, 3 и 4, вы будете суммировать каждую перестановку 2, 3 и 4, которая является избыточной. Одним из быстрых улучшений было бы суммирование комбинаций, но даже в этом случае мы иногда суммируем одно и то же разделение дважды, когда есть факторы, которые появляются более одного раза.

Следующее решение решает эту проблему, отслеживая простые множители с Counter вместо list. Позже это позволит нам использовать itertools.product.

Этот алгоритм может находить нужные суммы для 4096 за миллисекунды, см. Анализ временной сложности ниже.

import itertools
from collections import Counter

def primes(n):
    primfac = Counter()
    d = 2

    while d ** 2 <= n:
        while (n % d) == 0:
            primfac[d] += 1
            n //= d
        d += 1

    if n > 1:
       primfac[n] += 1

    return primfac

def primecombo(n):
    factor_sums = [[p * e for e in range(exp + 1)] for p, exp in primes(n).items()]

    sums = set(sum(partition) for partition in itertools.product(*factor_sums))

    return sums

primecombo(4096) # {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24}

Сложность времени

Сложность по времени зависит от распределения ваших простых факторов. Худший сценарий наступает, если существует k различных факторов. Тогда наш itertools.product имеет размер 2 k. Таким образом, алгоритм

О (к * 2 к)

person Olivier Melançon    schedule 12.04.2018
comment
Не могли бы вы добавить в свой отличный ответ время работы исходного кода OP и вашего кода? - person Gabriel; 12.04.2018