Приближение графа инкрементной цены

Question

Мне нужно отобразить график цен криптовалюты, основанный на том, что сделано на CoinMarketCap: https://coinmarketcap.com/currencies/bitcoin/

Могут быть гигабайты данных для одной валютной пары в течение длительного периода времени, поэтому отправка всехданные для клиента не вариант.После некоторых исследований я использовал алгоритм аппроксимации линии Дугласа-Пекера: https://www.codeproject.com/Articles/18936/A-C-Implementation-of-Douglas-Peucker-Line-Appro Это позволяет уменьшить количество точек, отправляемых клиенту, но есть одна проблема: каждый раз, когда появляются новые данные, я должен идтичерез все данные на сервере, и, поскольку я хотел бы обновлять данные на клиенте в режиме реального времени, это требует много ресурсов.

Так что я думаю о некоем прогрессивном алгоритме, гдескажем, если мне нужно отобразить данные за последний месяц, я могу разбить данные на 5-минутные интервалы, предварительно обработав только последний интервал, а когда он будет завершен, удалить первый.Я обсуждаю либо настройку алгоритма Дугласа-Пекера (но я не уверен, подходит ли он этому сценарию), либо нахождение алгоритма, разработанного для этой цели (любая подсказка будет высоко оценена)

Answer 1

Постоянное пересчет всех точек сокращения при поступлении новых данных будет постоянно изменять ваш график.График не будет иметь согласованности.График, видимый одним пользователем, будет отличаться от графика, видимого другим пользователем, и график будет меняться, когда пользователь обновляет страницу (этого не должно происходить!), И даже в случае закрытия сервера / приложения ваши данные должныбудьте последовательны с тем, что было раньше.

• Вот как я бы подошел:

Ваши уменьшенные очки должны быть такими, какие они есть.Предположим, вы получаете данные каждую секунду и вычислили уменьшенные точки для графика с 5-минутным интервалом, сохраните эти точки данных в ограничивающей очереди.Теперь соберите данные всех секунд за следующие 5 минут и выполните операцию сокращения для этих 600 точек данных и добавьте окончательную уменьшенную точку к вашей очереди ограничения.

Я бы сделал Очередь синхронной, и основной поток вернул быточки данных в очереди всякий раз, когда происходит вызов API.И рабочий поток вычислит точку сокращения для 5-минутных данных, как только станут доступны данные за весь 5-минутный интервал.

Answer 2

Я бы использовал дерево.

Подузел содержит значения «точность» и «среднее».

«точность» означает диапазон дат.Например: 1 минута, 10 минут, 1 день, 1 месяц и т. Д. Это также означает уровень в дереве.

«среднее» - это значение, которое наилучшим образом представляет цену для диапазона.Вы можете использовать простое среднее, линейную регрессию или все, что вы считаете «лучшим».

Так что, если вам нужно 600 баллов (скажем, вы получите размер окна), вы можете найти точность на prec=total_date_range/600и некоторое округление к существующим диапазонам.

Теперь у вас есть «предварительная» информация, необходимая для извлечения узлов для этого «предварительного» уровня.

Будучи гигабайтами данных, я бынарезать их на объекты std :: vector.Дерево будет хранить идентификаторы для этих векторов для самых низких узлов.Остальные узлы также могут быть реализованы с помощью индексов для векторов.

Обновление с использованием новых данных требует только обновления ветви (или даже создания новой), начиная с корня, но не с таким количеством подузлов.