Страницы

Поиск по вопросам

среда, 17 апреля 2019 г.

RecursionError: maximum recursion depth exceeded - как преодолеть?

Есть задача в вопросе; есть ее решение, где по изяществу Python "победил" C#, но вот у же на х=512 вылетает RecursionError: что посоветуете, отцы? Как преодолеть, если хочется посчитать для х=1024 скажем?
import functools from math import sqrt
@functools.lru_cache() def f(x): if x <=1: return 0 return 1 + min([ f(m + x // m - 2) for m in range(1,int(sqrt(x))+1) if x%m ==0])
добавлю после первого ответа:
Кто предложит как изменить алгоритм?
Кстати. Добавил количество рекурсии до 5000. Получается странная фигня. для 1024 считает, делая 3600 итераций, а для 2048 - "выбивает" интерпретатор на 1000+ рекурсии. Вообще не пойму - в чем проблема....


Ответ

Я python не знаю... Но на С++ решение этой задачи - вот в этом ответе: https://ru.stackoverflow.com/a/770528/195342
Как видите, на ideone решило миллиард за 0.04с без особого напряжения по стеку.
Ключевые моменты:
Перебор с отсечением
Мы сразу отсекаем особо длинные рекурсии, которые, очевидно, не приведут к оптимальному решению.
Начинаем со значений, близких к корню
Такая вот эвристика - там цепочки самые короткие, и мы сразу найдем решение, которое позволит отсечь большое количество заведомо плохих решений и не лезть глубоко в рекурсии.
Мемоизация
Позволит не считать повторно то, что уже посчитано. Кстати, подозреваю, что она не сильно и нужна, но сохранилась с предыдущих попыток решить задачу. Возможно, имеет смысл заменить массив, все-таки с немалым размером, на map (словарь). Это уже надо проверять и экспериментировать, но увы, сегодня на это уже нет времени.
Да, это не так красиво выглядит... Но зато решает с очень малой глубиной рекурсии и очень быстро.
Еще раз извиняюсь за незнание python... Вроде у малого в школе на следующий год обещают его преподавать - ну, вот тогда придется изучить и исправиться :)
Update
Использовал вместо массива на миллиард байт просто map. На моей машине миллиард вместо 77ms стал считаться 104ms, но зато при этом потребовалось только 44675 элементов в map. Экономию памяти оцените сами :)
При полном отказе от мемоизации не получается восстановить решение, но сама величина - 8 - для миллиарда находится за примерно 580ms.

Комментариев нет:

Отправить комментарий