На уровне интеллекта всегда знал, что структуры данных (в каком виде хранятся и используются данные в программе) это важно, но знать и понимать это не одно и то же. Частенько бывало - "И так сойдёт, лень переделывать..." Сегодня - прочувствовал, почему правильный подбор структуры данных важен.
Когда то уже брался за проект Эйлера, но хватило меня не надолго, после 20-30 задач забросил. Недавно начал прорешивать по-новой, чтобы потренировать навыки программирования на Python.
Задача 23 - Non-abundant sums - быстро набросал простенький алгоритм, используя списки (list) и запустил. Жду - ответа нет, почитал книжку - ответа нет... Ладно пообедал, вернулся за монитор - наконец-то! 24 минуты ушло на подсчет. Ответ правильный, но - 24 минуты! У меня в памяти (не помню правда откуда) что задачи проекта Эйлер должны решаться в пределах минуты. Если дольше - скорее всего это не оптимальный алгоритм. Ладно, посижу-подумаю...
Алгоритм глобально не поменять, по крайней мере у меня идей нет, но можно заменить структуры данных. Множества (set) в некоторых аспектах быстрее, чем списки. Заменил список на множество, не трогая всю остальную логику, запускаю скрипт и 15 секунд спустя тот же самый ответ. Слегка дооформив, чтобы полнее использовать плюсы множеств, сократил время подсчета до 13 секунд.
Один и тот же алгоритм, разница только в используемых структурах данных - и такая разница во времени выполнения. 13 секунд против 24 минут
Когда то уже брался за проект Эйлера, но хватило меня не надолго, после 20-30 задач забросил. Недавно начал прорешивать по-новой, чтобы потренировать навыки программирования на Python.
Задача 23 - Non-abundant sums - быстро набросал простенький алгоритм, используя списки (list) и запустил. Жду - ответа нет, почитал книжку - ответа нет... Ладно пообедал, вернулся за монитор - наконец-то! 24 минуты ушло на подсчет. Ответ правильный, но - 24 минуты! У меня в памяти (не помню правда откуда) что задачи проекта Эйлер должны решаться в пределах минуты. Если дольше - скорее всего это не оптимальный алгоритм. Ладно, посижу-подумаю...
Алгоритм глобально не поменять, по крайней мере у меня идей нет, но можно заменить структуры данных. Множества (set) в некоторых аспектах быстрее, чем списки. Заменил список на множество, не трогая всю остальную логику, запускаю скрипт и 15 секунд спустя тот же самый ответ. Слегка дооформив, чтобы полнее использовать плюсы множеств, сократил время подсчета до 13 секунд.
Один и тот же алгоритм, разница только в используемых структурах данных - и такая разница во времени выполнения. 13 секунд против 24 минут
