c++ - boost::dynamic_bitset 连接性能

Question

我想以一种不会降低性能的方式连接一个大的位集和一个较小的位集。目前，我的应用程序仅在以下代码中就花费了 20% 的 CPU 时间:

boost::dynamic_bitset<> encode(const std::vector<char>& data)
{
    boost::dynamic_bitset<> result;

    std::for_each(data.begin(), data.end(), [&](unsigned char symbol)
    {
        for(size_t n = 0; n < codes_[symbol].size(); ++n)
            result.push_back(codes_[symbol][n]); // codes_[symbol][n].size() avarage ~5 bits
    });
    return result;
}

我读过这个post它提出了一个解决方案，不幸的是，它对我不起作用，因为目标位集和源位集的大小差异非常大。

有什么想法吗？

如果使用 boost::dynamic_bitset 无法有效地做到这一点，那么我愿意接受其他建议。

Answer 1

这是因为你一直在使用push_back()，但实际上你已经提前知道大小了。这意味着大量的冗余复制和重新分配。你应该先调整它的大小。此外，您不必 push_back() 每个值 - 您应该可以使用某种形式的 insert() (我实际上并不知道这是确切的接口(interface)，但我认为 append() 是一次插入整个目标 vector 的名称)，这应该会好得多。

此外，您将 dynamic_bitset 保留为 unsigned long，但据我所知，您实际上只是将 unsigned char 插入其中。改变这一点可以让您的生活更轻松。

我也很好奇 codes_ 是什么类型 - 如果它是 map 你可以用 vector 替换它，或者事实上因为它的静态大小最大(256 个条目是 unsigned char 的最大值)，所以是一个静态数组。