4

パフォーマンスを低下させない方法で、大きなビットセットと小さなビットセットを連結したいと思います。現在、私のアプリケーションは、次のコードだけでCPU時間の20％を費やしています。

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

解決策を提案するこの投稿を読みましたが、宛先ビットセットとソースビットセットのサイズのサイズの差が非常に大きいため、残念ながら機能しません。

何か案は？

これがboost::dynamic_bitsetで効率的に行うことができない場合、私は他の提案を受け入れています。

4

3 に答える 3

1

使い続けているからですpush_back()が、実は事前にサイズを知っているはずです。これは、多くの冗長なコピーと再割り当てを意味します。最初にサイズを変更する必要があります。さらに、すべての値を指定する必要はありません。何らかの形式（正確なインターフェイスかどうかはわかりませんが、名前だと思います）を使用して、ターゲットベクトル全体を一度に挿入push_back()できるはずです。これは大幅に改善されるはずです。insert()append()

さらに、あなたはdynamic_bitset署名されていない長いままにしておきますが、私が見る限り、あなたは実際にそれに挿入unsigned charしているだけです。それを変えることであなたの生活が楽になるかもしれません。

また、タイプが何であるかについても興味があります。codes_それがaの場合は、静的配列の静的なサイズ（256エントリはの最大値）であるため、または実際にmap置き換えることができます。vectorunsigned char

于 2011-04-23T19:51:29.950 に答える
0

以前にパフォーマンスコードでブーストビットセットを使用してみましたが、がっかりしました。私はそれを少し掘り下げて、自分のビットバッファクラスを実装する方が良いと結論付けましたが、ブーストのクラスが決して速くなることはないと確信したことの詳細を忘れています（アセンブリを検査するところまでは行きました生成された）。

ビットバッファ/ビットセット/ビットストリームを構築する最速の方法、またはそれらを呼び出したいものが何であるかはまだわかりません。同僚がこの関連する質問を見つけようとしていますが、執筆時点ではまだ良い答えを待っています。

于 2011-04-23T18:29:15.120 に答える
0

私は自分のビットセットクラスを書きました。改善のための提案に感謝します。SSEを調べて、そこに役立つものがあるかどうかを確認します。

非常に大まかなベンチマークでは、一度に6ビットを追加しながら、パフォーマンスが11倍向上しました。

class fast_bitset
{
public:
    typedef unsigned long block_type;
    static const size_t bits_per_block = sizeof(block_type)*8;

    fast_bitset() 
        : is_open_(true)
        , blocks_(1)
        , space_(blocks_.size()*bits_per_block){}

    void append(const fast_bitset& other)
    {
        assert(!other.is_open_);

        for(size_t n = 0; n < other.blocks_.size()-1; ++n)
            append(other.blocks_[n], bits_per_block);
        append(other.blocks_.back() >> other.space_, bits_per_block - other.space_);
    }

    void append(block_type value, size_t n_bits)
    {
        assert(is_open_);
        assert(n_bits < bits_per_block);

        if(space_ < n_bits)
        {
            blocks_.back() = blocks_.back() << space_;
            blocks_.back() = blocks_.back() | (value >> (n_bits - space_));
            blocks_.push_back(value);
            space_ = bits_per_block - (n_bits - space_);
        }
        else
        {
            blocks_.back() = blocks_.back() << n_bits;
            blocks_.back() = blocks_.back() | value;
            space_ -= n_bits;
        }
    }

    void push_back(bool bit)
    {
        append(bit, 1);
    }

    bool operator[](size_t index) const
    {
        assert(!is_open_);

        static const size_t high_bit = 1 << (bits_per_block-1);
        const size_t block_index = index / bits_per_block;
        const size_t bit_index = index % bits_per_block;
        const size_t bit_mask = high_bit >> bit_index;
        return blocks_[block_index] & bit_mask;
    }

    void close()
    {
        blocks_.back() = blocks_.back() << space_;
        is_open_ = false;
    }

    size_t size() const
    {
        return blocks_.size()*bits_per_block-space_;
    }

    const std::vector<block_type>& blocks() const {return blocks_;}

    class reader
    {
    public:
        reader(const fast_bitset& bitset) 
            : bitset_(bitset)
            , index_(0)
            , size_(bitset.size()){}
        bool next_bit(){return bitset_[index_++];}
        bool eof() const{return index_ >= size_;}
    private:
        const fast_bitset& bitset_;
        size_t index_;
        size_t size_;
    };

private:
    bool is_open_;
    std::vector<block_type> blocks_;
    size_t space_;
};
于 2011-04-23T20:55:36.607 に答える