Все ли задачки из проекта Эйлера должны быстро вычисляться на Python?
Осваиваю Python, параллельно решаю задачки из проекта Эйлера. Иногда реализация решения очередной задачки хромает и код выходит медленный. Ну т.е. сама задача решается правильно, но очень медленно (например время выполнения около часа). Обычно в задачах Эйлера специально подбираются большие числа и большие диапазоны, да и сам Python не отличается скоростью, но всё-таки, хотелось бы точно знать, конкретная задача в принципе на Python решается медленно или проблема в моей реализации. В готовые решения заглядывать не хочу, поделитесь у кого есть опыт решения этих задачек на Python - есть ли там задачи, которые выполняются долго (больше 5-10 минут) ? Или же для всех есть быстрые реализации ?
Речь не про какую-то конкретную задачку, просто периодически реализация выходит подозрительно медленной.
Soul1 дорогой пользователь, настоятельно рекомендуем еще раз обратить самое пристальное внимание на п. 3.1 регламента работы сервиса (и, в особенности, на его последний абзац).
В противном случае ваши вопросы будут удаляться по причине тег-спама, а систематические нарушения приведут к блокировке учетной записи.
Я не знаком, к сожалению, с проектом Эйлера, но обратил бы в первую очередь на сложность вашего алгоритма. И если внезапно окажется, что это алгоритм сложности O(N!), то тут надо скорее удивляться тому, что он вообще завершился при нашей жизни и начать искать более эффективный подход (если он теоретически есть, разумеется).
Модератор, извините, я наоборот думал, что чем больше тегов тем лучше, а кроме "Python" и "программирование" других тегов то и нет, вот и подумал, что лишь 1 тега мало и вопрос могут даже не опубликовать. Спасибо, буду иметь в виду !
Владимир, Ну, 1 алгоритм я написал, в задачке нужно было вычислить для диапазона 600 млрд, алгоритм был линейный (без прогрессии), поэтому было нетрудно высчитать скорость на основе скорости выполнения более лёгкого примера, например в диапазоне 600 млн. Для 600 млн вычислило примерно за 1,5 минуты. Выходит для 600 млрд будет считаться в 1000 раз больше (алгоритм линейный), около суток.
Хотя задачи Эйлера не предназначены конкретно для Python (они широкого профиля), поэтому может это и не так уж удивительно, ведь на других языках бы считалось сильно быстрее.
Я написал программу, теперь придётся ждать результата вычислений пару дней?
Разумеется, нет! Каждая задача подчиняется "правилу одной минуты", которое гласит: несмотря на то, что на построение алгоритма решения могут уйти часы, эффективная реализация позволяет получить ответ на компьютере средней вычислительной мощности меньше, чем за одну минуту.
Soul1, тут явно не нужен полный перебор. Самый правильный вариант, наверное, разобраться в алгоритмах факторизации и разложить число на простые множители эффективным образом. Самый "инженерный" это взять таблицу простых чисел от 1 до корня квадратного из целевого числа и факторизовать наше целевое число с ее помощью. Идем с конца таблицы, делим целевое число на все эти числа по очереди, если результат получается целым числом, то пытаемся рекурсивно факторизовать таким же макаром получившееся частное. Хотя я не уверен, что использование таблиц простых чисел считается "хорошим" решением в этом проекте :).
Я реализовал так: написал простенький алгоритм проверки является ли число простым, затем начал перебирать числа от максимального до 0 с шагом -1, каждое число проверяем на условие 1) Является ли целочисленным делителем 2) Является ли простым числом. Так как перебираем числа от большего к меньшему, то первое найденное число и будет наибольшим простым делителем.
По вашему варианту могу сказать, что использование таблицы с уже найденными простыми числами является нечестным )
А почему вы пишете, что поиск делителя нужно начинать с квадратного корня исходного числа ? В задаче же не говорится, что само исходное число является простым.
Нет, это скорее у вас костыль какой-то написан. Попробуйте подумать над задачей и сделать решение производительней. Вероятно, вы используете списки или другие тяжёлые инструменты этого прекрасного языка. Обычно такие задачи нужно решать через циклы и со статическими списками. Эйлер учит алгоритмам
