Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > С/С++: Кроссплатформенное программирование, Qt/Gtk+/wxWidgets > Построение графика по большому объему данных

Автор: math64 14.4.2015, 12:56

Есть большой файл (около 6Gb) с парами (X,Y). X изменяется монотонно, но не равномерно.
Нужно иметь возможность построить график, иметь возможность выделить кусок (Xmin, Xmax) и рассмотреть его детально.
Используется Qt, как делать если все данные помещаются в ОЗУ знаю.

Автор: Amp 14.4.2015, 13:27

Читать данные, сэмплировать/агрегировать в соответствии с какой-нибудь логикой, чтобы на выходе получить всего несколько тысяч отсчетов. Для зума либо пересчитывать все в реальном времени (если будет отнимать разумное время), либо заранее просчитывать с десяток разных уровней детализации (ориентируясь на объем ОЗУ) и в соответствии с уровнем зума выбирать какой из них отображать. Полученные данные уже отправлять на отрисовку.

Автор: borisbn 14.4.2015, 14:05

Я бы ещё перегнал бы этот файл в БД (sqlite, например) и добавил бы индекс по X.

Автор: math64 14.4.2015, 15:16

Цитата(borisbn @ 14.4.2015, 14:05

)

Я бы ещё перегнал бы этот файл в БД (sqlite, например) и добавил бы индекс по X.

Была такая идея. Но насколько это ускорит?
Как будет выглятеть запрос данных с нужным шагом по X?
PS: попросили визуализировать процесс считывания. Оказалось при замене

Код


for(int i = 0; i < recCnt; i++) {
    file.seek(..,);
    file.read(...);
}
emit dataChanged(createIndex(0, 0), createIndex(recCnt - 1, colCnt - 1));

на

Код


connect(this, SIGNAL(readData(int)), this, SLOT(onReadData(int)), Qt::QueuedConnection);

emit readData(0);

void DataModel::onReadData(int i0)
{
    int i = i0, n = i0 + 1000;
    for(; i < recCnt && i < n; i++) {
        file.seek(...);
        file.read(...);
    }
    emit dataChanged(createIndex(i0, 0), createIndex(i - 1, colCnt - 1));
    if (i < recCnt)
        emit readData(i);
    else
        file.close();
}

по крайней мере, визуально, времени затрачивается меньше.

Автор: math64 21.4.2015, 12:51

Попробовал через sqlite. Объём базы данных - 13G, создаётся долго (использется транзакция - без неё будет ещё дольше).
Запрос на выборку данных

Код


select round(x*10) as n, x, max(y) as max, min(y)  as min, count(*) as count from data group by n

тоже выполняется слишком долго, быстрее выбрать данные из исходного файла.

Автор: tzirechnoy 21.4.2015, 12:52

Цитата

Я бы ещё перегнал бы этот файл в БД (sqlite, например) и добавил бы индекс по X.

Зачем?

Автор: math64 27.4.2015, 11:36

Отбираю отсчёты, комбинируя алгоритмы бинарного поиска и быстрой сортировки:

Код


void DataModel::find(int min, int max)
{
  if (max <= min + 1)
    return;
  int mid = (max+min)/2;
  file.seek(...);
  file.read(...);
  mid = ...; // пересчет mid в соответствии x прочитанной записи
  find(min, mid);
  find(mid, max);
}

укладываюсь в 1 секунду, но если в графике есть высокочастотные изменения, он не соответствует эталонному.

Отбор точек путем последовательного просмотра всего файла занимает около 2 минут.
PS: не в 1 секунду. В первый раз около 70 секунд. Потом файл оказывается в каком-то системном кеше и повторный поиск занимает примерно 0.5 секунды.

Автор: Alexeis 29.4.2015, 22:10

Цитата(math64 @ 14.4.2015, 13:56

)

Есть большой файл (около 6Gb) с парами (X,Y). X изменяется монотонно, но не равномерно.

Монотонно возрастает или убывает на всем промежутке? Если так, то можно разбить весь файл на количество интервалов равное числу пикселей графика. На каждом интервале достаточно исследовать первую и последнюю точку. Такой график посчитается за милисекунду. А зум нужно формировать обходя файл и разбивая заново на интервалы.

Автор: math64 30.4.2015, 08:13

После того, как точки отобраны - да, график рисуется за несколько миллсекунд.
Но отбор точек происходит медленно.
Степень неравномерности можно увидеть по прилагемому графику 3a.png
1a.png - неравномерность отбора точек при последовательном просмотре графика (около 2 минут), ошибка +/- 0.5 пискеля
2a.png - неравномерность отбора точек при бинарном поиске - 70 секунд первый раз, 0.5 секунды при повторе.

Добавлено через 10 минут и 8 секунд
Использование file.map() вместо file.seek() и file.read() только замедляет дело.

Автор: math64 25.6.2015, 10:30

Собираюсь сделать так:
При открытии файла отбираются опорные точки, по которым строится график.
При зуме сразу строится пиближённый график по опорным точкам и начинаются считываться промежуточные. По мере считывания график перерисовывается.
При повторном зуме старое считывание промежуточных точек нужно остановить и начать новое (но некоторые считанные промежуточные точки можно оставить).
Детали реализации пока не продуманы.