VPF::Построение графика по большому объему данных

math64

Дата 14.4.2015, 12:56 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 23
Всего: 72

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

Amp

Дата 14.4.2015, 13:27 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 886
Регистрация: 17.2.2009

Репутация: 7
Всего: 17

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

Это сообщение отредактировал(а) Amp - 14.4.2015, 13:32

borisbn

Дата 14.4.2015, 14:05 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 48
Всего: 135

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

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

math64

Дата 14.4.2015, 15:16 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 23
Всего: 72

Цитата(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 - 23.4.2015, 09:25

math64

Дата 21.4.2015, 12:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 23
Всего: 72

Попробовал через 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

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

Это сообщение отредактировал(а) math64 - 21.4.2015, 12:52

tzirechnoy

Дата 21.4.2015, 12:52 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1173
Регистрация: 30.1.2009

Репутация: 1
Всего: 16

Цитата

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

Зачем?

math64

Дата 27.4.2015, 11:36 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 23
Всего: 72

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

Код


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 секунды.

Это сообщение отредактировал(а) math64 - 28.4.2015, 09:03

Alexeis

Дата 29.4.2015, 22:10 (ссылка)

(нет голосов)

Загрузка ...

Амеба

Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 1
Всего: 459

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

)

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

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

--------------------

Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать

math64

Дата 30.4.2015, 08:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 23
Всего: 72

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

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

Присоединённый файл ( Кол-во скачиваний: 4 )

screens.zip 90,69 Kb

math64

Дата 25.6.2015, 10:30 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 23
Всего: 72

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| С/С++: Кроссплатформенное программирование, Qt/Gtk+/wxWidgets \| Следующая тема »