时间戳

首页 > 解决方案 > Incremental price graph approximation

algorithm - Incremental price graph approximation

问题描述

I need to display a crypto currency price graph based similar to what is done on CoinMarketCap: https://coinmarketcap.com/currencies/bitcoin/

There could be gigabytes of data for one currency pair over a long period of time, so sending all the data to the client is not an option. After doing some research I ended up using a Douglas-Peucker Line Approximation Algorithm: https://www.codeproject.com/Articles/18936/A-C-Implementation-of-Douglas-Peucker-Line-Appro It allows to reduce the amount of dots that is sent to the client but there's one problem: every time there's new data I have to go through all the data on the server and as I'd like to update data on the client in real time, it takes a lot of resources.

So I'm thinking about a some kind of progressive algorithm where, let's say, if I need to display data for the last month I can split data into 5 minute intervals, preprocess only the last interval and when it's completed, remove the first one. I'm debating either customising the Douglas-Peucker algorithm (but I'm not sure if it fits this scenario) or finding an algorithm designed for this purpose (any hint would be highly appreciated)

标签： algorithmgraph

解决方案

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

  • 这就是我的处理方式：

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

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

推荐阅读