Какую структуру данных вы должны использовать, чтобы любой момент времени ваш сервер мог рассказать вам количество запросов, обработанных за последний час?Структура данных, которая будет использоваться для потоковой передачи данных
Например, в 10:20:23 вы спрашиваете, сколько запросов было обработано; он должен рассказать вам общее с 9:20:23 до сих пор. Аналогичным образом, в 10:00 он должен сообщить вам общее с 9:00.
Одним из вариантов является сохранение всех данных в стандартном динамическом массиве, отсортированном по времени. Всякий раз, когда есть входящий запрос, вы добавляете его в конец массива.
Чтобы узнать, сколько запросов произошло за последний час, вы можете выполнить двоичный поиск по массиву, чтобы найти первый запрос, который произошел в течение часа. Сравнение индекса этого элемента массива с общим количеством элементов даст вам общее количество запросов в этом окне времени.
Чтобы предотвратить слишком большой массив, одним из вариантов является обработка массива как растущего кольцевого буфера. Всякий раз, когда у вас заканчивается пробел в массиве, выполните двоичный поиск первого элемента в массиве, который произошел за последний час. Все элементы до этого можно отбросить. Если вы храните массив в виде кольцевого буфера, вы можете эффективно в O (1) время удалить все эти элементы, просто отрегулировав начальную позицию, чтобы логически удалить их из буфера. Если вам все еще нужно больше места, вы можете удвоить размер кольцевого буфера и скопировать старые элементы. Если вы применяете политику всегда копировать все, если после сброса старых элементов (например, 75%) заполняется больше, чем некоторая постоянная часть буфера, тогда это выходит за счет амортизации O (1) времени на каждую вставку.
Короче говоря, вы получаете амортизацию O (1) и O (log n) наихудший поиск количества запросов за последний час.
Надеюсь, это поможет!