Как бы писал я.

Я бы меньше байта не мельчил - только расстраиваться.
У каждого байта я бы считал старший разряд флагом конца числа. А младшие семь - значимыми разрядами. И число 0-127 помещались бы в один байт, 0.....128*128-1 - в два байта и так далее.

Двухбайтные из диапазона 0....127 я бы оставил себе на память как эскейп- коды.

Если жалко терять один бит из восьми, то тогда бы брал слова (или двойные слова) с битом-флагом. Тогда потери на флаг конца - 1/16 32 64 - Это хорошо. Но, диапазон ноль-127 кодируется в два байта - это небольшая потеря, если маленьких чисел мало, большая - если много.

Опять же, если чисел в диапазоне 0...32000 мало, в общем объеме, то флагом можно снабжать уже не слово, а двойное, или даже четверное слово. Или даже кусок бОльшей разрядности.

В зависимости от того, насколько большие числа в среднем - выгодно будет использовать кусочки разной длины. Для переключения между разрядностью зафлагированного куска - вышеупомянутые эскейп - коды.

Наверное, похожим образом устроены коды символов в utf. - не знаю толком, возможно. Мне кажется,что в контексте задачи можно поизучать устройство многобайтных кодировок символов, ну и устройство библиотек по работе с ними.....


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

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

Mayton - байтами удобно работать процессору. Это может быть неидеальный код, на байтах. Но. Он не запредельно хуже хорошего, который на битовой строке. И немного заплатить эффективностью за удобство работы по моему, на практике, вполне логично.

И, я согласен с мнением ранее высказанным в теме - не имея представления о гистаграмме входного массива, оценивать эффективность кода невозможно....

Как с сортировкой - каждому алгоритму можно подобрать такой набор входной, что он поработает подольше.

То есть, если задачу рассматривать как игру разума - то тогда битовый массив, а только соберешься в сторону прикладного - байты, слова, двойные и четверные - тут как тут....

Ну, мнение. Уважаю тех, кто способен к более абстрактному, менее приземленному мышлению.

В конце концов, ну давайте нагоним тест. На вход впихнем поток рандомных натуральных 0...2^64-1.

И посмотрим, какой компактификатор сделает среднюю битность меньше 60?

В среднем 64 разрядном числе вероятность иметь 64 бита - половина, больше 62 - 3/4, больше 61 - 7/8, > 60 ----- 15/16.....
И так далее. В общем средняя длина в битах числа из равномерного рандомного потока - немногим меньше разрядности.

Исхитряйся или нет. Если поток сильно отличается от равномерного, и мелочи там много - тогда конечно дело другое. Но, как справедливо отмечали выше, тогда эту неравномерность и перекос надо описывать? Перед моделированием для битвы кодировок, в которой побеждает компактнейшая.

Давайте уточним формулировку.

Например, создать битовый код для натуральных чисел 1...N , позволяющий записывать их в поток и считывать в произвольном количестве и порядке, такой что сумма битовых длинн по всему набору была минимальна? Или как? Или с доп ограничением, что длинна битовой последовательности для маленького числа была заметно меньше, чем для числа очень большого?

или доп- требование минимакса - чтобы максимальная длинна кодирующей последовательности по всему набору была как можно меньше? Для последнего выгодно кодирование в равной разрядности.

---- критерии к.м.к. не заданы точно, отсюда разночтения

Для кодировки произвольного натурального числа можно построить ф-цию R(n) - сколько разрядов бинарного представления нужно для представления числа n.

Какой интеграл, или максимум, или еще чего от этой ф-ции мы оптимизируем на всем множестве возможных кодировок? Понятно, что наитупейшая кодировка такова - столько единичек, какое число а потом нолик. Такими кодами можно кодить любое натуральное и r(n)=n по такому случаю,
Самая остроумная кодировка по моему не может давать стабильно лучше чем log 2 (N).

какой интеграл от ф-ции разрядности соответствует интуитивному идеалу --компактного представления числа-- ?

В принципе, я могу предложить простенькую кодировку для r(n) = A* log B (n) + C.

Например берем X. Кодируем n. В системе по основанию 2^x-1 - если икс=2 - то в троичной.

Каждому знаку этой кодировки ставим в соответствие ее двоичный код, разрядности икс.

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

Ну вот, вышли на логарифмическую метрику, с константами A, B, C. Она хорошая, или нет? И почему? В каком смысле другие ==кодировки== лучше или хуже..... практичнее? В принципе, вариант ==байт с маркером== дает такую же метрику

чем больше икс, тем меньше лишних разрядов будет на больших числах, но больше - на маленьких, вроде так.......

Иван FXSVladimir Baskakov простенькую кодировку для r(n) = A* log B (n) + C.

Например берем X лично я не понял, как у вас тут соотносятся r и Х ...

Для случая икс=2.

2^x-1 = 3.

Кодируем число в троичной системе.

Каждый знак кода заменяем
0 на 00
1 на 01
2 на 10

11 - стоп-биты.

Длина кода в тоичной системе для числа N - log 3 (N), каждый знак кодируется двумя битами - A=2, стоп-битов тоже два С=2.

Икс=3 - два в кубе=8, кодируем в семиричной системе

3 (log 7 (n)) + 3.

Умные кодировки, они конечно получше. Намного ли? Вопрос.

На практике, я бы этим кодом кодировал длину битовой последовательности числа. а само число оставлял как есть.

Ноль
01 11 0
1 01 11 1
2 - 10 11 10

-- на практике от этого польза сбалансирована вредом. Так, на тысячебитное целое В заголовке будет 6*2+2 - 10 бит.... вроде немного, но такие длинные целые малотипичны. Для 64 разрядного - 4*2+2 = 10 бит. Потери больше 10 %...