2

I have a list of clients say (A,B,C,D) that have their own time periods/windows. I set a timer internally based on the next window expiry... from among (A,B,C,D)'s window sizes..

For example:

Client Window Size
A      10
B      15
C      20
D      50

So timer expiry is going to be: 10,15,20,30,40,45,50 ...

What's the best way to do this? Choosing C as our language to implement. Client Periods are stored in a statically allocated array (we know the size)

4

2 回答 2

1

最好的方法是优先级（最小）堆，优先级基于过期时间。

每次窗口过期时，在 O(1) 时间内从堆中删除最小项，并在过期时间加上窗口大小在 O(log(N)) 时间内重新插入。所需空间为 O(N)。

为了代表当前时间，有（至少）两种选择。

1) 使用一个宽值（比如 64 位）来处理太阳熄灭之前的时间

2）使用模运算；这需要仔细的比较运算符

对于模数方法，时间值必须至少与最大窗口大小一样大，加上定时器到期延迟的小余量。使用无符号算术。堆中的值应该是插入条目的时间。每个条目的剩余时间为

window - (now - inserted)

请注意，(now - inserted)它始终是正数，因为它衡量了条目在堆中的时间——如果差异“包装”为零，则无符号结果将是正确的；window也是积极的。如果我们有两个条目x，y我们想看看

(x.window - (now - x.inserted)) > (y.window - (now - y.inserted))

我们可以使用无符号算术来做到这一点

(x.window + (now - y.inserted)) > (y.window + (now - x.inserted))

这是我们用来比较堆条目的比较运算符。

于 2013-04-26T23:38:20.490 回答
0

取决于您添加客户端的频率以及窗口大小有多大我会考虑使用这种方法：

  1. 将 m 定义为最大窗口大小：m = max(Window Size)。

  2. 然后你可以分配布尔数组：bool Alarms[m]。

  3. 对于每个客户端集：范围内的Alamrs[k*windowsize]=true位置k<1, m/windowsize>

    • 在您的示例中，警报将如下所示： 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 ... Alarms[10]=true; 警报[15]=真；警报[20]=真；警报[30]=真；等等

警报的每个滴答声都会检查Alarms[tick % m]其值。当您阅读真正的警报时，应该响起。读取状态为 O(1)。

当窗口大小相似并且您不经常添加具有较高窗口大小的客户端时，这种方法很好。

  • 添加 Window Size > m 的客户端时，您必须重新分配整个数组，这可能很昂贵。

  • 当客户端窗口之间有大空间时 - 例如 A=1 和 B=30000 您将需要 29998 个空单元格。

于 2013-04-26T23:28:50.323 回答