Форум » Обработка целых чисел » Время выполнения задачи №25 » Ответить
Время выполнения задачи №25
nikson: Коллеги, которые оказывают помощь Полякову К.Ю в разработке задач, предлагаю не создавать больших интервалов исходных данных. 1. Я не думаю, что во всей стране на егэ будут мощные ПК. 2. Когда время ожидания результата будет более минуты, даже используя round(sqrt(n)+1) ) для ускорения, могут быть аппеляции, что потрачены лишние минуты, которых не хватило для решения других задач. 3. Если посмотреть Демо 2021, то разработчики в 25 задаче создали интервал [174457; 174505] . Всего 48 чисел. 4. Даже если создать интервалы в задачах 20000 обрабатываются практически мгновенно. Думаю можно подобрать в условиях задач такие диапазоны, когда ответ появится на экране в течении 30 секунд максимум. 5. Ведь цель на егэ проверить не быстродействие компьтера, а умениие найти верное решение. 6. Конечно, можете возразить: нужно применять более эффективные алгоритмы. Но даже в простых задачах иногда это не спасает.
Ответов - 6
nikson: Вот пример задачи: Определите количество простых чисел в диапазоне [2; 20000]. Используя стандартный код - 12с; Используя перебор нечетных - 3 ; Используя n**0.5 - 1 с; Увеличиваем диапазон до 50 000.. Получается 113, 22 и 3 с соответственно. Но в списке задач есть задача №78 - 80. там числа от 200 000. Первые два алгоритма использовать нельзя по времени. Третий считает 31с (для 200 000) Для условия 3577000 даже третий алгоритм не спасает
nikson: К примеру авторский код (Б.С.Михлин) http://egekp.unoforum.pro/?1-22-0-00000016-000-0-0-1605379770 на моем компьютере выполняется 61 секунду. При этом программа находит максимальное количество делителей - 80, на отрезке [586132; 586430]. Но стоит уменьшить значения интервала до [50132, 50430] и программа работает всего 5 секунд.
nikson: Ну заканчивая обсуждение темы с интервалами приведу пример: Стример Информатик Бу решая задачу Е. Джобса №97 https://www.youtube.com/watch?v=ikbkS3aSWtA Время выполнения задачи на Паскале составило 11 секунд. (смотреть с 1ч 56 мин 35 с). Я для чистоты эксперемента взял и один в один перебрал код на Python.[pre2] import time start = time.time() for n in range(135790, 163228+1): s = 0 # сумма k = 0 # количество for d in range(2, n//2+1): if n%d == 0: k += 1 s += d if s > 460000: print(k, s) print(time.time() - start)[/pre2] Время выполнения - 1183.68 c У меня процессор Core i7 - 2.4 Ghz ОЗУ - 12Гб
Поляков: nikson пишет: Время выполнения - 1183.68 c У меня процессор Core i7 - 2.4 Ghz ОЗУ - 12Гб Неудачный пример. Если сделать перебор до sqrt(n), время около 2 с на i3 / 4Гб.
nikson: Поляков пишет: Неудачный пример. Если сделать перебор до sqrt(n), время около 2 с на i3 / 4Гб. Мне интересно было сравнить один и тот же код у стриммера на Паскале и на Питоне
Поляков: nikson пишет: предлагаю не создавать больших интервалов исходных данных. Андрей Николаевич, спасибо за замечание. Мысль дельная. Но, на мой взгляд, выполнение программы при оптимальном алгоритме в пределах 20-30 секунд на среднем компьютере вполне допустимо. Заодно алгоритмы подучим, рекурсию будем заменять динамическим программированием, использовать перебор до корня и т.п.
полная версия страницы