是否有一个好的算法来检查在一段特定时期内的数据变化？

Question

我们有大约7K的金融产品，其收盘价理论上应该上下移动一定的比例范围内，整个定义的时间段（比如一周或一个月期间）。

我可以访问内部系统，用于存储这些历史价格（而不是关系数据库！）。我想产生一个报告，列出其价格在所有或小于发言权的时间10％没有移动的任何产品。

我不能只在最后（n天）比较的第一个值（1天）的值作为价格可能已经搬回这是什么的最后一天，这将导致假阳性，而该产品的价格可能在过程中的加标之间的某处。

是否有任何既定的算法来做到这一点在合理的计算时间？

Answer 1

如果要经常检查这需要（大量时间间隔，如每天的最后一年，而同组的产品），您可以存储每周/每月每个项目的高值和低值。通过在区间的边缘右侧每周和/或每月的界限与一些原始数据结合，你可以得到在区间的最小值和最大值。

Answer 2

有没有任何办法做到这一点不看的每一天。

假设数据看起来像这样：

oooo0oooo

通过在中间的那个单日尖峰。你不会抓，除非你检查的日子，穗发生 - 换句话说，你需要检查每一天。

Answer 3

如果您可以将数据添加到KDB（即您不限于读存取）你可能会考虑加入“天数从去年的价格变化”作为一个新的数据集（每个金融工具即一个号码）。然后每天的任务就是获取今天的标记和昨天的，并且更新存储的数字。同样，你可以保持最近（上月，去年）在KDB高点和低点。你得值最初运行在更大的数据集主要工作，但那么你的日常更新将涉及更少的数据。

建议如果采用这样你有办法重新运行数据集的全部或部分的东西（比如添加新产品）。

最后 - 被历史归反对目前的价格？ （即是股票分割或考虑重估相似）。如果没有，你需要检测这些不连续性和分裂出来。

修改的

我调查USNG KDB + / Q 以执行信号处理，而比提取原始数据的Java应用程序。正如你所说，这是非常高性能的。

Answer 4

您可以做到这一点，如果你能在时间间隔内跟踪分钟和价格的最大价值 - 这是假定的时间间隔不被不断地变化。保持设定项目的改变的最小值和最大值的轨迹的方法之一是放置“背靠背”两个堆 - 你可以存储这个和必要的一些指针找到并在您的商店中删除一个或两个数组老项目。把两个堆背靠背的想法是在计算机的Knuth的程序设计艺术第3卷作为练习31第5.2.3节。高德纳称这种野兽的优先出队，这似乎是搜索。最小和最大可在成本不变。当一个新的价格到达修改它的成本是log n，其中n是存储的项目的数目。