[C++] [хочу либу] Хранение кучи данных y(x)

> в double мантисса всего 52 бита.

если считать, что инт — 32-битный, то 1млн таких интов дадут сумму, не превышающую 2^20 × 2^31 = 2^51 (знак хранится отдельным битом). кроме того, можно считать, что в дабле 53-битная мантисса, где самый старший «виртуальный» бит всегда равен единице для ненулевых значений. так что ещё и запас есть. но оперировать целыми числами, конечно, предпочтительнее.

Тут вопрос в скорости работы QMap. google_sparse_map /dense_map - очень быстрые, я гарантирую это :) Им несколько миллионов записей нипочём. Так что смотрите сами.

Неужели про косвенную адресацию все забыли?!? Записи с постоянным шагом, время (тип time_t) хранится в double --> напрашивается простейшее решение:

double value(double t, std::vector<double> tdat, std::vector<double> vdat)
{
int n=int((t-tdat[0])/5+0.5); // lower position
if(n>tdat.size()-2 || n<0) return NAN;// out of range
double v1=vdat[n], v2=vdat[n+1];
return v1+(v2-v1)*(t-tdat[0]-5*n)/5;
}

Затраты на поиск точки — 1 операция. Аналогично пишется для среднего арифметического.

Я выше написал, некоторые записи бракованы, то есть иногда шаг скачет.

Читай комменты.

Ну в общем, понятно. Суть всё равно одна, всё это сортированные словари с поиском. Коли понадобится скорость, посмотрю эти либы, но пока, кажется, хватает QMap. Тем паче, задача почти одноразовая.

Спасибо, посмотрю. Хотя уже сделал в лоб на QMap. Но потом пригодится.

Имеется в виду, что иногда шаг кратный 5 сек? Тогда делаем несколько итераций. В худшем случае потребуется log(n-n0) итераций, где n0 — начальное приближение.

Так это очень близко к бинарному поиску тогда.

В худшем варианте — да

Можте быть стоит посмотреть в сторону баз данных?

P.S. Тред не читал.

Тред глянул бегло.

Если шаг фиксирован, хранить все в double/float, битые значения писать как nan. Это гораздо быстрее любого двоичного поиска + можно тупо юзать плоский файл для хранения на диске. То есть это в принципе самая быстрая реализация из возможных (при небольшом кол-ве битых записей)

Хранить в обычном массиве ес-но.

> Посоветуйте, пожалуйста, готовые либы для моих задач.

mysql?

А может дерево?

глубина дерева - уровень детализации 5сек-1мин-1час-1сутки-1мес. Ну что-то в таком духе.

Каждый узел дерева хранить вспомогательную информацию, ну там среднее по всем конечным звеньям (самым нижним), которые относятся в этому звену и их количество.

При добавлении нового элемента в дерево, пересчитывать средние значения во всех узлах выше.

Посчитать среднее арифметическое на любом интервале будет не трудно.

//тред не читал

Для п.2 это то, что придётся как-то обходить переполнение.

А какие могут быть проблемы с переполнением? O_o

Тут уже ведь говорили про растаманский инкрементальный расчет среднего арифметического. Вот формула:

S(n+1)=S(n)*n/(n+1) + V(n+1)/(n+1)

S - среднее значение

V - величина

Правда все операции надо проводить с double. Но я не вижу в этом большого зла.

В чем проблема? Я не понимаю.

Но но на большой выборке малых значений появятся погрешности.

        double summ = 0;
        for(int i = 1; i <= 10; i++)
        {   
            summ += i / 10.0f;                                                                                                                                                    
        }   
        printf("m: %f\n", summ);
 

> Перебором не катит, запись трёх месяцев с интервалом 5 секунд это немало.

Если один datum 4 байта, то 6 метров. Много?

Если один datum 4 байта, то 6 метров. Много?

Смотря для каких целей? Неизвестно, что за безумные задачи надо решать ТС. Может необходимо 100500 раз вызывать подсчет среднего для разных интервалов.

Среднее надо считать для каждого дня.

Среднее надо считать для каждого дня.

O_o Если строго 00:00 до 23:59, то я не вижу проблем. Проходим в лоб по массиву считаем среднее для каждого целого дня и запоминаем позицию где остановились. Потом, когда получим новые данные, продолжим с места последней остановки.

#include <stdio.h>
double diffpct(double x, double y) {
	double diff = x / y;
	if (diff > 1) return 100 * (diff - 1);
	return 100 * (1 - diff);
}
int main() {
	int a[1000000];
	for (int i = 0; i < 1000000; i += 1) a[i] = rand();
	int mid1 = 0;
	for (int i = 0; i < 1000000; i += 1) mid1 += 0.000001 * a[i];
	printf("%d\n", mid1);
	long long mid2 = 0;
	for (int i = 0; i < 1000000; i += 1) mid2 += a[i];
	mid2 /= 1000000;
	printf("%ld\n", mid2);
	double diff = diffpct((double)mid2, (double)mid1);
	printf("%lf %\n", diff);
	return 0;
}

$ ./1
1073255973
1073756018
0.046591 %

Хотя это все равно плохо.

$ time ./1
1073255973
1073756018
0.046591 %

real	0m0.122s
user	0m0.117s
sys	0m0.007s

Для исходника выше. На сраном атоме. Без оптимизаций типа -O2, -O3.

> Без оптимизаций типа -O2, -O3.

К слову, с ними разницы никакой абсолютно.

> с линейной интерполяцией, например

А че так просто-то?

int a[1000000];
int mid1 = 0;
mid1 += 0.000001 * a[i];

Блин, как же эта целочисленная арифметика режет глаза.

При шаге 5 секунд это не важно для измеряемой величины (напряжённости магнитного поля среды). Производная достаточно мала.

> Как я написал выше, некоторые значения бракованные и не добавляются в массив.

Если таких данных не слишком много, можно использовать hunt search, описанный в Numeric Recipes in C, глава How to search an ordered table. Идея в том, чтобы оценить где должна находится нужная точка, в твоём случае это (t-t0) / 5, как уже кто-то писал выше, а затем пройтись по массиву с увеличивающимся шагом в нужном направлении, пока не будут найдены границы, в пределах которых лежит нужное значение. Затем запускается бинарный поиск в этих границах.