Вот написал на колене рабочий пример. Конечно на идеальный код не претендует, но тем не менее.
Интересное решение! Вот только Вы чересчур увлеклись сокращением объема задействуемой оперативки, что с водой и ребенка выплеснули. Автор пишет:
Для ускорения работы хотелось бы загружать массив из файла в оперативку целиком. Но мне не нравится такая пустая трата ресурсов (да и не на любом компе такое получится загрузить, либо получится с тормозами) - ведь если элементов всего пять, то для их кодирования достаточно трех битов, а не байта.
Человек хочет
ускорить работу своего алгоритма, и с этой целью рассматривает вариант помещения всего массива данных в память. Из предложенной вами реализации видно, что функция выборки элемента из массива будет задействовать в среднем 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 элемент. При этом накладные расходы будут не больше.
