Форум » Массивы, сортировка, работа с файлами » Задача 4741, слишком долго считается » Ответить
Задача 4741, слишком долго считается
mr_vkv: Добрый день. Пытаюсь решить задачу https://kpolyakov.spb.ru/school/ege/gen.php?action=viewTopic&topicId=4741 Для анализа нагрузки сервера для каждого запроса в журнал записываются время начала и время завершения его обработки (в миллисекундах от момента начала исследований). Если начальное время равно 0, запрос начал обрабатываться до начала исследований, если конечное время равно 0, то обработка запроса закончилась после окончания исследований. Необходимо определить наибольшее количество запросов, которые сервер обрабатывал одновременно в течение суток, начиная с момента K, и суммарное время, в течение которого обрабатывалось это максимальное количество запросов. Входные данные представлены в файле 26-66.txt следующим образом. Первая строка входного файла содержит количество записей N и время K. Каждая из следующих N строк содержит два целых числа: время начала и время завершения обработки одного запроса (в миллисекундах). Запишите в ответе два числа: наибольшее количество запросов, которые сервер обрабатывал одновременно в течение указанных суток, и суммарное время, в течение которого обрабатывалось это максимальное количество запросов. Мое решение(на питоне): 1. В лоб. Всего есть около 52 тысяч записей в файле. Считываю в массив данные попутно ищу самое позднее время окончания процесса(но не ноль). Массив выглядит вот так: [[0, 125], [123, 3456], [12345, 0]], т.е. записываю время начала и конца процесса. Затем создаю массив заполненный нулями. Каждый элемент массива - милисекунда. Если в эту миллисекунду выполняется процесс, то увеличиваю элемент на 1. Иду по массиву процессов и для каждого процесса инкрементирую соответствующие элементы массива милисекунд. Затем остается пройтись по массиву милисекунд и найти максимальное значение в нем и сколько раз подряд оно встретилось. Но этот алгоритм работает слишком долго. Потому что время начала процессов и их окончания находятся где-то между 1 200 000 000 и 1 300 000 000. Получается я делаю 50 000 * 1 300 000 000 итераций (порядка 65 триллионов). Затем я решил схитрить. Я нашел самое раннее время начала выполнения процесса. И вычел его из времен всех процессов. Все равно как минимум первые 1 200 000 000 секунд ничего не происходит. Получилось, что все процессы теперь умещаются в отрезке времени от 0 до примерно 92 млн милисекунд. И запустил еще раз. Все еще невероятно долго выполнение. Давайте оптимизируем еще раз: при чтении файла не буду записывать в массив процессов те процессы, которые закончились раньше, чем время, начиная с которого надо считать их максимальное количество одновременно запущенных. Все еще долго, примерно на 76 часов выполнения. Явно я делаю что-то нет. Можно получить какую-нибудь подсказку или намек на правильный алгоритм. Целиком решение не совсем интересно, потому что хочу сам додуматься в итоге. Спасибо.
Ответов - 3
Поляков: Это задача 26-66 из основного сборника. Здесь есть решения всех 26-х задач на Python.
mr_vkv: Спасибо!
Тузова: Добрый день. В варианте Статграда 23.04.2024 есть задача, подобная 26-66 из основного сборника, но предложенное в 26-66 решение для неё не работает, даёт неверный ответ. По-видимому, проблема в том, что не учитывается факт одновременного начала и окончания процессов. Поэтому в некоторые моменты времени возникают "пики", которых на самом деле нет, они потом гасятся окончанием других процессов в тот же момент, но код это не учитывает. Например, пусть до наступления момента t наблюдалось 10 процессов - и это было максимальным значением. В момент t запустился новый процесс и одновременно закончился какой-то процесс. На мой взгляд, в момент t как было, так и осталось 10 процессов, а программа нам скажет, что максимальное количество процессов теперь 11. Я не права? Условие статградовской задачи: Информационная система выполняет сложные запросы. Для анализа нагрузки системы и её колебаний в течение суток в протокол занесли все запросы, выполненные в течение одного календарного дня. Для каждого запроса указаны время начала и время конца обработки. Входные данные Первая строка входного файла содержит целое число N (N ≤ 1 000 000) – общее количество запросов. Каждая из следующих N строк описывает один запрос и содержит 2 целых числа: время начала обработки запроса t1 и время окончания его обработки t2. Время задаётся в секундах от начала суток. Например, если t1 = 10 и t2 = 15, то обработка запроса началась через 10 секунд после начала суток и завершилась через 15 секунд после начала суток, то есть длилась 5 секунд. Гарантируется, что обработка всех запросов начинается и заканчивается в пределах одних суток, то есть 0 ≤ t1 < t2 ≤ 86400.
полная версия страницы