Сжимать соответствующими алгоритмами (Шеннон-Фано и т.п.)| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Сжатие дробных чисел |
| Автор: MastEdm 14.8.2007, 15:50 |
| Может кто встречался с алгоритмом сжатия дробных чисел? Постановка задачи примерно такая. Нам идёт набор чисел типа float. Нужно уметь писать их в файл и соответственно читать. Причём требования по скорости такие, что читать нужно очень быстро, а писать - ну как придётся. Причём писать нужно каждое пришедшее число. Какие будут идеи? |
| Автор: Sartorius 14.8.2007, 16:31 |
| Работать с потоком Float - ов как с потоком бит. Сжимать соответствующими алгоритмами (Шеннон-Фано и т.п.) |
| Автор: MastEdm 15.8.2007, 16:02 |
| Не подойдёт. Нужно уметь писать каждое пришедшее число в независимости от предыдущих чисел. Максимум если только от предыдущего. А на 32 битах особо не развернёшься. Сейчас использую свой алгоритм работы с битиками, но там страшный код. Хочется что-то ещё посмотреть. Основной акцент должен быть сделан на битовую структуру флота. Нужно учесть, что чаще всего в последовательности встречаются числа 0.15, 0.2, 0,25, то есть в них много нулей в битах |
| Автор: skyboy 15.8.2007, 18:31 | ||
а вообще, каково вероятностное распределение значений? может, стОит использовать словарный алгоритм для значений, которые встречаются чаще других? например, первый бит значения соотвествует флагу "словарное значение"/"уникальное значение" и если флаг установлен - последующее будет соотвествовать порядковому номеру числа в словаре, а если не установлен, то последующие биты будут соотвествовать числу. кроме того, если числа одного порядка, то стоило бы проводить нормализацию, и тогда можно было бы избавиться от мантиссы... |
| Автор: JackYF 15.8.2007, 18:40 | ||
хм... в бинарном представлении будет всё немного хуже при переводе из десятичного. Если нужна скорость - я бы писал напрямую. Без преобразований. 4 байта - не так уж и много. А при архивации скорость чтения будет страдать. |
| Автор: MastEdm 15.8.2007, 19:00 |
| JackYF, напрямую сжирается много времени на чтение / запись. |
| Автор: Sartorius 16.8.2007, 13:24 |
MastEdm, а покажи как у тебя ввод-вывод реализован. Может ты там fprintf используешь или вообще потоки...  |
| Автор: MastEdm 16.8.2007, 14:39 |
| Ввод / вывод open / read для std::fstream |
| Автор: JackYF 16.8.2007, 15:23 | ||||
таки потоки. Ну раз read, то это не слишком критично. Кстати, а поиграться с буферизацией/антибуферизацией? FILE* там всякие... Если для каждого числа тебе нужно записать 4 байта (всего лишь), а ты хочешь заархивить это (во что? в байт, в два, в три? - ведь тебе же надо, чтобы оно было независимо). Куда уже дальше? Что может быть быстрее, чем прямая запись в файл четырех байт без преобразований? При архивации, имхо, ты потратишь в десятки раз больше процессорного времени, чем при обычной записи. Кстати, а ты уверен, что именно чтение из файла - узкое место в программе? |
| Автор: MastEdm 17.8.2007, 14:52 |
| Решение нашёл, правда не в сжатии. Буду читать не по одному числу, а сразу большим буфером и потом с ним работать. |
