java - 是否有一个好的算法来检查指定时间段内的数据变化？

Question

我们有大约 7,000 种金融产品，理论上它们的收盘价应该在规定的时间段内（比如一周或一个月的时间段）内在一定的百分比范围内上下波动。

我可以访问存储这些历史价格的内部系统（不是关系数据库！）。我想制作一份报告，列出在此期间价格完全没有变动或低于 10% 的任何产品。

我不能只将第一个值（第 1 天）与结束时的值（第 n 天）进行比较，因为价格可能会回到最后一天的水平，这会导致产品价格出现误报当然，可能会在两者之间的某个地方飙升。

是否有任何已建立的算法可以在合理的计算时间内做到这一点？

Answer 1

如果不查看每一天，就没有任何方法可以做到这一点。

假设数据如下所示：

oooo0oooo

中间有一天的飙升。除非您检查峰值发生的那一天，否则您不会捕捉到这一点 - 换句话说，您需要每天检查。

Answer 2

如果这需要经常检查（对于大量的时间间隔，如去年的每天，以及同一组产品），您可以存储每周/每月每个项目的高值和低值。通过将正确的每周和/或每月界限与区间边缘的一些原始数据相结合，您可以获得区间内的最小值和最大值。

Answer 3

如果您可以将数据添加到 kdb（即您不限于读取访问权限），您可能会考虑将“自上次价格变化以来的天数”添加为一组新数据（即每个金融工具一个数字）。然后，每日任务将获取今天的标记和昨天的标记，并更新存储的数字。同样，您可以在 kdb 中维持最近（上个月、去年）的高点和低点。您必须在较大的数据集上运行一项作业来初始值，但随后您的每日更新将涉及更少的数据。

建议如果您采用这样的方法，您可以通过某种方式重新运行全部或部分数据集（例如添加新产品）。

最后 - 历史是否根据当前价格标准化？（即是否考虑了股票拆分或类似情况的重估）。如果没有，您需要检测这些不连续性并将它们分开。

编辑

我会研究使用kdb+/Q来实现信号处理，而不是将原始数据提取到 Java 应用程序中。正如你所说，它是高性能的。

Answer 4

如果您可以在时间间隔内跟踪价格的最小值和最大值，则可以执行此操作 - 这假设时间间隔没有不断变化。跟踪更改的一组项目的最小值和最大值的一种方法是“背靠背”放置两个堆 - 您可以将这个和一些必要的指针存储在商店中的一个或两个数组中查找和删除旧项目. 将两个堆背靠背放置的想法在 Knuth 的计算机编程艺术第 3 卷中，作为练习 31 第 5.2.3 节。Knuth 称这种野兽为 Priority Dequeue，这似乎是可搜索的。最小值和最大值可按固定成本获得。当新价格到达时修改它的成本是 log n，其中 n 是存储的项目数。