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

люди разучились писать код чтоли? Скоро либы для хелловорлда просить будут

берешь значит редис. складываешь туда записи. 15млн он переварит без проблем. Ключ == время. И тащи что тебе надо. Можешь сделать расчет вообще не стороне редиса, тогда будет еще шустрей.

> берешь значит редис

Ггг

Мне ключ == время не катит, как тогда интерполировать?

Ок. Берешь значит С++ и людую реализация хэша %)

Похоже, тебе нужен RRDtool

Это ты так пошутил сейчас?

Нет, не пошутил. Есть у меня 2 значения, записанные для 11:00:00 и для 11:00:05. Нужно получить значение для 11:00:02. Как тут поможет хэш?

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

Похоже на то. А в виде библиотеки для C/C++ есть?

А как интерполируют вообще?... Берут 2 соседних значения. в 11:00:05 и в 11:00:00 и интерполируют (в данном случае линейно). Осталось придумать более-менее быстрый способ находить 2 соседних ключа. Можно тупо-перебором, если интервалы небольшие. Не вижу в чём проблема. В качестве контейнера взять к примеру это http://goog-sparsehash.sourceforge.net

В дистрибутивах есть пакет даже соответствующий.

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

Бинарный поиск же

> Можно тупо-перебором, если интервалы небольшие.

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

Тогда да, с бинарным поиском вполне можно использовать тот же QMap. Но это лишь одно из возможных шагов к ускорению нужного мне процесса. Можно разбивать всё на некоторое подобие b-trees, можно длинные места, где функция апроксимируема, заменять на формулы и т.п. Поэтому я и хочу готовую либу, самому всё это делать долго.

Грёбанный Кебастос! Ведь есть iterator QMap::lowerBound(const Key &key). И не надо заботиться о реализации поиска.

Остаётся вопрос рассчёта среднего значения. Есть миллион int'ов, как для них посчитать среднее?

> Есть миллион int'ов, как для них посчитать среднее?

суммируешь и делишь на их количество…

> суммируешь и делишь на их количество…

… и получаешь переполнение.

> … и получаешь переполнение.

не получишь, если выберешь подходящий тип.

… и получаешь переполнение.

Суммируй в больший по размеру тип.

Да, точно. В моей системе INT_MAX/LLONG_MAX=4294967298, так что миллион int'ов влезет в long long.

Нет, ну там перебор небольшой. Вы похоже не поняли о чём я.
У вас есть записи
11:00:00
11:00:05
11:00:10

Вы хотите получить значение в 11:00:07.
В итоге нужно сделать 3 операции поиска, для того чтобы найти последующее значение и 2 - предыдущее.
Т.е. вы проверяете на наличие в хэш таблице ключи: 11:00:08, 11:00:09, 11:00:10
И соответственно вниз. Если вы уверены, что записи идут с точностью раз в 5 секунд, то тогда можно просто как-нибудь так: startTime + 5 * floor(curKey / 5)
startTime - время первой записи(первый ключ)...

Почему бы не выбрать double? Всё-таки размерность удобна + сохраняется точность. Приведения вроде как в обоих случаях будут?

Достаточно сделать одну операцию поиска с помощью lowerBound, а следующее значение будет следующим итератором.

Достаточно сделать одну операцию поиска с помощью lowerBound

У тебя же данные упорядочены по времени с равномерным шагом, мочему напрямую индекс не вычислять?

потому что как выяснилось, нифига не равномерно

… и получаешь переполнение.

Считать среднее инкрементально.

> Считать среднее инкрементально.

посчитай инкрементально среднее ряда 1..10 ;)

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

1/10 + 2/10 + … + 10/10 = 5

> 1/10 + 2/10 + … + 10/10 = 5

1/10 + 2/10 + … + 10/10 = 1.

Не понял, где подвох.

avg1 = 1

avg2 = (avg1*1 + 2)/2 = 1.5

avg3 = (avg2*2 + 3)/3 = 2

…

Но видать, где-то есть, просвети, будь добр.

> 1/10 + 2/10 + … + 10/10 = 5

1/10 + 2/10 + ... + 10/10 = 5.5 ...

Ты int'ами оперируешь что ли? Если нет, то ты неправильно посчитал.

Упс. Но это верно.

целочисленная же арифметика

тип данных в студию

> 1.5

int? o_O

> Ты int'ами оперируешь что ли?

конечно, ведь это продолжение разговора о том, что у тебя при суммировании int переполнится.

Задача ставилась как.

Есть миллион int'ов, как для них посчитать среднее?

В упор не вижу при чем здесь

целочисленная же арифметика

int? o_O

Где требование, что результат среднего должен быть интом?

Для быстрого подсчёта суммы на интервале нужно дерево отрезков. Из суммы на интервале легко найти среднее на интервале.

> Где требование, что результат среднего должен быть интом?

ты писал этот пост не приходя в сознание?

ты писал этот пост не приходя в сознание?

У меня час ночи уже, а тред про недобуки разъел остатки серого вещества. Поэтому не смотри свысока на убогого. Если не сложно, просто разверни мысль. Я тебя тупо не понимаю.

> Если не сложно, просто разверни мысль. Я тебя тупо не понимаю.

я вот тебя тоже не понимаю. ТС в процитированном тобой посте жалуется, что у него при суммировании 1млн интов пойдёт переполнение. когда может случится переполнение? правильно, если суммировать в тот же инт; double с его максимумом 10^308 и миллиардом интов не переполнишь. но если использовать для аккумулятора double, то на кой фиг вообще считать среднее инкрементально?

учи мат. часть.

Для полутора миллионов значений редис?
Ха-ха-ха...
SQLite хватит с избытком.

и сколько стоит доступ к ключу по айдишнику?

*записи по айдишнику. В редисе быстрей.

Эээ... поясните пожалуйста, редис это однолетние или двулетние растения из рода Редька семейства Капустные или что?

http://redis.io/

но если использовать для аккумулятора double, то на кой фиг вообще считать среднее инкрементально?

Резонно, но тогда уж лучше взять long long, в double мантисса всего 52 бита.

Посмотри в mrtg либу для хранения данных (не помню название, но разбирался в ней в свое время).

Она позволяет сохранять не все данные, а с уменьшающимся временным разрешением.

Не знаю, это ли именно тебе нужно, но советую.