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

Упаковка графика функции (3 стр)

Страницы: 1 2 3 4 5 Следующая »
#30
21:22, 25 ноя. 2016

IROV..
> Меня заинтересовал вопрос, а как бы я поступил не имея анализа а просто производный график, наверное единственное свойство которого это 99% неразрывность.
Такие задачи в общем виде обычно решения не имеют. Любое сжатие предполагает, что есть наиболее вероятный вид набора данных.
Соответственно, метод сжатия определяется путем пристального взгляда на график и проведения статистических тестов.

Конкретно, в задаче хранения вещественнозначной функции, первое что необходимо сделать — это четко определить необходимую точность.
Абсолютной точности с плавающей точкой не бывает и полная точность float/double тоже обычно не нужна.
Перейдя к n-битным целым (n может быть не только 8/16/32/64) уже можно серьезно сжать данные.

Если функция достаточно гладкая, то я бы нарезал ее на куски, каждый кусок приблизил полиномом некоторой степени, а остатки пожал Хаффманом/арифметикой.


#31
21:43, 25 ноя. 2016

}:+()___ [Smile]
> Абсолютной точности с плавающей точкой не бывает
бывает
>Перейдя к n-битным целым (n может быть не только 8/16/32/64) уже можно серьезно сжать данные.
ясно

#32
2:18, 26 ноя. 2016

IROV..

> преобразовать такой график в dF и хранить дельта значение
Толку от такого преобразования в плавающей точке - полный ноль. Получится шум, который сжимать нисколько не легче, чем исходные данные. В целой точке может чуть получше будет за счёт возможного уменьшения разрядности.

#33
2:36, 26 ноя. 2016

Ghost2
Уменьшить разрядность для флоата тоже можно, но тут согласен что в режиме целых чисел добиться этого проще. Но это уже немного другое.

#34
22:44, 26 ноя. 2016

Ghost2
> Толку от такого преобразования в плавающей точке - полный ноль.
IROV..
> но тут согласен что в режиме целых чисел добиться этого проще.
Вот вы оба либо не видите либо ни когда этого не делали. Но проблем ни каких с описанными вами проблемами не вижу, тем более что Smile выше вам практически всю подноготную подробно расписал. Хотя тоже немного отклонился. Поскольку приближение тем же полиномом даст остаток, в несколько младших бит (тем же вычитанием) от float/double, который собственно он и пожал.
Кстати даже в графике со скачками (условно не большим шумом) можно тем же полиномом (или парой коэффициентов фурье) убрать основную амплитуду колебаний, а остальное сжать.
"убрать основную амплитуду колебаний" -  это собственно даст выравнивание степеней точности плавающих значений, что превратит остаток в целые числа, точнее биты мантисы.
Проблемы конечно же возникнут, но если ряд значений будет ... 0 1 2 0 3 1e+55 10 1 3 ... вот это проблема соглашусь. И все таки это не более чем высоко частотный всплеск.

Есть еще вариант тем же образом отфильтровать отдельно экспоненту(порядок) и мантису, но я не пробовал.

#35
22:45, 26 ноя. 2016

}:+()___ [Smile]
>с плавающей точкой не бывает
Перебор, а?
То что задача странная, ещё не значит, что универсально забить.

IROV..
Правильно ли я понимаю постановку задачи?
Есть массив флоатов. Он по замыслу - отсчёты некоторой функции (если повезёт - они ещё эквидистантные). О функции почти ничего не известно, но надеемся, что она более-менее внятная - непрерывная, без особой болтанки, и фигни.
Нужно этот массив сжать без потерь: при расжатии получить те же (побитово) данные.
Ещё хочется доступ за O(1), или быстрее, чем за O(N).

Ок, давай смотреть.
Ну вообще да, первый приходящий в голову способ не обнадёживает:
http://rextester.com/PUPM72786

#36
0:44, 27 ноя. 2016

FordPerfect
Синус все таки не зря используют для генерации случайных чисел, поскольку он выдает достаточно хаотичное чередование бит, если это не шаг кратный ПИ, так что думаю его одного бы хватило чтобы LZW не справился, независимо от последовательности и ранжирования этих чисел.
Наверняка 90% сжатия получилось за счет степени порядка поскольку она там повторяется.

#37
1:52, 27 ноя. 2016

FordPerfect
> То что задача странная, ещё не значит, что универсально забить.
То, что такая задача, вообще, возникла, говорит о том, что автор занимается чем-то странным.
Результат набора операций над float/double зависит от железа, компилятора, опций, стандартной библиотеки; поэтому требование битовой идентичности говорит о том, что человек не умеет обращаться с плавающей точкой.
То, что эту задачу, в принципе, можно решить, не отменяет ее бредовости.

foxes
> Синус все таки не зря используют для генерации случайных чисел
Синус используют для генерации случайных чисел только те, кому пофиг на качество и производительность.
Серьезные тесты случайности синус не пройдет.

#38
2:11, 27 ноя. 2016

}:+()___ [Smile]
Ключевое выражение здесь
foxes
> чередование бит
Но было бы не плохо глянуть на материал с такими тестами.

