 |
|
Модераторы: Daevaorn |
 
|
|
Компактный массив значений в диапазоне 0..2 
| semibug |
|
|||
|
Опытный  Профиль Группа: Участник Сообщений: 323 Регистрация: 27.3.2009 Репутация: нет Всего: нет |
Имеется большое кол-во значений в диапазоне 0..2. Необходимо обеспечить компактное хранение в памяти и произвольный доступ к любому из значений.
Укладка в один байт по 4 значения ( 2 бита на значение ) избыточна ( 2 бита могут кодировать диапазон 0..3 ). Подскажите пожалуйста, если кто сталкивался с подобной проблемой, в каком направлении двигаться. |
|||
|
||||
Загрузка ...
| RatHat |
|
|||
 Вождь индейцев Профиль Группа: Участник Сообщений: 234 Регистрация: 5.9.2005 Репутация: нет Всего: 1 |
меньше, чем в два бита, не вложишься.
--------------------
Ma a kis' hi ve'ist i wan'i na e'ho ho wan'i |
|||
|
||||
| semibug |
|
||||
|
Опытный Профиль Группа: Участник Сообщений: 323 Регистрация: 27.3.2009 Репутация: нет Всего: нет |
Пока пришло в голову упаковывать в один байт по 5 значений. Это на 0.4 бита/значение компактнее варианта "два бита на значение".
Тройка в пятой степени дает 243, некоторая избыточность всё же сохраняется. Упаковываем:
Распаковываем:
|
||||
|
|||||
| Void |
|
|||
 λcat.lolcat Профиль Группа: Участник Клуба Сообщений: 2206 Регистрация: 16.11.2004 Где: Zürich Репутация: 40 Всего: 173 |
В байт (8 бит) сравнительно легко можно уложить 5 тритов (3^5 = 243), что очень близко к теоретическому максимуму 8 * log(2) / log(3) = 5.05.
Доставать и устанавливать триты просто в соответствии с определением троичной системы счисления. -------------------- “Coming back to where you started is not the same as never leaving.” — Terry Pratchett |
|||
|
||||
| semibug |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 323 Регистрация: 27.3.2009 Репутация: нет Всего: нет |
Void, спасибо за формулу 8 * log(2) / log(3), остановлюсь на этом варианте.
|
|||
|
||||
| Peter |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 771 Регистрация: 28.7.2003 Где: Ставрополь Репутация: -1 Всего: 1 |
Читаем байт в троичной системе счисления. Получается, что в байте (0..255) укладывается 5 троичных цифр (0..242).
Можно увеличить единицу хранения - не один байт, а... Кому хочется, пусть сам считает. Но экономия памяти уже будет незначительной, а вычислений - чрезмерными. Так что если хранить троичную цифру в двух битах, перерасход памяти равен 33% (4:3-1). А если хранить 5 троичных цифр в байте, перерасход памяти 5% (256:243-1). -------------------- всё, что делаете, делайте от души, как для Господа (Послание апостола Павла колоссянам, 3:23). |
|||
|
||||
| SenkraD |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 933 Регистрация: 3.2.2006 Где: Украина::Киев Репутация: 2 Всего: 23 |
semibug, сорри за лёгкий оффтоп, но мне просто интрестно:
- под что щас пишеш? какуе-то фирмварю? - или просто интерестно стало? -------------------- Имеющий язык - да не убоится спросить!  |
|||
|
||||
| GoldFinch |
|
|||
|
Профиль Группа: Завсегдатай Сообщений: 2141 Регистрация: 30.11.2008 Репутация: 15 Всего: 26 |
в n двоичных разрядов можно уместить n/log2(3) трит
например в 8 двоичных разрядах- 5.047 трит, с избыточностью 0.047трит для 16 избыточность будет в 2 раза больше, т.к. там поместится 10.095трит а для 7 двоичных разрядов избыточность будет уже равна 0.416 так что надо просто подобрать блок с наименьшей избыточностью |
|||
|
||||
| semibug |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 323 Регистрация: 27.3.2009 Репутация: нет Всего: нет |
SenkraD, до интересов руки всё не доходят ))
Пишу змейку под атмеловский чип. Оперативки доступно 1 кб, а змею хотят с плавным перемещением по всем направлениям, т.е. для каждого пикселя по пути змеи приходится хранить данные. Вот извращаюсь как бы её подлиннее на несколько сегментов сделать. |
|||
|
||||
| mes |
|
|||
|
любитель Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: 144 Всего: 250 |
а стоит ли вообще заводить tribool ? я так понимаю блок данных всегда отн. большой.. мож просто хранить по отдельности наборы необходимых битов ? |
|||
|
||||
| semibug |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 323 Регистрация: 27.3.2009 Репутация: нет Всего: нет |
Не совсем понял о чем идет речь. |
|||
|
||||
| RatHat |
|
|||
|
Вождь индейцев Профиль Группа: Участник Сообщений: 234 Регистрация: 5.9.2005 Репутация: нет Всего: 1 |
semibug, чип серии ATtiny1X что ли?
--------------------
Ma a kis' hi ve'ist i wan'i na e'ho ho wan'i |
|||
|
||||
| mes |
|
||||
|
любитель Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: 144 Всего: 250 |
предлагал пересмотреть способ организации массива..
какое "имя" у каждого из значений этого диапазона ? Добавлено через 1 минуту и 4 секунды и язык какой си или с++ ? |
||||
|
|||||
| SenkraD |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 933 Регистрация: 3.2.2006 Где: Украина::Киев Репутация: 2 Всего: 23 |
semibug, я так понимаю, что mes предлагает тебе использовать разрежённые массивы.
mes, я прав? - если да, то идею поддерживаю 2 руками. И ещё всё таки неплохо было бы знать язык на котором ты пишеш -------------------- Имеющий язык - да не убоится спросить! |
|||
|
||||
| semibug |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 323 Регистрация: 27.3.2009 Репутация: нет Всего: нет |
компилятор C++
Разреженный массив, если правильно понял, не подходит, т.к. заполненность массива может достигать 100% |
|||
|
||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0561 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |