lundi 6 avril 2015

Packing integers close together in a vector - can it be done faster?

For the data structure I'm currently making, I need to pack the integers closely together. This means, that if the maximum element in a vector is n, I would use at most lg n bits to represent it. Thus, I treat a vector of integers like a list of bits. My current solution works just fine - but I need to know if I can speed up the unpacking of an integer. That lookup operation is a quite integral part of the search query to my data structure.



// uint is an unsigned 32 bit integer (std::uint32_t)
uint
Data::findInt(const std::vector<uint>& input, int size, int pos) {
pos = pos*size;
int end = pos+size;
int firstc = pos/32;
int secondc = end/32;
int ipos = pos % 32;
int jpos = end % 32;

if(firstc == secondc) {
uint number = input.at(firstc);
number = number >> (32 - end);
number = number & ((1 << size) - 1);
return number;
}
// else
uint number = input.at(firstc);
number = number << (jpos);
number = number & ((1 << size) -1);
uint number2 = input.at(secondc);
number2 = number2 >> (32 - jpos);
number2 = number2 & ((1 << jpos) - 1);

return number + number2;
}

std::vector<uint>
Data::packBits(const std::vector<uint>& input, int size) {

std::vector<char> bits = translatetobits(input, size);
while(bits.size() % 32 != 0) {
bits.push_back(0);
}

std::vector<uint> packedbits;
for(int i = 0; i < bits.size(); i += 32) {
uint res = 0;
for(int j = 0; j < 31; ++j) {
res += (bits.at(i+j));
res = res << 1;
}
res += (bits.at(i+31));
packedbits.push_back(res);
}

// Current lookup requires an empty entry - should be fixed
packedbits.push_back(0);

return packedbits;
}


I can only fetch one integer at a time and the index of a look-up operation jumps quite arbitrarily around, so I can't batch look-ups together. Does anyone have a good idea for speeding up the look-up?


Aucun commentaire:

Enregistrer un commentaire