Кто работал с QBitArray? - поделитесь соображениями

[fulkabaster]

Стоит задача обработки больших массивов данных, в которых каждый элемент может принимать одно из пяти значений. Длина массивов - до сотен миллионов элементов.
До этого я массивы задавал просто - с помощью char. Т.е. один байт на один элемент. При этом массивы могли занимать пару сотен мегабайт. Для ускорения работы хотелось бы загружать массив из файла в оперативку целиком. Но мне не нравится такая пустая трата ресурсов (да и не на любом компе такое получится загрузить, либо получится с тормозами) - ведь если элементов всего пять, то для их кодирования достаточно трех битов, а не байта.
Например:
A - 000
B - 001
C - 010
D - 011
E - 100
Так можно уменьшить размер занимаемой памяти почти в три раза.
Жалко, не существует в Qt готовых решений массивов, где можно задать количество бит на элемент
Так вот, хочу создать свой класс, который будет хранить данные внутри как QBitArray, но наружний интерфейс будет работать только тройками битов.
Так вот вопросов два - 1) может есть что-то подобное уже готовое, что я мог проглядеть (хотя и не обязательно Qtшное); 2) Если делать это с нуля с помощью битовых СИшных операций или с помощью QBitArray - разница в скоросте работы не будет существенной (в описании QBitArray мало что сказано о том, насколько он быстро работает)?
Да, и самый главный вопрос - а выгодно ли это делать с точки зрения скорости? Ведь если загружаю байты, то их будет больше, но читаются они быстрее. Если загружу битами (хотя это те же байты, конечно), то памяти займет меньше, но скорость? Как я понимаю, чтобы прочитывать все элементы, там в каждом байте сначала биты будут сдвигаться и сравниваться.

[Makss]

ну если ваши трёх-битные элементы реализовывать с помощью QBitArray, то на счёт скорости я незнаю как будет, а вот в памяти вы точно проиграете, ну это в том случае если каждый элемент будет реализован с помощью QBitArray.
Готовых решений нету, покрайней мере я про них незнаю...

ну я бы сделал так: с помощью QBitArray хранил массив элементов, ну например максимум на массив 192(64 * 3), это означает 64 элемента в массиве, каждый размером по 3 бита, ну или сами как хотите. Максимальный размер массива по количеству элементов должен быть кратным 3!!! Выбирать из массива элемент по индексу думаю не составит труда - обычная математика. Ну а в случае если индекс элемента принадлежит другому массиву - то это также простая математика... таким способом учтём проигрышь по памяти...


А вообще в С++ есть такое понятие как "Битовые поля"
int bits:4; //4 бита
int bits:3; //3 бита

[Dendy]

Если речь про сотни мегабайт памяти, то вместо восьмеричной системы счисления есть смысл использовать пятеричную. Экономия при идеальном выборе слова для хранения данных - 37.5% ОЗУ.

[fulkabaster]

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

Конечно нет, я собирался просто массив из QBitArray рассматривать не как массив отдельных битов, а как массив отдельных троек битов.

Про битовые поля почитал (http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=131) - вроде из них не получится массивы делать. Там же написано, что работать с битами все-таки медленнее, чем с байтами... Теперь думаю, какой выбор сделать в этой дилемме.

Если речь про сотни мегабайт памяти, то вместо восьмеричной системы счисления есть смысл использовать пятеричную. Экономия при идеальном выборе слова для хранения данных - 37.5% ОЗУ.

Что-то  я не совсем понял... Вроде бы система счисления в компах всегда олна - двоичная, речь идет о том, сколько разрядов юзать. И почему пять? Для кодирования пяти символов хватает и трех битов.

[Dendy]