+ тем не менее
#39
4:05, 27 ноя. 2016

}:+()___ [Smile]
Да вроде мало сейчас неконформного IEEE754 железа. Разве что SPU (Cell) вспоминается из относительно свежего. Ну и GPU, может быть, но это отдельный разговор.
Компиляторы... делают жизнь интереснее. Но и с ними можно дружить. Особенно если ограничиться базовыми операциями, и не звать функции стандартной библиотеки. На худой конец - можно асм, зафиксировать порядок операций.
Т. е. есть куча подвохов (напр. -mfpmath=387, -ffast-math, -frounding-math, FENV_ACCESS,  FP_CONTRACT), но они довольно известны, и можно идентичности достигать (и во многих классах ситуаций они не проявляются).
Результат базовых операций - определён однозначно (за вычетом вещей вроде битового представления NaN) - зависит от направления округления, но его можно не менять.
Мой тезис - побитовая повторяемость часто достижима и иногда осмысленна.
Конкретно в данной задаче - хз.

>Серьезные тесты случайности синус не пройдет.
http://www.gamedev.ru/code/forum/?id=215866&page=2#m25
На BigCrush не проверял, впрочем.
Кстати, если не лениво - проверишь?

IROV..
foxes
По здравом размышлении:
1. Для более плавной функции сжатие лучше. Например x*=0.1f в моём примере даёт сжатие ~48%.
2. Вместо DEFLATE можно использовать ranges. Что-то в духе

0[10 bits] - input in [-2^9;+2^9)
10[20 bits] - input in [-2^19;+2^19)
11[32 bits] - input in [-2^31;+2^31)
3. Таблицу можно разделить на блоки (например по 64). Каждый сжать, начала - в массиве (+4 байта на блок). При запросе - разжимаем блок, берём значение.

Подозреваю 2x сжатие можно получить.

Насколько это оправданно - вопрос к ТС.

#40
5:34, 27 ноя. 2016

Собственно код:
http://rextester.com/NRQIX28009
Время - для демонстрации, можно сильно оптимизировать.

#41
6:04, 27 ноя. 2016
Размер блока Сжатие Время запроса
4 106% 96 нс
8 69% 132 нс
16 50% 252 нс
32 40% 469 нс
64 36% 925 нс
128  34% 1833 нс
#42
6:58, 27 ноя. 2016

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

> На BigCrush не проверял, впрочем.
Там основной источник рандома — это взятие дробной части, а не синус. Подозреваю, что его можно безболезненно заменить на простой полином.
Но я бы не стал использовать генератор с явно неравномерным распределением, особенно когда есть более вменяемые альтернативы.

#43
13:48, 27 ноя. 2016

foxes

> Поскольку приближение тем же полиномом даст остаток, в несколько младших бит
Не будет оно давать остаток младшими битами. Даже если у тебя диапазон разностей будет от -1 до 1, то это половина всех чисел флоат. Каждая разность со свое мантиссой, экспонентой и знаком.

> что превратит остаток в целые числа, точнее биты мантисы.
Вот у тебя остаток - 0,0001 и для следующего числа 0,001. В хексе это будет 0x38d1b717 и 0x3a83126f. Тебе сильно легче это сжимать стало?

> можно тем же полиномом (или парой коэффициентов фурье) убрать основную амплитуду колебаний
Давай уже переходи к формулам.

#44
22:17, 27 ноя. 2016

Ghost2
> Вот у тебя остаток - 0,0001 и для следующего числа 0,001. В хексе это будет
> 0x38d1b717 и 0x3a83126f. Тебе сильно легче это сжимать стало?
Возьмем "табличное" 0.001 (0x3a83126f) (0.000976562500 *  1.0240000486373901) и "приближенное" 0.00233456 (0x3b18ff6b) (0.00195312500 *  1.195294737815857)
Дополнительная проблема вычитания с плавающей точкой в том что при большой разнице порядков мы еще и точность теряем.
Я бы здесь сделал самое простое целочисленное вычитание и получил бы 0xFF6A1304. В лучшем случае основная масса остатков будет 0xFFnnnnnn, 0x00nnnnnn. В идеале приближения с равными порядками, 0xFFFFnnnn, 0x0000nnnn - я думаю это поможет.

Если взять твой пример с разницей 0,0001 между "табличным" 0.001 (0x3a83126f) и "приближенным" 0.0011 0x3a902de0.
То будем иметь такую разницу 0xFFF2E48F. По сути мы здесь будем хранить не фактический порядок(экспоненту/степень) остатка, а относительный.
Для точного вычисления log2 SSE double, Интеловцы использовали именно такой подход c 8 кило байтовой корректирующей таблицей (таблицей остатков) для всех результатов. Только само вычитание/сложение в реализации они использовали плавающее потому что часть остатка там имеет фиксированный порядок.

Но я бы вообще разделил хранение порядка и мантисы, и работал бы с ними как с отдельными целочисленными таблицами, не пытаясь добавить единицу в начало мантис.

FordPerfect
> http://www.gamedev.ru/code/forum/?id=215866&page=2#m25
FordPerfect
> Ну и тормозит, дело ясное.
У тебя n - 1,2,3... ?
можно заменить на приращение угла, будет нормальная скорость. Или там другое?

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

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