Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
#1

Кодирующие контейнеры? - C++

07.07.2013, 14:05. Просмотров 475. Ответов 17
Метки нет (Все метки)

Существуют ли контейнеры, которые позволяют хранить N элементов за memory<O(N)? Именно на ходу. Скорость не так важна.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.07.2013, 14:05     Кодирующие контейнеры?
Посмотрите здесь:

C++ контейнеры
Контейнеры и итераторы C++
C++ Контейнеры и итераторы
C++ Контейнеры
контейнеры С++ C++
C++ Шаблоны и контейнеры
Строки-контейнеры C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
0x10
2452 / 1624 / 238
Регистрация: 24.11.2012
Сообщений: 3,999
07.07.2013, 14:09     Кодирующие контейнеры? #2
nexen, QVector, например, реализует copy-on-write. Т.е. если создаешь копию вектора, то копируется только указатель до тех пор, пока не понадобится изменять значения элементов одного из векторов.

Upd: пардон, не так понял тему, перечитал название - дошло.
DU
1480 / 1056 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
07.07.2013, 14:27     Кодирующие контейнеры? #3
std::vector<bool>
Croessmah
Модератор
Эксперт CЭксперт С++
12702 / 7176 / 801
Регистрация: 27.09.2012
Сообщений: 17,701
Записей в блоге: 2
Завершенные тесты: 1
07.07.2013, 14:29     Кодирующие контейнеры? #4
Цитата Сообщение от DU Посмотреть сообщение
std::vector<bool>
и как оно отражается на
Цитата Сообщение от nexen Посмотреть сообщение
хранить N элементов за memory<O(N)?
???
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 14:33     Кодирующие контейнеры? #5
Нужен сжимающий контейнер с нелинейным ростом размера архива от количества заархивированной инфы, монотонным ростом коэффициента сжатия от размера и возможностью добавлять инфу без полной распаковки того, что уже есть и последующей запаковки не сжатого контейнера?
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
07.07.2013, 14:41  [ТС]     Кодирующие контейнеры? #6
taras atavin, как уже сказал, скорость не так важна, но было бы не плохо, если бы можно было выбирать между контейнерами, что могу и с распакованной и с не распакованной инфой работать.
Да, с нелинеймным ростом архива, а вот коэффициент сжатия.. недопонял вас. Если имели ввиду, что при 100 байтах ушло 5 байт, а при 1000 уже 100 байт, а не 50, то это не важно. Главное, чтобы он сжимал и, желательно, хорошо сжимал на объемах 100мбайт+.
Если есть такие для стандартных типов, то ладно, а если есть и для кастомных - то вообще шикарно!
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 14:47     Кодирующие контейнеры? #7
Ну как где я толкую о скорости?

Добавлено через 1 минуту
Цитата Сообщение от nexen Посмотреть сообщение
Да, с нелинеймным ростом архива, а вот коэффициент сжатия.. недопонял вас.
Коэффициент сжатия есть отношение размера заархивированной инфы к размеру архива. Ладно, напишу проще. Чем больше, тем компактней?

Добавлено через 2 минуты
То есть 100 байт занимают 90, 1000 - 800, 10000 - 7000, а гигабайт вжимается менее, чем сотню мегов? График размера архива от размера заархивированной инфы должен быть выпуклым?
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
07.07.2013, 14:49  [ТС]     Кодирующие контейнеры? #8
taras atavin, одно дело - распаковать, найти, запаковать, другое дело - найти. На скорость виляет.
Ну значит я правильно понял про коэффициент, о чем и написал
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 14:55     Кодирующие контейнеры? #9
Цитата Сообщение от nexen Посмотреть сообщение
одно дело - распаковать, найти, запаковать, другое дело - найти. На скорость виляет.
Только на расход памяти, произвольный доступ на запись элемента сразу архива может занимать даже больше времени, чем распаковать всё, добавить и снова запокавать.

Добавлено через 1 минуту
Цитата Сообщение от nexen Посмотреть сообщение
Ну значит я правильно понял про коэффициент, о чем и написал
Нет. 100/5=20, 1000/100=10. 10<20, это уменьшение коэффициента сжатия с ростом размера архива, а не увеличение.
Tulosba
:)
Эксперт С++
4387 / 3230 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
07.07.2013, 14:56     Кодирующие контейнеры? #10
А не проще ли взять обычный контейнер нужного типа и реализовать сжатие при добавлении, а распаковку при извлечении?
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 15:01     Кодирующие контейнеры? #11
И что останется от обычного?
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
07.07.2013, 15:04  [ТС]     Кодирующие контейнеры? #12
taras atavin, эм, это увеличение коэф. сжатия. Делите в неправильном порядке
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 15:08     Кодирующие контейнеры? #13
В правильном. Размер инфы на размер архива. Если 100 байта храним в 5-ти, то размер инфы 100, а архива 5, если 1000 байт храним в 100-а, то размер инфы 1000, а архива 100. размер инфы делится на размер архива. 100/5=20, 1000/100=10. Вот если 100 байт занимают 5, а 1000 40, то 100/5=20, 1000/40=25, рост.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
07.07.2013, 15:17  [ТС]     Кодирующие контейнеры? #14
taras atavin, эм, что? Вы явно делаете что-то не так, но я вас теперь совсем не понял. Ещё раз, если было 100, а при ахривации ушло (может это слово вы пропустили в прошлый раз?) 5 байт (т.е. стало 95), то коэф. сжатия 5/100 = 5%, а если при 1000 ушло 100, то коэф. сжатия 100/1000 = 10%. Или нет?

update: теперь понял, я дулма про %, как коэффициент сжатия, а вы про "настоящий", так сказать, коэффициент.
DU
1480 / 1056 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
07.07.2013, 15:20     Кодирующие контейнеры? #15
Сообщение от DU
std::vector<bool>
и как оно отражается на
Сообщение от nexen
хранить N элементов за memory<O(N)?
???
не знаю как в новом стандарте, но в старом стандарте специально оговорен случай для std::vector<bool>
в нем элементы хранятся запаковано.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 15:22     Кодирующие контейнеры? #16
Запаковано не значит не линейно.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
07.07.2013, 15:23  [ТС]     Кодирующие контейнеры? #17
taras atavin, вот только я теперь не могу понять, почему 100/5 эффективнее 1000/100, ведь % потерь выше во втором случае, но коффициент ниже :\ Где логика?
Каюсь, про коэффициент узнал впервые. Всегда считал это %

update: Таки да, 100/95 и 1000/900. Ну знал же, что ошибка где-то
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2013, 17:33     Кодирующие контейнеры?
Еще ссылки по теме:

контейнеры (литература) C++
Контейнеры с++ C++
ООП и контейнеры C++
Контейнеры C++
Контейнеры STL C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 17:33     Кодирующие контейнеры? #18
Процент потерь - это вообще совсем другое. Процент потерь есть выраженная в процентах доля исходной инфы, не подлежащая восстановлению после кодирования. То есть если было 10 000, сжали до 2 000, потом распаковали и совпало только 9900, то процент потерь 10%. Есть ещё сжатие до стольки то процентов, это наоборот 100*размер архива/размер инфы.

Добавлено через 2 минуты
Сжатие с коэффициентом 4 (четырёхкратное) - это сжатие до 25%. С коэффициентом 2 (двухкратное) - до 50%.
Yandex
Объявления
07.07.2013, 17:33     Кодирующие контейнеры?
Ответ Создать тему
Опции темы

Текущее время: 04:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru