Sza*_*lcs 3 c++ algorithm simulation performance data-structures
我没有正式的CS培训,所以请耐心等待.
我需要做一个模拟,可以抽象到以下(省略细节):
我们有一个代表事件发生时间的实数列表.在每一步中,我们
- 删除第一个事件,和
- 作为"处理"它的结果,一些其他事件可能会在严格的后期插入到列表中
并重复多次.
问题
我可以使用哪种数据结构/算法来尽可能高效地实现它？我需要显着增加列表中的事件/数字的数量.优先考虑的是尽可能快地列出长列表.
因为我在C++中这样做,STL或boost中已经有哪些数据结构可以使它实现起来变得简单？
更多细节:
列表中的事件数量是可变的,但它保证在某个模拟参数之间n和之间.虽然事件时间在增加,但最新和最早事件的时差也保证小于常数.最后,我怀疑时间事件的密度虽然不是常数,但也有上限和下限(即所有事件永远不会强烈聚集在一个时间点附近)2*nnT
到目前为止的努力:
正如问题的标题所说,我正在考虑使用排序的数字列表.如果我使用链表进行恒定时间插入,那么我很难找到以快速(次线性)方式插入新事件的位置.
现在我正在使用近似值,我将时间划分为桶,并跟踪每个桶中有多少事件.然后随着时间的推移逐个处理铲斗,当从前面移除一个铲斗时,总是在末端添加一个新铲斗,从而保持铲斗的数量不变.这很快,但只是近似值.
| 归档时间： |
|
| 查看次数： |
2915 次 |
| 最近记录： |