Проблема с реализацией счетчика посещений, который записывает попадания за последние 5 минут

Question

Я столкнулся с этой проблемой и все еще пытаюсь решить эту проблему:

Вы хотите зарегистрировать количество посещений сайта.

Реализовать две функции, log_hit (), который вызывается при регистрации попадания, и get_hits_in_last_five_minutes (), которая возвращает общее количество попаданий в последние пять минут. Предположим, что все метки времени располагаются в возрастающем порядке.

Моя идея (попытка решить проблему):

Структура данных: массив.

Моя логика:

Когда вызывается log_hit (), мы в основном сохраняем время в мс (Date (). GetTime () в мс) в массиве и сохраняем обращения к определенной секунде в hashmap.

function Counter() {
  this.map = {};
  this.store = [];
}

Counter.prototype.log_hit = function() {
  const d = new Date().getTime()/1000;
  this.store.push(d);
  this.map[d] = this.map[d] ? this.map[d]++ : 1;
}

Counter.prototype.get_hits_in_last_five_minutes = function() {
 const fiveMin = 60 * 60; //seconds.
 const initalPointer = new Date().getTime() / 1000 - fiveMin;
 // Somehow retrieve the value and return it back
}

Однако я не думаю, что это самый оптимальный способ ее решения, если бы я хотел продлить решение на час или какую-то другую гранулярность.

Как бы я решил такую ​​проблему?

Answer 1

Нам нужно использовать этот факт -

Предположим, что все метки времени располагаются в порядке возрастания.

Алгоритм:

• Мы записываем каждое попадание в массив и постепенно увеличиваем его размер на 1.
• Чтобы получить нет. хитов за последние 5 минут ( без учета текущего попадания ), мы выполняем двоичный поиск , чтобы получить наш ответ, поскольку все метки времени располагаются в возрастающем порядке, что сортироваться по умолчанию.
• Сначала мы выполняем двоичный поиск в массиве, чтобы получить последний действительный индекс верхней границы по времени t, предоставленному get_hits_in_last_five_minutes().

• Upper bound используется предел, до которого мы могли бы использовать хиты, чтобы судить нет. звонков за последние 5 минут. Это необходимо, поскольку в заявлении о проблеме указано get_hits_in_last_five_minutes (), которое возвращает общее количество обращений за последние пять минут . Таким образом, технически это означает, что он будет использоваться как API, чтобы проверить, сколько вызовов было сделано за 5 минут до времени передачи параметра t. не гарантирует , что время, переданное этому методу t, всегда будет последней вставленной отметкой времени в счетчике. В связи с этим нам нужно искать верхнюю границу в массиве, то есть до какого индекса хиты, хранящиеся в массиве, могут считаться действительными для нашего ответа.

• Во-вторых, мы выполняем двоичный поиск от 0 до upper_bound, чтобы получить все действительные попадания, которые были за последние 5 минут до t.

• Сложность пространства: O (n) , где n - это номер. хитов зарегистрировано.

• Сложность времени:
  • O(log(n)) для поиска верхней границы.
  • O(log(n)) чтобы получить фактические хиты, зарегистрированные за последние 5 минут.
  • Общая сложность = O(log(n)) + O(log(n)) = 2 * O(log(n)) = O(log(n))

Примечание: Я преобразовал время t в секунды при сохранении и поиске.

Код:

function Counter() {
  this.hits = [];
  this.hits_size = 0;
}

Counter.prototype.log_hit = function(t) {
  this.hits[this.hits_size++] = t * 60;
}

Counter.prototype.get_hits_in_last_five_minutes = function(t) {
  if (this.hits_size < 2) return 0;
  t *= 60;
  var upper_bound = this.getUpperBound(t);
  this.last_call_type = 2;
  var low = 0,
    high = upper_bound;
  while (low <= high) {
    var mid = low + parseInt((high - low) / 2);
    if (this.hits[mid] > t - 300) high = mid - 1;
    else if (this.hits[mid] < t - 300) low = mid + 1;
    else return upper_bound - mid + 1;
  }

  return upper_bound - low + 1;
}

Counter.prototype.getUpperBound = function(t) {
  var low = 0,
    high = t > this.hits[this.hits_size - 1] ? this.hits_size - 1 : this.hits_size - 2;
  var ans = 0;
  while (low <= high) {
    var mid = low + parseInt((high - low) / 2);
    if (this.hits[mid] >= t) {
      high = mid - 1;
    } else {
      ans = mid;
      low = mid + 1;
    }
  }

  if (high < 0) return -1;
  return ans;
}


console.log("*****Counter 1******");
var c1 = new Counter();
c1.log_hit(1);
console.log("Registered, 1 = " + c1.get_hits_in_last_five_minutes(1));
c1.log_hit(2);
console.log("Registered, 2 = " + c1.get_hits_in_last_five_minutes(2));
c1.log_hit(3);
console.log("Registered, 3 = " + c1.get_hits_in_last_five_minutes(3));
c1.log_hit(4);
console.log("Registered, 4 = " + c1.get_hits_in_last_five_minutes(4));
c1.log_hit(5);
console.log("Registered, 5 = " + c1.get_hits_in_last_five_minutes(5));
c1.log_hit(6);
console.log("Registered, 6 = " + c1.get_hits_in_last_five_minutes(6));
c1.log_hit(7);
console.log("Registered, 7 = " + c1.get_hits_in_last_five_minutes(7));
c1.log_hit(8);
console.log("Registered, 8 = " + c1.get_hits_in_last_five_minutes(8));
c1.log_hit(9);
console.log("Registered, 9 = " + c1.get_hits_in_last_five_minutes(9));
c1.log_hit(10);
console.log("Registered, 10 = " + c1.get_hits_in_last_five_minutes(10));

console.log("*****Counter 2******");
var c2 = new Counter();
c2.log_hit(2);
console.log("Registered, 2 = " + c2.get_hits_in_last_five_minutes(2));
c2.log_hit(7);
console.log("Registered, 7 = " + c2.get_hits_in_last_five_minutes(7));
c2.log_hit(8);
console.log("Registered, 8 = " + c2.get_hits_in_last_five_minutes(8));
c2.log_hit(9);
console.log("Registered, 9 = " + c2.get_hits_in_last_five_minutes(9));
c2.log_hit(10);
console.log("Registered, 10 = " + c2.get_hits_in_last_five_minutes(10));
c2.log_hit(11);
console.log("Registered, 11 = " + c2.get_hits_in_last_five_minutes(11));
c2.log_hit(12);
console.log("Registered, 12 = " + c2.get_hits_in_last_five_minutes(12));
c2.log_hit(17);
console.log("Registered, 17 = " + c2.get_hits_in_last_five_minutes(17));
console.log("Unregistered, 18 = " + c2.get_hits_in_last_five_minutes(18));
c2.log_hit(19);
console.log("Registered, 19 = " + c2.get_hits_in_last_five_minutes(19));
console.log("Unregistered, 20 = " + c2.get_hits_in_last_five_minutes(20));
c2.log_hit(21);
console.log("Registered, 21 = " + c2.get_hits_in_last_five_minutes(21));
console.log("Unregistered, 6 = " + c2.get_hits_in_last_five_minutes(6));
console.log("Unregistered, 500 = " + c2.get_hits_in_last_five_minutes(500));
console.log("Unregistered, 15 = " + c2.get_hits_in_last_five_minutes(15));
console.log("Registered, 17 = " + c2.get_hits_in_last_five_minutes(17));

Почему бинарный поиск?

• Вы можете спросить, почему бы не выполнить цикл в обратном направлении и получить счетчик всех этих значений, которые меньше t - 300. Таким образом, это может быть O(1) за звонок.
• Обратите внимание, что наше пространство поиска чуть меньше t - 300. Если это увеличивается, например, t - 9000, то наша обратная итерация также увеличивается до 9000, а если число вызовов для get_hits_in_last_five_minutes() оказывается равным 10000 или более, то сложность простого цикла умножается на общую сложность. Таким образом, это может быть

10000 звонков на get_hits_in_last_five_minutes() *9000* 1098 *

Если мы используем алгоритм, описанный выше, это будет

10000 звонков на get_hits_in_last_five_minutes() * log (n)

Что делать, если вызовы никогда не заканчиваются (бесконечно)?

• Это зависит от того, как мы решили использовать метод get_hits_in_last_five_minutes().

  • Если время t, прошедшее до вызовов, сделанных на get_hits_in_last_five_minutes(), всегда будет неубывающим, то мы могли бы обрезать / удалить попадания из нашего хранилища.

    • Чтобы сделать это, мы снова можем выполнить бинарный поиск, чтобы получить индекс максимального значения из нашего хранилища, который не попадает под t - 300. После этого мы можем просто сделать срез массива и сбросить this.hits_size на новую длину.
      • Нам нужно сделать это в методе log_hit(), а не get_hits_in_last_five_minutes(), так как время t передано ему не обязательно должно быть частью наших зарегистрированных обращений .
      • Использование array slice может немного усложнить задачу, поскольку возвращает пустую копию исходного массива, а его сложность равна O(N), где N равно end - start. См. сложность среза массива . Чтобы избежать этого, мы можем составить связанный список и сохранить в нем данные, а также использовать карту для хранения узлов. Таким образом, мы можем сбросить заголовок списка и выполнить обрезку / усечение O(1). Нам также нужно будет поддерживать количество усеченных узлов, поскольку мы не можем сбросить карту с новыми значениями.

  • Если время, которое t прошло для звонков, сделанных на get_hits_in_last_five_minutes() для вашего сайта, находится в произвольном порядке, то мы не можем ничего обрезать, поскольку нам нужны все данные, чтобы дать ответ. В этом случае, вероятно, хранить данные в базе данных. Хорошая часть в том, что вы можете просто запросить свой ответ из БД и вместо выполнения вычислений в javascript.

Answer 2

Использование очереди было бы правильным способом решения этой проблемы.

   var HitCounter = function() {
            this.queue = [];
   };

/**
 * Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). 
 * @param {number} timestamp
 * @return {void}
 */
HitCounter.prototype.hit = function(timestamp) {
    this.queue.push(timestamp);
};

/**
 * Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). 
 * @param {number} timestamp
 * @return {number}
 */
HitCounter.prototype.getHits = function(timestamp) {
    while(this.queue.length && this.queue[0] <= timestamp-300) {
        this.queue.shift();
    }
    return this.queue.length;
};

const counter = new HitCounter();
counter.hit(1);
counter.hit(2);
counter.hit(3);
counter.getHits(4);
counter.hit(300);
counter.getHits(300);
console.log(counter.getHits(301)); // should output 3.