Оптимизация кода CodeWars Python 3.6: Факторная декомпозиция

Мне нужна помощь в оптимизации моего кода codewars, который называется факториальной декомпозицией. Цель ката состоит в том, чтобы разложить n! (факториал n) на его простые множители. Результат должен возвращать такую строку;

п = 12; разложить(12) -> "2^10 * 3^5 * 5^2 * 7 * 11"

Мой код работает правильно и проходит тесты, но когда я пытаюсь попробовать свой код, я получаю ошибку тайм-аута. Вот моя попытка;

def decomp(n):

    number_count = {2 : 1}
    return_str = ""

    def add_list(num):
        if num not in number_count:
            number_count[num] = 1
        else:
            number_count[num] += 1

    for x in range(n, 1, -1):
        add = False
        for y in range(1, x):
            if x == 1 or y == 1: continue
            a = True
            while a:
                if x % y == 0 and y != 1:
                    x = int(x / y)
                    add_list(y)
                else:
                    a = False
                    add = True

        if add and x != 1:
            add_list(x)

    number_count3 = {k: number_count[k] for k in sorted(number_count.keys())}

    for x, y in number_count3.items():
        if y == 1:
            return_str += str(x) + " * "
        else:
            return_str += str(x) + "^" + str(y) + " * "

    return return_str[:-3]

python

28.05.2019 01:12

Почему в Python есть оператор "pass"?

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Некоторые методы, о которых вы не знали, что они существуют в Python

Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...

Основы Python Часть I

Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?

LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

Оптимизация кода с помощью тернарного оператора Python

И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это

Советы по эффективной веб-разработке с помощью Python

Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.

979

Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы можете улучшить это, воспользовавшись некоторой теорией чисел. Для факториала типа 12! будет

12//2 + 6//2 + 3//2

коэффициенты два. Аналогичные закономерности будут справедливы и для всех остальных простых чисел. Таким образом, вы можете составить список простых чисел меньше n и быстро разложить экспоненту примерно так:

def primes(n):
    n += 1
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]


def mults(n):
    res = []
    for p in primes(n):
        rest = n
        s = 0
        while rest >0:
            j = rest // p
            s += j
            rest = j
        if s > 1:
            res.append(f'{p}^{s}')
        else:
            res.append(str(p))
    return ' * '.join(res)

mults(16)

Результат

'2^15 * 3^6 * 5^3 * 7^2 * 11 * 13'

Сравнение времени с оригиналом дает:

%timeit decomp(22)
54 µs ± 201 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit mults(22)
8.23 µs ± 30.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Что кажется достойным улучшением. Разница более заметна с большими n:

%timeit decomp(130)
823 µs ± 965 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit mults(130)
25.4 µs ± 73 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Спасибо за ваш ответ. Потрясающий подход. Вот только одна маленькая проблема. Функция «простые числа» не ищет n сама. Если n — простое число, ответ получается с одним множителем. Например, для 5 - "2^3 * 3" . Должно быть - "2^3 * 3 * 5". Я решил это, добавив n += 1 начало простой функции.

— 28.05.2019 04:51

Это хороший улов @UysalAltas, спасибо. Я отредактирую ответ, когда вернусь за компьютер.

— 28.05.2019 04:58

28.05.2019 01:54