Russian Qt Forum
Ноябрь 01, 2024, 06:45 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: 1 [2]   Вниз
  Печать  
Автор Тема: Кто работал с QBitArray? - поделитесь соображениями  (Прочитано 12211 раз)
ilot
Гость
« Ответ #15 : Декабрь 29, 2009, 05:17 »

Вот написал на колене рабочий пример. Конечно на идеальный код не претендует, но тем не менее.
Интересное решение! Вот только Вы чересчур увлеклись сокращением объема задействуемой оперативки, что с водой и ребенка выплеснули. Автор пишет:
Для ускорения работы хотелось бы загружать массив из файла в оперативку целиком. Но мне не нравится такая пустая трата ресурсов (да и не на любом компе такое получится загрузить, либо получится с тормозами) - ведь если элементов всего пять, то для их кодирования достаточно трех битов, а не байта.
Человек хочет ускорить работу своего алгоритма, и с этой целью рассматривает вариант помещения всего массива данных в память. Из предложенной вами реализации видно, что функция выборки элемента из массива будет задействовать в среднем 14(!) операций деления (исходя из предположения, что обращение к любому из 27 элементов равновероятно). Функция вставки и того сложнее - в среднем 28 операций деления, 14 - умножения, 14 - сложения. Умножение и деление - это довольно дорогие операции! Даже без тестирования понятно, что данная реализация будет работать в разы медленнее, чем работа с октетами. А значит весь выйгрыш от экономии памяти сожрется многократно.
Забудьте о том как думает процессор, думайте сами (-:
А ничего, что в конечном итоге именно процессор будет это все делать? Подмигивающий Поэтому, если вы хотите что-то оптимизировать, то как раз об этом и стоит думать. Вовсе не случайно на практике используются системы счисления, основанием которых является степень двойки. Так уж устроены современные ЭВМ, что только такие системы счисления дают максимальную эффективность при вычислениях.
На мой взгляд, для данной задачи лучше всего подходит использование именно октетов. Это позволит существенно сократить объем используемой памяти, без заметного падения производительности. Вот как-то так (взял за основу функции Dendy, не сочтите за плагиат   Улыбающийся):
Код
C++ (Qt)
typedef unsigned char uchar;
typedef unsigned qint64 uint64;
static const int MaxItems = 21;
static const uchar mask = 7;
 
inline uchar takeAt( uint64 blob, int i )
{
Q_ASSERT( i >= 0 && i < MaxItems );
       return (uchar)(blob >> i*3)&mask;
}
 
inline void putAt( uint64 & blob, int i, uchar value )
{
Q_ASSERT( i >= 0 && i < MaxItems );
Q_ASSERT( value >= 0 && value < 5 );
       blob |= ((uint64)value << i*3);
}
 
Код не тестировал (возможны недочеты и опечатки), но общая идея должна быть ясна. Приведеные побитовые операции будут выполняться очень быстро.

И еще, по поводу inline-функций: функции, приведенные Dendy, слишком сложны, чтобы компилятор смог бы сделать их подставляемыми, а значит ко всему прочему добавятся накладные расходы на их вызов  Подмигивающий

P.S. по сравнению с вариантом от Igors, в котором в 64 бита можно поместить 16 элементов, здесь можно сохранить 21 элемент. При этом накладные расходы будут не больше.
« Последнее редактирование: Декабрь 29, 2009, 05:55 от ilot » Записан
Dendy
Гость
« Ответ #16 : Декабрь 29, 2009, 06:10 »

Октетами... Это же банально и скучно. Снова эти степени двойки, да их уже все наизусть знают. А вот вы посчитайте степени пятёрки хотя бы до 7-го порядка, слабо? ((-:

Вообще вы не подумайте, я с вами полностью согласен. Просто хотел предложить нестандартное решение, напомнить, что кроме двоичного счисления существуют и другие (надо же!). А то того и гляди хохма про 1024 метра в километре станет правдой.

Кстати, я там дальше утонил, что можно для умножения/деления использовать константы. И если логика обработки значения гораздо тяжелее логики выборки, а память важна - таки можно разменять ресурсы RAM на ресурсы CPU (-;
Записан
ilot
Гость
« Ответ #17 : Декабрь 29, 2009, 06:47 »

Октетами... Это же банально и скучно. Снова эти степени двойки, да их уже все наизусть знают. А вот вы посчитайте степени пятёрки хотя бы до 7-го порядка, слабо? ((-:
Веселый Что поделать, довольно часто работа программиста банальная и скучна, даже рутинна. Но судя по вопросу автора работа с битами для него нова, а значит скучно быть не должно Подмигивающий. Да и стоит ли заморачивать голову человеку нестандартными подходами, если он еще с классикой разобраться не успел? Так кроме каши в голове ничего не получиться.

Не слабо. Степени пятерки в уме как раз очень хорошо считаются Улыбающийся.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #18 : Декабрь 29, 2009, 16:06 »

До кучи: 5 бит на значение встречается не так уж редко (напр. некоторые форматы QuickTime). Реализация скромная, на базе unsigned short (используются 15 бит из 16)
Записан
fulkabaster
Гость
« Ответ #19 : Январь 02, 2010, 16:52 »

Я правильно понимаю, что если мне не нужно изменять содержимое файла, то memory mapping не даст преимущества перед простой загрузкой данных целиком из файла, например, в QList?
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #20 : Январь 02, 2010, 19:51 »

Я правильно понимаю, что если мне не нужно изменять содержимое файла, то memory mapping не даст преимущества перед простой загрузкой данных целиком из файла, например, в QList?
Ну это уж Вы сами смотрите по обстановке. "Паковка" дает хорошую экономию по памяти и незначительное увеличение вычислений. Другое дело с ней заботы - стандартный контейнер не попользовать, адрес от этого "3-битового чудика" не получить, надо работать по индексу и.т.п. Все это не смертельно и пережить можно, но, как правило, имеет смысл только если "есть что паковать".
Записан
fulkabaster
Гость
« Ответ #21 : Январь 02, 2010, 20:46 »

Нет, в последнем вопросе я имел ввиду работу с байтами, без паковки. Тут просто предложили вариант Memory Mapped File, я с ним не знаком, но по названию догадываюсь, что это отображение файла в память, при этом наверняка изменения данных в памяти потом запишутся в файл. Я и поинтересовался - если мне не нужно сохранять эти изменения в файл, то какое преимущество дает Memory Mapping перед простой загрузкой данных в любой контейнер?

А насчет паковки я решил сделать оба варианта Улыбающийся Будет проверяться кол-во свободной памяти. Если хватает - загрузим байтами, если маловато - то битами. Компромис разрешен Улыбающийся
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #22 : Январь 02, 2010, 21:01 »

Нет, в последнем вопросе я имел ввиду работу с байтами, без паковки. Тут просто предложили вариант Memory Mapped File, я с ним не знаком, но по названию догадываюсь, что это отображение файла в память, при этом наверняка изменения данных в памяти потом запишутся в файл. Я и поинтересовался - если мне не нужно сохранять эти изменения в файл, то какое преимущество дает Memory Mapping перед простой загрузкой данных в любой контейнер?
Memory Mapped File - это своя песня и к битовой паковке прямого отношения не имеет. А вот когда надо наладить обмен данными между 2-мя процессами - без Memory Mapped не обойтись.

А насчет паковки я решил сделать оба варианта Улыбающийся Будет проверяться кол-во свободной памяти. Если хватает - загрузим байтами, если маловато - то битами. Компромис разрешен Улыбающийся
Программист должен быть ленивым и никогда не делать 2 варианта  Улыбающийся
Записан
Страниц: 1 [2]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.069 секунд. Запросов: 23.