Как я могу ускорить этот код на Python?

#python #performance

#python #Производительность

Вопрос:

 input_numbers=list(map(int,input().split()))
sum_number=0

def my_gen(a):
    i=0
    while i <= a:
        yield i
        i  = 1

for i in my_gen(input_numbers[0]):
    sum_number  = i**input_numbers[1]

print(sum_number%1000000009)

Я пытался не использовать generator, но это было слишком медленно.
итак, попробовал еще раз с генератором, и он тоже был медленным.

Как я могу сделать это быстрее?//

Дополнительная информация: мой бот для подсчета очков объявляет тайм-аут. и (1<=input_numbers[0]<=1,000,000,000) (1<= входные номера[1]<=50)

amp; Numpy не может быть использован

1. Ну, вы можете заменить свою my_gen() функцию на range() , чтобы начать.

2. Как вы думаете, почему зацикливание на целых числах является здесь узким местом? То, что вы должны попытаться оптимизировать, — это повторное возведение в степень. Вы my_gen просто range плохо переопределяете.

3. Насколько велики числа? Откуда проблема?

4. Что вы подразумеваете под «быстрее»? Есть ли у вас какой-нибудь тестовый пример, который доказывает, что это недостаточно хорошо для удовлетворения ваших требований?

5. Что было сказано в обсуждении leetcode? Я почти уверен, что это проблема.

Ответ №1:

Вы можете использовать формулу Фаульхабера, которая потребует только цикла над значением мощности (а не миллиарда чисел от 0 до N).

 from fractions import Fraction
from functools import lru_cache
@lru_cache()
def bernoulli(n,result=True): # optimized version
    A = [Fraction(1,n 1)]
    for j,b in enumerate(bernoulli(n-1,False) if n else []):
        A.append((n-j)*(b-A[-1]))
    return A[-1] if result else A

@lru_cache()
def comb(n,r):
    return 1 if not r else comb(n,r-1)*(n-r 1)//r

def powerSum(N,P):
    result = sum(comb(P 1,j) * bernoulli(j) * N**(P 1-j) for j in range(P 1))
    return (result / (P 1)).numerator

вывод:

 powerSum(100,3) # 25502500

sum(i**3 for i in range(100 1)) # 25502500 (proof)

powerSum(1000000000,50)%1000000009 
# 265558322 in 0.016 seconds on my laptop

sum(i**50 for i in range(1000000000 1))%1000000009 
# 265558322 (proof in 16.5 minutes)

1. Я написал версию, использующую целые числа по модулю 1000000009 вместо дробей , теперь, похоже, примерно в 15 раз быстрее в этом большом случае (см. Результаты тестов внизу).

2. Большое спасибо! Это действительно полезно!

Ответ №2:

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

Ответ №3:

Это плохая часть проблемы: https://projecteuler.net/problem=429 Но самое приятное — это решить эту проблему самому.