增量价格图近似

Question

我需要显示一个类似于在CoinMarketCap上所做的那样的加密货币价格图表：https://coinmarketcap.com/currencies/bitcoin/

一个货币对在很长一段时间内可能有千兆字节的数据，因此不能将所有数据发送到客户端。在做了一些研究后，我最终使用了道格拉斯-普克线近似算法：https://www.codeproject.com/Articles/18936/A-C-Implementation-of-Douglas-Peucker-Line-Appro它允许减少发送到客户端的点数，但有一个问题:每次有新数据时，我必须检查服务器上的所有数据，因为我希望实时更新客户端上的数据，这需要占用大量资源。

所以我在考虑一种渐进式算法，假设我需要显示上个月的数据，我可以将数据分成5分钟的间隔，只预处理最后一个间隔，当它完成时，删除第一个间隔。我正在讨论定制Douglas-Peucker算法(但我不确定它是否适合这个场景)，或者寻找一个为此目的而设计的算法(任何提示都将不胜感激)。

Answer 1

当新数据到达时，不断地重新计算整个缩减点将不断地更改您的图形。图表将缺乏一致性。一个用户看到的图形将与另一个用户看到的图形不同，当用户刷新页面时，图形会发生变化(这不应该发生！)，即使在服务器/应用程序关闭的情况下，您的数据也需要与以前一致。

• 这就是我的方法：

你的减分应该是原样的。假设您正在获取每秒的数据，并且您已经计算了5分钟间隔图的简化点，请将这些数据点保存在限制队列中。现在收集接下来5分钟的所有秒数据，对这600个数据点执行缩减操作，并将最终缩减的点添加到您的限制队列中。

我会使队列同步，只要有API调用，主线程就会返回队列中的数据点。一旦整个5分钟间隔的数据可用，工作线程将计算5分钟数据的减少点。

Answer 2

我会用树。

子节点包含“精度”和“平均值”值。

“精度”是指日期范围。例如:1分钟、10分钟、1天、1个月等。这也意味着树中的一个级别。

"average“是最能代表一个范围内价格的值。你可以使用简单的平均值，线性回归，或任何你认为是“最好的”。

因此，如果你需要600点(假设你得到了窗口大小)，你可以通过prec=total_date_range/600找到精度，并对现有的范围进行一些舍入。

现在您有了“prec”，您只需要检索该“proc`”级别的节点。

由于有千兆字节的数据，我会将它们分成std::vector对象。该树将存储最低节点的这些向量的ids。其余的节点也可以通过向量的索引来实现。

使用新数据更新只需要更新一个分支(甚至创建一个新分支)，从根开始，但子节点不是很多。