我需要显示一个类似于CoinMarketCap所做的加密货币价格图表:https://coinmarketcap.com/currencies/bitcoin/
在很长一段时间内,一个货币对可能有数千兆字节的数据,因此不能选择将所有数据发送到客户端.在做了一些研究后,我最终使用道格拉斯 - 佩克尔线近似算法:https://www.codeproject.com/Articles/18936/AC-Implementation-of-Douglas-Peucker-Line-Appro它允许减少发送到客户端的点但有一个问题:每次有新数据我都必须通过服务器上的所有数据,因为我想实时更新客户端上的数据,需要大量资源.
所以我正在考虑一种渐进式算法,比方说,如果我需要显示上个月的数据,我可以将数据分成5分钟的间隔,只预处理最后一个间隔,当它完成时,删除第一个.我正在讨论自定义Douglas-Peucker算法(但我不确定它是否适合这种情况)或者找到为此目的而设计的算法(任何提示都会受到高度赞赏)
当新数据到达时,不断重新计算整个缩减点将不断改变您的图形.该图表缺乏一致性.一个用户看到的图表与另一个用户看到的图表不同,当用户刷新页面时图表会发生变化(这不应该发生!),即使在服务器/应用程序关闭的情况下,您的数据也需要与之前的情况保持一致.
你的减少积分应该是原样.假设您正在获取每秒数据,并且您已经计算了5分钟间隔图的减少点,将这些数据点保存在限制队列中.现在收集接下来5分钟的所有秒数据,并对这600个数据点执行还原操作,并将最终的减少点添加到限制队列中.
我会使Queue同步,并且只要有API调用,主线程就会返回队列中的数据点.一旦整个5分钟间隔的数据可用,工作线程就会计算5分钟数据的缩减点.
我会用树。
子节点包含“精度”和“平均值”值。
“精度”是指日期范围。例如：1 分钟、10 分钟、1 天、1 个月等。这也表示树中的级别。
“平均”是最能代表某个范围价格的值。您可以使用简单平均值、线性回归或任何您认为“最佳”的方法。
因此，如果您需要 600 点（假设您获得了窗口大小），您可以通过 找到精度 prec=total_date_range/600，并对现有范围进行一些舍入。
现在您已经有了“prec”，您只需检索该“prec”级别的节点即可。
作为千兆字节的数据，我将它们分割成 std::vector 对象。树会将最低节点的 id 存储到这些向量中。其余节点也可以通过向量索引来实现。
更新新数据只需要更新一个分支（甚至创建一个新分支），从根开始，但没有那么多子节点。