用于处理未来事件的查找结构（基于时间） [英] Lookup structure for handling future events (time based)
问题描述
我正在寻找一个有效的数据结构，这将允许我提示事件，也就是说，我将有一个应用程序，在任何时候执行，可能会提出一个事件对于未来的执行点......如下所示：
- t = 20：在420秒内，A发生
- t = 25：在13秒钟内，B发生
- t = 27：在735秒内，C发生
- ...
所以我想要一个数据结构，我可以在任何时候在任何时候在将来和哪里可以得到和（通过这样做）删除所有应有的事件...也，一个加号将是，如果我能够从数据结构中删除一个事件（因为它被取消）...不是太重要，因为我可以简单地将其标记为已取消...
我的第一个想法是，可能要做某种树，但我猜，删除应有的事件部分需要很多重新平衡...
我正在考虑只需要一个int哈希，映射时间戳为在这个时间点发生的空值或堆栈事件...我认为在场景中，有很多事件（可能是每秒几次 - 这是我打算使用的），这实际上是'毕竟这样一个坏主意...
所以我很想听到你的意见...：）
编辑：
- 更具体：我认为这里的大约是100K-1M，我想我可能会有1-100个事件/秒...
- 这不是特别重要的...它只是为了说明未来的事件可以随时入队...
谢谢
back2dos
如果您的活动有明确的上限（例如没有事件在将来的2天以后），您可以简单地从开始时间按秒数索引数组。
数组的值是该偏移量的事件列表。
列表或删除非常有效 - 只需在您希望的时间内找到偏移量列出或切断并获取或重新初始化该偏移后由索引指向的数组。
如果您的事件可以无限期延伸到未来，那么您自己的使用从偏移到事件列表的hashmap的想法是最好的一个，有一个扭曲 - 有一个已知的偏移的排序列表（但是你想实现它），这样你将有非常有效的查找（例如你不会必须循环每个关键离子的地图）。
您不需要从已知偏移量列表中删除任何内容，因此无需重新平衡的问题 - 您只需从hashmap指向的数组中删除。 p>
此外，您的问题似乎不清楚是否需要知道t - 事件发生的时间。如果您需要知道，请将其存储为事件的一部分。但事件发生时的引用应该与某些起始点是绝对的（如果它是具有无限范围的hashmap，则可以使用时代秒，如果事件具有我列出的第一个数组解决方案的限制，则应该而是使用从开始范围开始的秒数 - 例如从昨天开始的一天。
I am looking for an efficient data structure, that'll allow me to cue events ... that is, i will be having an app, where at any time in execution, it is possible, that an event will be raised for a future point in execution ... something like:
- t=20: in 420 seconds, A occurs
- t=25: in 13 seconds, B occurs
- t=27: in 735 seconds, C occurs
- ...
so i'd like to have a data structure, where i can put in any event in any time in the future and where i can get and (by doing so) remove all due events ... also, a plus would be, if i were able to remove an event from the datastructure (because it was canceled) ... not too important though, since i can simply flag it as cancelled ...
my first thought was, maybe to do some sort of tree, but i guess the removing-due-events part requires a lot of rebalancing ...
i am considering simply having an int hash, mapping timestamps to either null or stacks of events that are to occur at that point in time ... i think in scenarios, with a lot of events (possibly multiple every second - which is what i intend to work with), this actually isn't such a bad idea after all ...
so i am eager to hear your input ... :)
edit:
- to be more specific: i think n here is at about 100K-1M, and i guess i might be having about 1-100 events/second ...
- the t is of no special importance ... it is only to illustrate that a future event can be "enqueued" at any time ...
thanks
back2dos
If your events have a well defined upper limit (e.g. no events later than 2 days in the future), you can simply have an array indexed by # of seconds from "beginning of time". The value of the array is a list of events at that offset.
Listing or Removal is very efficient - simply find the offset for the time where you wish to list or cut off and get or re-initialize the arrays pointed to by indices after that offset.
If your events can stretch out indefinitely into the future, then your own idea of using a hashmap from offsets to list of events is the best one, with a twist - have a sorted list (however you wish to implement it) of known offsets, that way you will have very efficient lookups (e.g. you won't have to loop over every key ion the map).
You don't need to delete anything from the list of known offsets so no issues with re-balancing - you merely delete from the arrays that hashmap points to.
Also, it seems unclear from your question whether there's any need to know "t" - the time when the event was raised. If you need to know it, store it as part of the event. but the reference to when the event should happen should all be absolute in relation to some starting point (if it's a hashmap with unbounded range, you can use epoch seconds, and if events have bounds like in the first array solution I listed, you should instead use "# of seconds since beginning of range" - e.g. from start of day yesterday.
这篇关于用于处理未来事件的查找结构（基于时间）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
