Nagibator & Facktor
Nagibator Nagibator
Facktor Facktor
Facktor Facktor
Когда-нибудь задумывался, кто бы смог создать самый быстрый алгоритм ожидания лифта? У меня есть несколько улучшений, которые должны убрать миллисекунды, но интересно, сможет ли твоё соревновательное начало переиграть мою математику.
Nagibator Nagibator
Ну, давай, попробуй меня обогнать. Я готов показать тебе, как надо считать. Уверен, мой алгоритм будет самым быстрым – без всяких сомнений.
Facktor Facktor
Ладно, выкладывай цифры. Прогоню твой код на моём тестовом наборе и посмотрю, как среднее время ожидания упадет. Если ты меня обойдёшь, мне придётся обновлять таблицу рекордов. Давай посмотрим, что у тебя получилось.
Nagibator Nagibator
Конечно. Вот элегантное решение за O(1), просто ведётся скользящая сумма времени ожидания и счётчик — без перебора всей истории. Используется двусторонняя очередь для хранения последних N отметок времени запросов, а затем берётся среднее значение из скользящей суммы. На моём тестовом наборе это урезает среднее время ожидания примерно на 3–5 миллисекунд. Проверь это на твоём рейтинге – если результат улучшится, придётся признать, что я самый быстрый.
Facktor Facktor
Отлично, закину это в бенчмарк. Пришли код и небольшой набор данных, посмотрю, реально ли эта задержка в 3–5 миллисекунд проявится в моей текущей лучшей версии. Жду результатов.
Nagibator Nagibator
Вот код – минимальная штука, оценивает время ожидания лифта, сложность O(1), держит скользящую сумму последних N моментов запросов.
Facktor Facktor
Я запустил код с тестовыми метками времени. Оценщик показывает примерно 0.332 секунды для текущего среднего времени ожидания. Если сравнивать это с моим базовым значением в 0.335 секунд на том же наборе данных, получается сокращение примерно в 3 миллисекунды, что подтверждает твои слова. Отличная работа.