Самый быстрый способ заполнить надстройку :: dynamic_bitset & lt; & gt; из вектора строк

Я реализую программу, которая использует кодирование Хаффмана для сжатия файла. У меня проблемы с записью битов сжатой строки в другой набор битов. У меня есть вектор байтов (8-значные целые числа) и вектор строк huffCodes, который имеет размер 256, в котором хранятся битовые строки для каждого индекса. (Например, 0 представлен 11, 1 представлен 11011 и т. Д.)

Вот мой текущий метод:

string compressed = "";
boost::dynamic_bitset<unsigned char> output;

for(byte b : bytes)
{
compressed += huffCodes [ ByteToInt(std::to_string(b)) ];
}

output = boost::dynamic_bitset<unsigned char> (compressed);

Он проходит через каждый байт и получает соответствующую ему строку битов из вектора huffCodes, а затем добавляет эту строку в сжатую строку. Как только сжатая строка завершена, она преобразует ее в набор битов. Проблема этого метода заключается в том, что он очень медленно заполняет набор битов, потому что в моем векторе 72 миллиона байт. Мне не нравится этот метод, потому что, кажется, нет необходимости заполнять эту огромную строку, просто чтобы преобразовать ее в набор битов. Я бы предпочел что-то вроде этого:

boost::dynamic_bitset<unsigned char> output;
string temp = "";
for(byte b : bytes)
{
temp = huffCodes [ ByteToInt(std::to_string(b)) ];
output.append(temp);
}

Очевидно, что это не настоящий код, но в идеале я бы заполнил выходной набор битов, пока собираю все строки из вектора huffCodes. Возможно ли сделать это с помощью какого-либо объединения или добавления строк в набор?

Примечание: содержимое вектора huffCodes представляет собой строки размером до 8, состоящие только из 1 и 0

0

Решение

Ваше узкое место почти наверняка это линия:

compressed += huffCodes [ ByteToInt(std::to_string(b)) ];

потому что выходная строка (compressed) будет перераспределяться и копироваться много раз во время итерации цикла.

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

std::string s;
int nbytes = 0;
for (b : bytes)
nbytes += huffcodes [b].size ();

{
std::vector <char> v (nbytes + 1);
for (b : bytes)
{
auto hc = huffcodes [b];
for (auto c : hc)
v.push_back (c);
}

v.push_back (0);    // NUL terminator
s = v.data ();
}

auto output = boost::dynamic_bitset<unsigned char> (s);

Как видите, преобразование в строку выполняется за одну операцию. Обидно, что нужно копировать такую ​​большую структуру данных, но другого пути, похоже, не существует.

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector