实现记录最后5分钟点击次数的点击计数器的问题

Question

我遇到了这个问题，并且仍在努力解决这个问题：

您想要记录网站的点击次数。

实现两个功能，log_hit()，在注册命中时调用，以及get_hits_in_last_five_minutes()，返回命中总数在最后五分钟。假设所有时间戳都是按递增顺序排列的。

我的想法(试图解决问题)：

数据结构：数组。

我的逻辑：

当调用log_hit()时，我们基本上将时间存储在数组中，单位为ms(Date().getTime()单位为ms)，并将特定秒的命中率存储在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

使用队列将是处理此问题的正确方法。

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.

Answer 2

我们需要利用这个事实-

假设所有时间戳都是按递增顺序排列的。

算法：

• 我们记录数组中的每一次命中，并将其大小逐渐增加1
• 为了获得最后5分钟内的点击次数(不包括当前点击)，我们进行二进制搜索以获得答案，因为所有时间戳都是按递增顺序排列的，默认情况下会进行排序
• 首先，我们对数组进行二进制搜索，以获得相对于提供给get_hits_in_last_five_minutes()的时间t的最后一个有效上界索引

• 使用的Upper bound是我们可以使用命中率来判断最后5分钟内的呼叫数量的极限。这是必要的，因为问题语句显示get_hits_in_last_five_minutes()，它返回最后五分钟内的总命中次数。因此，从技术上讲，这意味着它将被用作API，以检查在参数经过时间t之前的5分钟内进行了多少次呼叫。它不能保证传递给此方法的时间t始终是计数器中最后插入的时间戳。因此，我们需要在数组中搜索上界，即，直到哪个索引，存储在数组中的命中数才能被视为对我们的答案有效。

• 其次，我们从0到upper_bound进行二进制搜索，以获得在t之前最后5分钟内的所有有效命中。

• 空间复杂度：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

如果我们使用上述算法，它将是

10000次呼叫get_hits_in_last_five_minutes()*log(n)

如果调用永远不会结束(无限)怎么办

• 这取决于我们选择如何使用get_hits_in_last_five_minutes()方法。

  • 如果传递给对get_hits_in_last_five_minutes()进行调用的时间t总是以非递减的方式，那么我们可以从存储中截断/删除命中。

    • 要做到这一点，我们可以再次进行二进制搜索，从不属于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()调用的时间是随机的，那么我们不能截断任何内容，因为我们需要所有数据来给出答案。在这种情况下，可能会将数据存储在数据库中。好的部分是，您可以从DB中查询答案，而不用用javascript进行计算。