Блог

Учитывая серию временных меток операций сетевого ввода-вывода, какой наилучший алгоритм для вычисления активности для всех временных интервалов за день?

Например, выберите размер интервала = 30 секунд, затем 1 день = 24*60*60/30 =2880 слотов. Для одного временного интервала пометьте его как активный или неактивный на основе заданных данных временных рядов (активный, если в этом интервале есть активность, неактивный в противном случае). Затем вычислите коэффициент активности = (# активных слотов) / (# всего слотов).

Предложения?

Я не уверен, что вы подразумеваете под «лучшим» в этом контексте, но потерпите меня.

Итак, нам нужна функция, которая будет принимать количество временных интервалов в 24-часовом дне и временную метку и возвращать временной интервал, к которому принадлежит временная метка. Что-то вроде:

 int GetSlot(int numberOfSlots, int secondsSinceMidnight)
{
    int secondsInSlot = 24 * 60 * 60 / numberOfSlots;
    return secondsSinceMidnight / secondsInSlot;
}
  

Теперь создайте пустую структуру данных карты от временных интервалов до количества временных меток. Начните перебирать набор временных меток. Для каждой временной метки вызовите GetSlot ; вызовите его слот assignedSlot . Мы проверяем структуру данных карты, чтобы увидеть, содержит ли она запись для assignedSlot . Если это так, мы увеличиваем отображенный счетчик на единицу. В противном случае мы добавляем новую запись для assignedSlot и устанавливаем количество временных меток равным единице. Продолжить для всех временных меток.

В конце у нас есть одна запись в структуре данных карты для каждого активного слота. Мы знаем общее количество слотов, поэтому получить среднее количество активных слотов легко: map.size() / numberOfSlots . Мы запомнили больше информации, чем вам технически нужно, но все же.

Это O (n) времени и O (n) пространства.

Альтернативой может быть сортировка временных меток в порядке возрастания, а затем перебор их, подсчитывая активные временные интервалы по мере продвижения. Это может быть сделано O (n log n) времени и O (1) пространства.

Если у вас есть множество временных меток, которые плотно сгруппированы в нескольких временных интервалах, первый подход, скорее всего, будет более эффективным. Если у вас меньше временных меток, но они более равномерно распределены по временным интервалам, второй подход может быть лучше.