Самый быстрый способ заполнить boost :: dynamic_bitset <> из вектора строк - PullRequest
Новая
       29

Самый быстрый способ заполнить boost :: dynamic_bitset <> из вектора строк

0 голосов
/ 03 декабря 2018

Я реализую программу, которая использует кодировку Хаффмана для сжатия файла.У меня проблемы с записью битов сжатой строки в другой набор битов.У меня есть вектор байтов (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

1 Ответ

0 голосов
/ 03 декабря 2018

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

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);

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

...