abi*_*ipc 5 algorithm data-structures
在cs.stackexchange上问这个..得到了一个downvote ..因为我不是很清楚..所以我会尝试在这里更具体..
问:设计一个数据结构,以便在最后1分钟内返回到Web服务器的连接数.
假设 -
我在寻找:
效率 - 是否可以在O(1)中执行此操作？例如,如果我们在O(n)中这样做..问题是如果计算答案需要N毫秒......还有一些连接已经在N ms中排队了.我应该如何解决这个问题.或者我只能忽略小延迟而O(n)是一个好的表现
推理/方法 - 我们在生产中的无数部署中是否做了类似的事情？有类似的问题..？
这是"大数据"吗？用于存储连接的数据是否是大数据问题的最后N(N是10阶)分钟？
我的努力:我知道 -
方法 -
我还运行一个守护程序,删除超过10分钟的条目/文件..所以我不存储不需要的数据
Duk*_*ing 12
队列方法
使用队列.
每当有新请求出现时,请将其排队.
每当我们需要在最后一分钟获取请求数时,首先将所有发生的条目出列的时间超过一分钟(这是有效的,因为队列中的条目按顺序插入,因此队列已排序).然后返回队列的大小(可以O(1)通过存储变量来返回大小).
由于您说每秒有大量请求,因此每当您收到新请求时,您也可以将旧条目出列,这样可以使队列保持接近正确的大小,从而最大限度地减少计数操作所需的时间.
这将是O(k)enqueue和get count两者,其中k是在任何时间段内发生的最大请求数t,其中t是任意两个请求之间的最大持续时间(例如,如果我们在接下来的毫秒内获得请求:1,2,3,5,15,20,最大持续时间是20-15 = 5,以5毫秒为单位发出的最大请求数4(即1,2,3,5发生在该时间段内1-5)).
另一种方法是运行一个定时器,使旧条目出列.
这种性能将O(1)用于入队和O(m)定时器运行并获得计数,其中m长度等于定时器频率的任何长度的最大请求数.例如,1,2,3,5,15,20再次使用,计时器间隔为6毫秒.以6毫秒为单位的最大请求数将是4(即1,2,3,5在该时段中发生1-6).
这是"大数据"吗？
那么,这实际上取决于您每秒获得的请求数量.我们通常会谈论大数据的许多数据(并随着计算机变得更强大而增加),我不认为只有最后一分钟的请求会接近这些数字.
基于计数的方法
如果您对一个小错误感到满意,可以执行以下操作:
有一个固定大小的队列(假设60,每个元素指示给定秒的请求 - 是一个简单的整数值).这可以实现为圆形阵列.
令count=一个变量,指示最后一秒的请求数,初始化为0.
有一个变量存储最后一个请求的第二个值(以便能够确定队列中的一个元素用于哪个秒).
当我们得到一个新的请求时,将所有指示秒超过一分钟的元素出列,count按出队的值递减,然后递增队列的后面(最后插入的值)count.
当我们需要获取最后一秒的请求数时,将表示秒超过一分钟的所有元素count出列,按出列值递减,然后返回count.
鉴于我们的队列是固定大小的,每个操作最多需要O(1)(或者,如果你愿意,队列的大小O(m)在哪里m).
这将给你一个最多1秒的错误.你当然可以玩弄错误.例如,如果您想要一个半秒的错误,只需将队列的大小加倍,然后每半秒转到下一个元素.