Как улучшить код для решения арифметической задачи?

Question

Приложенный ниже код решает следующую задачу:

Найдите наибольшее натуральное число, такое, что если прибавить к нему сумму его цифр, получится число, введённое пользователем.

# Найдите наибольшее натуральное число, такое, что если прибавить
# к нему сумму  его цифр, получится число, введённое пользователем.

n = int(input())
k = n
while (k + sum(int(digit) for digit in str(k)) != n) and k!=0:
    k -= 1
if k!=0:
    print(k)
else:
    print('No such positive integer.')

Приму любую конструктивную критику, направленную на оптимизацию вышеизложенного кода.

Answer 1

Приведу небольшой пример как можно решить задачу за меньшее время, тест скорости включен.

Основная идея

Для вычисления суммы пользуемся исключительно арифметикой.

Код

import time

def test(n):
    k = n
    while (k + sum(int(digit) for digit in str(k)) != n) and k!=0:
        k -= 1
    if k!=0:
        return(k)
    else:
        return('No such positive integer.') 

def findSum(num):
    s = 0
    while num > 0: 
        s += num % 10
        num = num // 10
    return s    

def test2(n):
    k = n
    while k and (k + findSum(k) != n):
        k -= 1
    if k:
        return(k)
    return('No such positive integer.') 

start = time.time()
for i in range(10000):
    r = test(i)
end = time.time()
print(end - start, r)

start = time.time()
for i in range(10000):
    r = test2(i)
end = time.time()
print(end - start, r)

Вывод:

9.353121042251587 9972
4.550509214401245 9972

В итоге мы получили почти двухкратную производительность.

Answer 2

Первая оптимизация которая приходит в голову - сумма цифр любого k ≤ n не превосходит 9·<количество цифр n>. Другими словами, не надо отступать слишком далеко от n:

def k(n):
    for k in range(n, max(0, n - 9 * len(str(n)) - 1), -1):
        if k + sum(map(int, str(k))) == n:
            return k
    return None

Сложность старого варианта была n·log n. Первый множитель - число повторений цикла проверки, второй - стоимость одной проверки (сложность занижена, но для наших целей сойдет).

Новый вариант имеет сложность log² n. Число итераций сократилось в худшем случае с линейного до логарифма.

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

P.S. Про замену str делениями. В теории замена ухудшает сложность. Чтобы извлечь из числа n все цифры делением на десять требуется log² n операций - log n делений, каждое из которых тоже стоит log n. Функция str могла бы делать это быстрее - перевод между системами счисления можно сделать с лучшей сложностью...

P.P.S. ... но в Питоне str реализован медленно, за квадрат логарифма.

БЛОГ НА HUSL

Как улучшить код для решения арифметической задачи?

Ответы (2 шт):