6

この関数は、文字列から double の配列を読み取ります。

vector<double> parseVals(string& str) {
    stringstream ss(str);
    vector<double> vals;
    double val;
    while (ss >> val) vals.push_back(val);
    return vals;
}

100 万個の数字を含む文字列で呼び出すと、関数の実行に 7.8 秒かかります (Core i5、3.3GHz)。これは、1 つの数値を解析するために 25000 の CPU サイクルが費やされることを意味します。

user315052 は、同じコードが彼のシステムで桁違いに高速に実行されることを指摘しており、さらにテストを行ったところ、異なるシステムやコンパイラ間で非常に大きなパフォーマンスの違いが示されました (user315052 の回答も参照してください)。

1. Win7, Visual Studio 2012RC or Intel C++ 2013 beta: 7.8  sec
2. Win7, mingw / g++ 4.5.2                          : 4    sec
3. Win7, Visual Studio 2010                         : 0.94 sec
4. Ubuntu 12.04, g++ 4.7                            : 0.65 sec

Boost/Spirit ライブラリで優れた代替手段を見つけました。コードは安全で、簡潔で、非常に高速です (VC2012 では 0.06 秒、stringstream よりも 130 倍高速です)。

#include <boost/spirit/include/qi.hpp>

namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;

vector<double> parseVals4(string& str) {
    vector<double> vals;
    qi::phrase_parse(str.begin(), str.end(),
        *qi::double_ >> qi::eoi, ascii::space, vals);
    return vals;
}

これにより、実用的な観点からは問題が解決されますが、stringstream のパフォーマンスが一貫していない理由を知りたいと思います。ボトルネックを特定するためにプログラムのプロファイルを作成しましたが、STL コードは意味不明に見えます。STL の内部構造に詳しい方からのコメントをお待ちしております。

PS: 最適化は、上記のすべてのタイミングで O2 以上です。プログラム プロファイルでの stringstream のインスタンス化もベクトル図の再割り当てもありません。ほとんどの時間は、抽出オペレーター内で費やされます。

4

5 に答える 5

5

1.6 GHz の i7 で実行されている Linux VM では、0.5 秒もかかりません。私の結論は、解析はあなたが観察しているほど遅くはないということです。あなたの観察結果が私のものと大きく異なる原因となっているのは、あなたが測定している他のアーティファクトであるに違いありません。リンゴとリンゴを比較していることをより確実にするために、私が行ったことを提供します.

編集:私の Linux システムでは、g++4.6.3 を でコンパイルしまし-O3た。私は MS や Intel のコンパイラを持っていないのでg++、同じく でコンパイルされた cygwin 4.5.3を使用しまし-O3た。Linux では、次の出力が得られました。もう 1 つの事実は、Windows 7 が 64 ビットであり、Linux VM も同様です。cygwin は 32 ビット モードでしか動作しないと思います。

elapsed: 0.46 stringstream
elapsed: 0.11 strtod

cygwin では、次のようになりました。

elapsed: 1.685 stringstream
elapsed: 0.171 strtod

cygwin と Linux のパフォーマンスの違いは、MS ライブラリの依存関係と関係があると推測しています。cygwin 環境は Linux VM のホスト マシン上にあることに注意してください。

これは、私が時間を計測したルーチンですistringstream。

std::vector<double> parseVals (std::string &s) {
    std::istringstream ss(s);
    std::vector<double> vals;
    vals.reserve(1000000);
    double val;
    while (ss >> val) vals.push_back(val);
    return vals;
}

これは、私が時間を計測したルーチンですstrtod。

std::vector<double> parseVals2 (char *s) {
    char *p = 0;
    std::vector<double> vals;
    vals.reserve(1000000);
    do {
        double val = strtod(s, &p);
        if (s == p) break;
        vals.push_back(val);
        s = p+1;
    } while (*p);
    return vals;
}

これは、文字列に 100 万個の double を設定するために使用したルーチンです。

std::string one_million_doubles () {
    std::ostringstream oss;
    double x = RAND_MAX/(1.0 + rand()) + rand();
    oss << x;
    for (int i = 1; i < 1000000; ++i) {
        x = RAND_MAX/(1.0 + rand()) + rand();
        oss << " " << x;
    }
    return oss.str();
}

これは、タイミングを行うために使用したルーチンです。

template <typename PARSE, typename S>
void time_parse (PARSE p, S s, const char *m) {
    struct tms start;
    struct tms finish;
    long ticks_per_second;
    std::vector<double> vals_vec;

    times(&start);
    vals_vec = p(s);
    times(&finish);
    assert(vals_vec.size() == 1000000);
    ticks_per_second = sysconf(_SC_CLK_TCK);
    std::cout << "elapsed: "
              << ((finish.tms_utime - start.tms_utime
                   + finish.tms_stime - start.tms_stime)
                  / (1.0 * ticks_per_second))
              << " " << m << std::endl;
}

そして、これはmain関数でした：

int main ()
{
    std::string vals_str;

    vals_str = one_million_doubles();
    std::vector<char> s(vals_str.begin(), vals_str.end());

    time_parse(parseVals, vals_str, "stringstream");
    time_parse(parseVals2, &s[0], "strtod");
}
于 2012-07-12T06:45:33.480 に答える
2

オーバーヘッドは、インスタンス化の繰り返しstd::stringstreamと解析自体の両方にあります。数値が単純で、ロケールに依存する書式設定を使用していない場合は、 と をお勧め#include <cstdlib>しstd::strtod()ます。

于 2012-07-12T06:02:32.770 に答える
1

stringCorei5 CPUにdoubleはその変換演算子が組み込まれていないため、変換が遅くなります。

そのCPUは比較的高速でashortをaにfloatネイティブに変換できますが、説明する変換は段階的に実行し、各文字を分析して、それがの一部であるかどうか、およびどのように決定するかを決定する必要があります。intdouble

-.0各 double がorINFまたは4E6orのように見えることを考慮して、観察しているのは、実行する必要がある実際の作業を表しています-NAN。切り詰める必要があるかもしれませんし、概算する必要があるかもしれませんしdouble、まったく有効でないかもしれません。

于 2012-07-12T06:16:10.860 に答える
0

これは、解析にとってかなり複雑なタスクです。double を解析するには、10 進数または浮動小数点数のいずれかに一致する必要があり、この文字列を抽出して実際の文字列変換を行う必要があります。これは、文字列内の各 double に対して、各 double を少なくとも 2 回調べ、さらに次の double に到達するために行われる他の機能を実行することを意味します。前述の他の部分は、サイズ変更時のベクトルは最も効率的ではないということです。ただし、文字列の解析と変換が遅いだけです。

于 2012-07-12T06:09:34.623 に答える
0

stringstreamその関数を呼び出すたびにオブジェクトを構築しますが、これは非常に高価になる可能性があります。

しかし、あなたの質問に答えるのに十分な情報がありません。最適化を常にオンにしてコンパイルしていますか? あなたの関数はインライン化されていますか、それともすべての呼び出しで関数呼び出しがありますか?

物事をスピードアップする方法に関する提案については、検討する必要がありますboost::lexical_cast<double>(str)

于 2012-07-13T04:01:44.950 に答える