Определенная сила суммы цифр N == N (работает слишком медленно)
Я пытаюсь написать сценарий Python, который находит все целые числа (N), где определенная степень суммы цифр N равна N. Например, N=81 квалифицируется, потому что 8 + 1 = 9, и определенная степень 9 (а именно 2) = 81.
Диапазоны, которые я выбрал, являются произвольными. Мой сценарий работает, но он очень, очень медленный. В идеале я хотел бы найти первые 30 таких целых чисел примерно за 6000 мс.
Мое первое решение:
def powerOfSum1():
listOfN = []
arange = [a for a in range(11, 1000000)] #range of potential Ns
prange = [a for a in range(2, 6)] # a range for the powers to calculate
for num in arange:
sumOfDigits = sum(map(int, str(num)))
powersOfSum = [sumOfDigits**p for p in prange]
if num in powersOfSum:
listOfN.append(num)
return listOfN
Во втором решении я попытался сохранить все полномочия для каждого sumOfDigits, но это не сильно улучшило производительность.
def powerOfSum2():
listOfN = []
powers= {}
for num in range(11, 1000000):
sumOfDigits = sum(map(int, str(num)))
summ = str(sumOfDigits)
if summ in powers:
if num in powers[summ]:
listOfN.append(num)
else:
powersOfSum = [sumOfDigits**p for p in range(2,6)]
powers[summ] = powersOfSum
if num in powers[summ]:
listOfN.append(num)
return listOfN
Я еще не изучал структуры данных и алгоритмы, поэтому буду признателен за любые указания по повышению эффективности этого сценария.
4 ответа
Обновление: я обнаружил, что это проблема Project Euler (#119), и я нашел в основном то же решение, которое уже задокументировано: http://www.mathblog.dk/project-euler-119-sum-of-digits-raised-power/
Я не уверен, что я слишком упрощен, но просто перебирать полномочия для диапазона чисел кажется довольно быстрым. Вы не можете гарантировать заказ, поэтому рассчитайте больше, чем нужно, а затем отсортируйте и возьмите топ 30. Я не могу доказать, что получил их все, но я проверил base до 500 и exp до 50 и возвращает ту же самую верхнюю 30. Следует отметить, что OP только тестировал показатели до 5, что значительно ограничивает число результатов:
def powerOfSum():
listOfN = []
for base in range(2, 100):
num = base
for _ in range(2, 10):
num *= base
if sum(map(int, str(num))) == base:
listOfN.append(num)
return sorted(listOfN)[:30]
powerOfSum()
Выход
[81,
512,
2401,
4913,
5832,
17576,
19683,
234256,
390625,
614656,
1679616,
17210368,
34012224,
52521875,
60466176,
205962976,
612220032,
8303765625,
10460353203,
24794911296,
27512614111,
52523350144,
68719476736,
271818611107,
1174711139837,
2207984167552,
6722988818432,
20047612231936,
72301961339136,
248155780267521]
Бег timeit по нему (в том числе по сорту) я получаю:
100 loops, best of 3: 1.37 ms per loop
Это прекрасное время, чтобы открыть профилировщик и посмотреть, где ваш код тратит все свое время. Для этого я положил немного cProfiler обертка вокруг вашего кода:
#!/usr/bin/env python
import cProfile
import math
def powerOfSum1():
listOfN = []
arange = [a for a in range(11, 1000000)] #range of potential Ns
prange = [a for a in range(2, 6)] # a range for the powers to calculate
for num in arange:
sumOfDigits = sum(map(int, str(num)))
powersOfSum = [sumOfDigits**p for p in prange]
if num in powersOfSum:
listOfN.append(num)
return listOfN
def main():
cProfile.run('powerOfSum1()')
if __name__ == "__main__":
main()
Запустив это, вот что я получил:
⌁ [alex:/tmp] 44s $ python powers.py
1999993 function calls in 4.089 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.005 0.005 4.089 4.089 <string>:1(<module>)
1 0.934 0.934 4.084 4.084 powers.py:7(powerOfSum1)
999989 2.954 0.000 2.954 0.000 {map}
10 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
2 0.017 0.009 0.017 0.009 {range}
999989 0.178 0.000 0.178 0.000 {sum}
Если вы посмотрите, кажется, что большую часть времени тратят на это map звоните, куда вы поворачиваете num в строку, затем сделайте каждую цифру целым числом, которое затем суммируется.
Имеет большой смысл, что это будет медленная часть программы. Мало того, что вы делаете это много, но это медленная операция: в этой строке вы выполняете операцию синтаксического анализа строки, а затем сопоставляете функцию преобразования int каждому символу в строке, а затем суммируете их.
Могу поспорить, что если вы сможете вычислить сумму цифр без предварительного преобразования строки, это будет намного быстрее.
Давайте попробуем это. Я сделал некоторые другие изменения, такие как удаление избыточных списков в начале. Вот что я получил:
#!/usr/bin/env python
#started at 47.56
import cProfile
import math
MAXNUM = 10000000
powersOf10 = [10 ** n for n in range(0, int(math.log10(MAXNUM)))]
def powerOfSum1():
listOfN = []
arange = range(11, MAXNUM) #range of potential Ns
prange = range(2, 6) # a range for the powers to calculate
for num in arange:
sumOfDigits = 0
for p in powersOf10:
sumOfDigits += num / p % 10
powersOfSum = []
curr = sumOfDigits
for p in prange:
curr = curr * sumOfDigits
if num < curr:
break
if num == curr:
listOfN.append(num)
return listOfN
def main():
cProfile.run('powerOfSum1()')
if __name__ == "__main__":
main()
Что значит cProfile должен сказать?
⌁ [alex:/tmp] 3m42s $ python powers.py
15 function calls in 0.959 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.006 0.006 0.959 0.959 <string>:1(<module>)
1 0.936 0.936 0.953 0.953 powers.py:13(powerOfSum1)
10 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
2 0.017 0.009 0.017 0.009 {range}
4 секунды до 0,9 секунды? Намного лучше.
Если вы действительно хотите увидеть эффект, добавьте дополнительный ноль к верхней границе arange, На моем ящике оригинальный код занимает ~47 секунд. Модифицированный код занимает ~10.
Профилировщик - ваш друг, и преобразование строк не является бесплатным, если вы делаете это сотни тысяч раз:)
Ваше решение проверяет каждое возможное целое число, чтобы увидеть, что оно может быть решением. Более эффективно проверять только целые числа, которые на самом деле являются полномочиями, чтобы увидеть, являются ли они правильными ответами - потому что их меньше. Вот кое-что, что делает это. Но, вероятно, потребуется более 6 секунд, чтобы найти 30 - они быстро становятся дефицитными.
РЕДАКТИРОВАТЬ - обновлено для более быстрого суммирования цифр, предложенного в комментариях Padraic Cunningham и fjarri, а затем обновлено, чтобы добавить пару дополнительных настроек, сделать его генератором и сделать его дружественным к Python-3.
Это все еще становится медленным быстро, но алгоритм может быть распараллеленным - возможно, вы могли бы поместить суммирование цифр в отдельный процесс.
РЕДАКТИРОВАТЬ 2 - Сбросить некоторое время, выполнив быструю проверку того, равны ли основание и значение результата по модулю 9. Возможно, существуют дальнейшие трюки теории чисел...
import heapq
import functools
def get_powers():
heap = []
push = functools.partial(heapq.heappush, heap)
pop = functools.partial(heapq.heappop, heap)
nextbase = 3
nextbasesquared = nextbase ** 2
push((2**2, 2, 2))
while 1:
value, base, power = pop()
if base % 9 == value % 9:
r = 0
n = value
while n:
r, n = r + n % 10, n // 10
if r == base:
yield value, base, power
power += 1
value *= base
push((value, base, power))
if value > nextbasesquared:
push((nextbasesquared, nextbase, 2))
nextbase += 1
nextbasesquared = nextbase ** 2
for i, info in enumerate(get_powers(), 1):
print(i, info)
[править: из-за ошибки в данном алгоритме, который я транскрибировал, этот метод довольно медленный (примерно так же быстро, как и другие методы). Я держу это здесь для справки кода. Однако это, кажется, лучшее, что можно сделать, не прибегая к уловкам теории чисел.]
При вычислении целочисленных последовательностей вы должны сначала перейти к Слоану и ввести последовательность. Это последовательность A023106 "a(n) является степенью суммы его цифр"., Первые 32 таких номера до 68719476736 можно найти, нажав на ссылку "список". Часто можно найти алгоритмы (которые могут или не могут быть эффективными), а также ссылки. Там также связаны первые 1137 таких номеров до [некоторого числа, достаточно большого, чтобы заполнить несколько абзацев]
Теперь что касается эффективного алгоритма: если у вас нет способа пропустить диапазоны чисел, не глядя на них, или если мы не можем использовать какое-то математическое свойство чисел, вы застряли в алгоритме O(N). Другой способ, которым вы могли бы подойти к нему, это попытаться вычислить все степени (что позволяет пропустить все числа), а затем проверить каждую степень P=n^m, чтобы увидеть, "есть ли число, цифры которого суммируются с некоторой степенью P (или любой другой)".
На самом деле этот алгоритм уже предоставлен нам в приведенной выше ссылке. Алгоритм, приведенный в приведенной выше ссылке: (в Mathematica):
fQ[n_] := Block[
{b = Plus @@ IntegerDigits[n]},
If[b > 1, IntegerQ[ Log[b, n]] ]
];
Take[
Select[
Union[ Flatten[
Table[n^m, {n, 55}, {m, 9}]
]], fQ[ # ] &],
31
]
(* Robert G. Wilson v, Jan 28 2005 *)
Свободный перевод:
def test(n):
digitSum = sum of digits of n
return n is a power of digitSum
candidates = set(n^m for n in range(55) for m in range(9))
matches = [c for c in candidates if test(c)]
Полная реализация будет:
from math import * # because math should never be in a module
def digitSum(n):
return sum(int(x) for x in str(n))
def isPowerOf(a,b):
# using log WILL FAIL due to floating-point errors
# e.g. log_3{5832} = 3.0000..04
if b<=1:
return False
# using http://stackru.com/a/4429063/711085
while a%b==0:
a = a / b
return a==1
def test(n):
return isPowerOf(n, digitSum(n))
M = 723019613391360 # max number to check
candidates = set(n**m for n in xrange(int(sqrt(M)+1))
for m in xrange(int(log(M,max(n,2)))+1))
result = list(sorted([c for c in candidates if test(c)]))
выход:
>>> result
[2, 3, 4, 5, 6, 7, 8, 9, 81, 512, 2401, 4913, 5832, 17576, 19683, 234256, 390625, 614656, 1679616, 17210368, 34012224, 52521875, 60466176, 205962976, 612220032, 8303765625, 10460353203, 24794911296, 27512614111, 52523350144, 68719476736, 271818611107, 1174711139837, 2207984167552, 6722988818432, 20047612231936, 72301961339136, 248155780267521]
К сожалению, это занимает значительное количество времени. Например, выше, мы должны проверить 53 863 062 кандидата, что может занять несколько минут.