В вашей задаче нужна пятеричная система счисления, поскольку у вас 5 значений - 01234, а следовательно 567 никогда не используются. Видите, вы сами решили оперировать октетами, хотя процессор ничего об этом не знает, просто C предоставляет битовые операции для удобства, а для пятеричной математики в C ничего нет. Забудьте о том как думает процессор, думайте сами (-:

[niXman]

ересь какая-то. нет единицы меры - 3 бита. как минимум придется выделить 1 байт. а если выделять по одному байту динамически, то при выделении 1024 байт, реальной памяти будет съедено как минимум в 12 раз больше.
и что за компы такие, что на них нельзя загрузить гигабайт в оперативку? что, 92 год?
а вообще, эта "задача" похожа на вымысел.

[niXman]

еще почитайте Memory mapping.

[Makss]

ересь какая-то. нет единицы меры - 3 бита. как минимум придется выделить 1 байт. а если выделять по одному байту динамически, то при выделении 1024 байт, реальной памяти будет съедено как минимум в 12 раз больше.

Ну почему, это наверно в случае если в 1 байте держать именно один элемент, но байт - 8 бит, туда максимум влезет 2 элемента, количество лишней памяти уже съедено, в 2 раза меньше...

конечно можно ещё и последнии биты задействовать, тогда получается так что один элемент будет лежать частями в разных байтах, такое тоже можно и не трудно написать, придётся писать ещё считывалку именно для такого случая... в этом случае вообще по памяти точно не проиграем и не будет тогда пустой не задействованной памяти

[Dendy]

... но байт - 8 бит, туда максимум влезет 2 элемента

Не-а. В байт помещаются значения 0..255, значит в него можно записать 3(!), а не 2 значения, ибо как 5^3 == 125, что тоже влезает в байт (-: Я бы сделал на пятеричной системе счисления чтобы хотя бы замерить отношение размена ресурсов CPU на сэкономленую память.

[Dendy]

Вот написал на колене рабочий пример. Конечно на идеальный код не претендует, но тем не менее.

Код

C++ (Qt)
static const int MaxItems = 27;
 
inline int takeAt( quint64 blob, int i )
{
	Q_ASSERT( i >= 0 && i < MaxItems );
 
	for ( ; i != 0; --i )
		blob /= 5;
	return blob % 5;
}
 
inline void putAt( quint64 & blob, int i, int value )
{
	Q_ASSERT( i >= 0 && i < MaxItems );
	Q_ASSERT( value >= 0 && value < 5 );
 
	int values[ MaxItems ] = {0};
 
	int j;
	for ( j = 0; j < i; j++ )
	{
		values[ j ] = blob % 5;
		blob /= 5;
	}
 
	blob /= 5;
	blob *= 5;
	blob += value;
 
	for ( ; j != 0; j-- )
	{
		blob *= 5;
		blob += values[ j-1 ];
	}
}
 

В 64-битное число помещается 21 октет (21*3 == 63, что меньше 64) или 27 квинтетов. Экономия памяти - 22%

[Dendy]

И даже если скорость чтения/записи упрётся в количество итераций умножения/деления - квинтеты можно хранить в 8 байтах, по 3 в каждом (3 операции умножения/деления вместо 14). Конечно тогда поместится только 24 значения, а не 27, но всё равно больше, чем 21 (-:

[niXman]

еще бы не плохо, подсчитать, во сколько раз упала производительность.

у меня вот что получилось.

Код

C++ (Qt)
#include <cctype>
#include <iostream>
 
int main() {
	const size_t sz = 1024*1024;
 
	for ( size_t i = 0; i < sz; ++i ) {
		new char;
	}
 
	std::cin.get();
 
	return 0;
}
 

как и ожидалось. для выделения массива в один байт, у ОС берется 16 байт. исходя из того, что менеджер памяти основан на двусвязном списке, все верно.
структура описывающий блок памяти примерно такая:

Код

C++ (Qt)
struct mem_block {
   struct mem_block* prev;
   struct mem_block* next;
   void* ptr;
   size_t size;
};
 

и того 16 байт.
страшно представить сколько памяти потребуется для 1024*1024 объектов QBitArray.
как мне кажется, оптимальный вариант, мемори-маппед файл и по байту для элемента.

[Dendy]

Думаю функцию бизнес-логики легко можно зашаблонить и подставлять нужный инлайновый сеттер/геттер значения: чистый байт, два октета в байте, 21 октет в int64, 3 квинтета в байте, 27 квинтетов в int64. Запустить все вместе и сравнить (-;

[Dendy]

Да, кстати, для каждого смещения квинтета можно делить/умножать сразу на константу, а не циклом, думаю прирост скорости будет существенный.

[Igors]

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

1) Да, битовый массив будет работать чуть медленнее байтового но падение скорости незначительно (особенно если не связываться с "использованием всех разрядов")

2) Да, это позволит сэкономить память значительно, но есть ли у Вас что экономить?  Паковать имеет смысл начиная примерно со 100 Mb

3) Есть ли это в Qt - не знаю. Но и своя реализация ничем не плоха, например простенько

Код:

typedef unsigned char uchar;   
struct Array3Bits {
   Array3Bits( size_t num ) : mData(0) { Alloc(num); }
 ~Array2Bits( void ) { Destroy(); }  
 
   uchar Get( size_t index ) const                { return (mData[index / 2] >> ((index & 1) ? 0 : 4)) & 7; }
   void   Set( size_t index, uchar val ) 
   { 
     uchar & t = mData[index / 2];
     if (index & 1) t = (t & 0xF8) | (val & 7);
     else t = (t & 0x8F) | ((val << 4) & 0x70);  
   }
 
private:
  void Alloc    ( size_t num )        { mData = num ? (new uchar [(num + 1) / 2]) : 0; }
  void Destroy( void )                 { if (mData) delete [] mData; }
  
// data
   uchar * mData;
};