0

スペースで区切られた 1 と 0 の文字列をすばやく変換するにはどうすればよいbitsetですか?

bitsetスペースで区切られていない文字列から a を初期化するコンストラクタ、abitsetをすべてゼロまたは 1 に初期化するコンストラクタ、および整数から初期化するコンストラクタが存在します。頭のてっぺんから、次の 3 つの方法を考えることができます。

  • 文字列からスペースを削除し、コンストラクターに渡します
  • バイナリを整数に変換してコンストラクタに渡す
  • すべての値をゼロに初期化し、for ループの文字列に従って各ビットの値を変更する

ビット数は 24 で、各文字列はちょうど 24 ビットで、それ以上でもそれ以下でもありません。

編集: パフォーマンスをテストするために使用するコードは次のとおりです。メソッド1と2のコードは次のとおりです。私のマシンでは、方法 1 に 3 ミリ秒、方法 3 に 14 ミリ秒かかります。

EDIT 2:私が使用する-O3 -o -g --std=c++11のは私のコンパイラ設定です。gccとclangを使用しました。

4

1 に答える 1

1

それに応じて各ビットを設定することによる符号なし整数への変換 (入力文字列を変更しない):

#include <bitset>
constexpr unsigned long long
extract_bits(const char* ptr, unsigned long long accumulator) {
    return (*ptr == 0)
        ? accumulator
        : extract_bits(ptr + 1, (*ptr == '1')
            ? accumulator << 1u | 1u
            : (*ptr == '0')
                ? accumulator << 1
                : accumulator);
}

template <unsigned N>
constexpr std::bitset<N>
to_bitset(const char* ptr) {
    return std::bitset<N>(extract_bits(ptr, 0));
}

#include <iostream>
int main()
{
    constexpr auto b = to_bitset<24>("0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0");
    std::cout << b << '\n';
    return 0;
}

注: 変換では、'0' と '1' 以外の文字は無視されます ("01-01" のような文字列も有効です)。

上記の変換のタイミングを取得し、文字列からスペースを消去するには:

#include <algorithm>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iostream>
#include <random>

using namespace std::chrono;

void print_duration(const char* what, const system_clock::time_point& start, const system_clock::time_point& stop) {
    auto duration = duration_cast<microseconds>(stop - start);
    std::cout << what << ": " << duration.count() << std::endl;
}

volatile unsigned long long result;
int main()
{
    std::string str = "0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0";
    std::vector<std::string> strings(1000, str);
    std::random_device random_device;
    std::mt19937 random_generator(random_device());
    for(auto& str : strings) {
        std::shuffle(str.begin(), str.end(), random_generator);
    }

    // Non mutating to_bitset
    {
        auto start = system_clock::now();
        for(const auto& str : strings) {
            auto b = to_bitset<24>(str.c_str());
            result = b.to_ullong();
        }
        auto stop = system_clock::now();
        print_duration("to_bitset", start, stop);
    }
    // Erasing spaces
    {
        auto start = system_clock::now();
        for(auto& str : strings) {
            str.erase(std::remove_if(str.begin(), str.end(), ::isspace), str.end());
            auto b = std::bitset<24>(str);
            result = b.to_ullong();
        }
        auto stop = system_clock::now();
        print_duration("str.erase", start, stop);
    }
    return 0;
}

g++ 4.8.4 with g++ -std=c++11 -O3 ショー:

to_bitsetよりも約 3 倍高速ですerasing spaces from a string/constructing a bitset。

于 2016-06-30T20:13:40.023 に答える