algorithm - 增量价格图近似

Question

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

一种货币对在很长一段时间内可能有数 GB 的数据，因此将所有数据发送给客户端不是一种选择。在做了一些研究之后，我最终使用了道格拉斯-普克线近似算法: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 分钟数据的减少点。