Войти
ПрограммированиеФорумОбщее

Упаковка графика функции

Страницы: 1 2 3 4 5 Следующая »
#0
15:08, 20 ноя. 2016

есть набор значений float, это график
есть ли такой алгоритм паковки который мог бы быстро дать ответ какое значение в указанной позиции, не используя O(N) памяти для распаковки


#1
15:46, 20 ноя. 2016

IROV..
F(x) - это и будет то, что ты ищешь.
Если функция неизвестна - можно попробовать аппроксимировать.
Если не получается, можно найти значение быстрее, чем за O(N)

Короче, ты ничего толком не объяснил.

#2
16:05, 20 ноя. 2016

Если X это int, то конечно есть :)

#3
16:11, 20 ноя. 2016

Sergio
> Если функция неизвестна - можно попробовать аппроксимировать.
нужно lossless

#4
16:12, 20 ноя. 2016

ArchiDevil
X - это инт, мало того он еще и равномерный инт))

#5
16:42, 20 ноя. 2016

IROV..
Запаковать любым Аллахом и создать таблицу смещений в запакованных данных в виде какого-нибудь бинарного дерева? Тогда будет явно быстрее O(n).
Тем же ZIP разбить эти float значения на "файлы"-бакеты, которые будут собирать в себя какое-то количество значений. Потом заюзать ZIP и вычитывать необходимый интервал (для графика ведь интервал будет нужен, я уверен) как "файл".

#6
17:13, 20 ноя. 2016

ArchiDevil
операция
getData(uint32_t _index) должна быть максимально быстрая, с zip так не получиться :)

#7
19:08, 20 ноя. 2016

IROV..
> getData(uint32_t _index) должна быть максимально быстрая, с zip так не получиться :)
Получится, если:
1. Грамотно кешировать некоторое количество уже распакованных интервалов
2. Распаковывать интервалы с упреждением в другом потоке (в случае последовательного доступа к интервалам)

#8
4:17, 21 ноя. 2016

Значение линейно интерполировать?
Поиск интервала будет заниматъ LOG(N) при правильной организации.

#9
8:57, 21 ноя. 2016

dave
> Поиск интервала будет заниматъ LOG(N) при правильной организации.
При ещё более правильной организации можно и LOG(1) добиться, если очень захотеть.

#10
9:56, 21 ноя. 2016

Hybernaculum
Разве что если интервал всего один, да и то спорно.

#11
11:45, 21 ноя. 2016

IROV..
Ряд Фурье пробовал?

#12
19:15, 21 ноя. 2016

foxes
> Ряд Фурье
если нужно lossless то ряд даст столько же "коэффициентов" сколько и "данных"

#13
19:32, 21 ноя. 2016

IROV..
> "коэффициентов" сколько и "данных"
1299.1; 400.34; 29.2; 10.4; 1.0; 0.0; 1.0; 0.0; 1.0; .....

#14
19:33, 21 ноя. 2016

foxes
и?

Страницы: 1 2 3 4 5 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.