在cs.stackexchange上问这个..得到了一个downvote ..因为我不是很清楚..所以我会尝试在这里更具体..
问：设计一个数据结构,以便在最后1分钟内返回到Web服务器的连接数.
假设 –
>服务器的连接数量很大..就像印度人一样
铁路预订或社交网站等.
>假设这是一个大数据问题..然后我有infra运行大数据工作..
我在寻找：
>效率 – 是否可以在O(1)中执行此操作？例如,如果我们在O(n)中这样做..问题是如果计算答案需要N毫秒……还有一些连接已经在N ms中排队.我应该如何解决这个问题.或者我只能忽略小延迟而O(n)是一个好的表现
>推理/方法 – 我们在生产中进行的无数次部署中,我们是否会做类似的事情？有类似的问题..？
>这是“大数据”吗？用于存储连接的数据是否是大数据问题的最后N(N是10阶)分钟？
我的努力：
我知道 –
>在通过线程提供服务之前,与Web服务器的连接将被放入队列中
>每个连接都有一个时间戳
方法 –
>只要在队列中放入连接,就将其写入文件..(至少它的时间戳和连接的句柄/唯一标识符)
>一旦客户端请求“在最后1分钟给我num连接”..处理文件以找出连接数…我们知道以毫秒为单位的当前时间,我们必须找到当前时间的当前时间戳连接 – 60秒
>这个作业可以使用map reduce运行..我也知道文件已经排序了数据(按时间戳).
解决方法
>使用队列.
>每当有新请求出现时,请将其排队.
>每当我们需要在最后一分钟获取请求数时,首先将所有发生的条目出列的时间超过一分钟(这是有效的,因为队列中的条目按顺序插入,因此队列已排序).然后返回队列的大小(通过使用存储该变量的变量,可以在O(1)中返回大小).
>由于您说每秒有大量请求,因此每当您收到新请求时,您也可以将旧条目出列,这样可以使队列保持接近正确的大小,从而最大限度地减少计数操作所需的时间.
对于enqueue和get count,这将是O(k),其中k是在任何长度为t的时间段内发生的最大请求数,其中t是任意两个请求之间的最大持续时间(例如,如果我们得到请求在以下毫秒：1,2,3,5,15,20,最大持续时间为20-15 = 5,并且在5毫秒内发生的最大请求数为4(即1,5发生在1-5))).
>另一种方法是运行一个计时器,使旧条目出列.
对于计时器运行和获取计数,其性能为入队的O(1)和计数的O(m),其中m是任何长度等于计时器频率的最大请求数.例如,再次使用1,定时器间隔为6毫秒.在6毫秒内发生的最大请求数将是4(即1,5发生在1-6期间).
Is this “Big data”?
那么,这实际上取决于您每秒获得的请求数.我们通常会谈论大数据的许多数据(并随着计算机变得更强大而增加),我不认为只有最后一分钟的请求才能接近这些数字.
基于计数的方法
如果您对一个小错误感到满意,可以执行以下操作：
有一个固定大小的队列(假设60,每个元素指示给定秒的请求 – 是一个简单的整数值).这可以实现为圆形阵列.
令count =一个变量,表示最后一秒的请求数,初始化为0.
有一个变量存储最后一个请求的第二个值(以便能够确定队列中的一个元素用于哪个秒).
当我们得到一个新请求时,将所有指示秒超过一分钟的元素出列,将计数递减出队列值,并递增队列的后面(最后插入的值)和count.
当我们需要获取最后一秒的请求数时,将计数减去出队值,并返回计数.
假设我们的队列是固定大小的,每个操作最多需要O(1)(或者,如果你愿意的话,O(m),其中m是队列的大小).
这将给你一个最多1秒的错误.你当然可以玩弄错误.例如,如果您想要一个半秒的错误,只需将队列的大小加倍,然后每半秒转到下一个元素.
