C++高速文字列解析？

Question

私は、このデータセットを解析するパーサを記述しようとしています：私はコードを書いたhttp://research.microsoft.com/en-us/projects/mslr/

（下）..しかし、それは遅すぎる..ですそれはデータの数百メガバイトを解析するために、ほぼ完全な分かかります。

私はプロファイラを実行し、ほとんどの時間がboost :: split（30％）とboost :: lexical_cast（40％）に費やされたと言いました...コードのスピードアップの方法はありますか？

ありがとうございました。

std::ifstream train("letor/Fold1/train.txt", std::ifstream::in | std::ifstream::binary); 

    m_train.clear(); 

    for (std::size_t i = 0; i < 10000 && train.good(); i++) { 
    std::size_t query; 
    boost::numeric::ublas::vector<double> features; 
    double label; 

    features.resize(get_feature_size(), false); 

    // 2 qid:1 1:3 2:3 3:0 4:0 5:3 6:1 7:1 8:0 9:0 10:1 11:156 12:4 13:0 14:7 15:167 16:6.931275 17:22.076928 18:19.673353 19:22.255383 20:6.926551 21:3 22:3 23:0 24:0 25:6 26:1 27:1 28:0 29:0 30:2 31:1 32:1 33:0 34:0 35:2 36:1 37:1 38:0 39:0 40:2 41:0 42:0 43:0 44:0 45:0 46:0.019231 47:0.75000 48:0 49:0 50:0.035928 51:0.00641 52:0.25000 53:0 54:0 55:0.011976 56:0.00641 57:0.25000 58:0 59:0 60:0.011976 61:0.00641 62:0.25000 63:0 64:0 65:0.011976 66:0 67:0 68:0 69:0 70:0 71:6.931275 72:22.076928 73:0 74:0 75:13.853103 76:1.152128 77:5.99246 78:0 79:0 80:2.297197 81:3.078917 82:8.517343 83:0 84:0 85:6.156595 86:2.310425 87:7.358976 88:0 89:0 90:4.617701 91:0.694726 92:1.084169 93:0 94:0 95:2.78795 96:1 97:1 98:0 99:0 100:1 101:1 102:1 103:0 104:0 105:1 106:12.941469 107:20.59276 108:0 109:0 110:16.766961 111:-18.567793 112:-7.760072 113:-20.838749 114:-25.436074 115:-14.518523 116:-21.710022 117:-21.339609 118:-24.497864 119:-27.690319 120:-20.203779 121:-15.449379 122:-4.474452 123:-23.634899 124:-28.119826 125:-13.581932 126:3 127:62 128:11089534 129:2 130:116 131:64034 132:13 133:3 134:0 135:0 136:0 
    std::string line; 
    getline(train, line); 

    boost::algorithm::trim(line); 
    std::vector<std::string> tokens; 
    boost::split(tokens, line, boost::is_any_of(" ")); 

    assert(tokens.size() == 138); 

    label = boost::lexical_cast<double>(tokens[0]); 
    query = boost::lexical_cast<std::size_t>(tokens[1].substr(tokens[1].find(":") + 1, tokens[1].size())); 

    for (std::size_t i = 2; i < tokens.size(); i++) { 
     features[i - 2] = boost::lexical_cast<double>(tokens[i].substr(tokens[i].find(":") + 1, tokens[i].size())); 
    } 

    m_train.push_back(query, features, label); 

    train.peek(); 
    } 

Answer 1

フォーマットが正しく理解されている場合、各行は数字とコロンで区切られたペアで始まります。各行の最初のペアは特別な意味を持ち、std::stringとsize_tで構成され、他のすべてのペアはインデックス（無視されます）とdoubleから構成されます。直接入出力ストリームを使用します：

std::streamsize max(std::numeric_limits<std::streamsize>::max()); 
std::string  line; 
std::istringstream in; 
for (std::size_t i(0); i < 1000 && std::getline(train, line); ++i) { 
    double label; 
    size_t query; 
    in.clear(); 
    in.str(line) 
    if ((in >> label).ignore(max, ':') >> query) { 
     boost::numeric::ublas::vector<double> features; 
     while (in.ignore(max, ':') >> feature) { 
       features.push_back(feature); 
     } 
     assert(features.size() == 136); 
     m_train.push_back(query, features, label); 
    } 
} 

注このコードは、それが実際に成功している読み込みチェックする慎重であることで、このすべてのためにブーストを使用する理由はありません。読み込みが成功するかどうかを事前にチェックしていますが、これは確実に機能しません。たとえば、最後の行が偽のスペースだけで構成されている場合は、assert()がトリガーとなります。これはほとんどあなたが望むものではありません。

Answer 2

これは、いくつかの実験をせずに言うのは難しいですが、...

私はboost::splitをドロップすることによって開始すると思います。 std::vector<std::string>を作成しています。これには、多くの動的な割り当てとコピーがあります。 おそらくあなたがしたいことは、++が次のトークンに進む文字列に何らかの並べ替えを書きます。 *は、現在のトークンを定義するイテレータのペアを返します。これにより、中間データ構造 が回避されます。より困難になりますboost::lexical_castによって使用される時間を削減

std::ostream& 
operator<<(std::ostream& dest, TextRange const& token) 
{ 
    std::copy(token.begin(), token.end(), 
       std::ostream_iterator<char>(dest)); 
    return dest; 
} 

：

あなたは、その後、このペアのようなものを<<演算子を定義することができます。 boost::lexical_castは、ソースを のstd::stringstreamに、そして>>にソースを挿入するために<<を使用しています。 と似ていますが、独自のstreambufを使用して、イテレータのペアに基づいて （非常に単純）を指定すると、イテレータのペアを指定すると、1） <<を使用する必要はありません。イテレータはistreamになります.2） は、中間のいずれかを完全に作成しないようにします。std::string （あなたが ないがstd::istreamに変換ルーチンを再実装したいです。）

Answer 3

文字列を複数回チョッピングメモリの割り当てと割り当て解除が必要です。あなたは良い古いstrtodと文字列を分割しないようにするためのcharポインタを使うことができます。これは、文字列トークン化の30％の支出をいくらか配慮します。刺すようにダブルに変換する40％については、これは大幅に改善することはできません。

クイックで汚れていて驚くほど醜いが、おそらく最も速いC専用のソリューションを試したい場合は、これを試してみてください。このテストは、E8300 2.83 GHz CPUで約35秒で完了しました。すべての文字列がまったく同じ形式であると仮定します。

#include "stdio.h" 

void main() 
{ 
    const char* test_str = "2 qid:1 1:3 2:3 3:0 4:0 5:3 6:1 7:1 8:0 9:0 10:1 11:156 12:4 13:0 14:7 15:167 16:6.931275 17:22.076928 18:19.673353 19:22.255383 20:6.926551 21:3 22:3 23:0 24:0 25:6 26:1 27:1 28:0 29:0 30:2 31:1 32:1 33:0 34:0 35:2 36:1 37:1 38:0 39:0 40:2 41:0 42:0 43:0 44:0 45:0 46:0.019231 47:0.75000 48:0 49:0 50:0.035928 51:0.00641 52:0.25000 53:0 54:0 55:0.011976 56:0.00641 57:0.25000 58:0 59:0 60:0.011976 61:0.00641 62:0.25000 63:0 64:0 65:0.011976 66:0 67:0 68:0 69:0 70:0 71:6.931275 72:22.076928 73:0 74:0 75:13.853103 76:1.152128 77:5.99246 78:0 79:0 80:2.297197 81:3.078917 82:8.517343 83:0 84:0 85:6.156595 86:2.310425 87:7.358976 88:0 89:0 90:4.617701 91:0.694726 92:1.084169 93:0 94:0 95:2.78795 96:1 97:1 98:0 99:0 100:1 101:1 102:1 103:0 104:0 105:1 106:12.941469 107:20.59276 108:0 109:0 110:16.766961 111:-18.567793 112:-7.760072 113:-20.838749 114:-25.436074 115:-14.518523 116:-21.710022 117:-21.339609 118:-24.497864 119:-27.690319 120:-20.203779 121:-15.449379 122:-4.474452 123:-23.634899 124:-28.119826 125:-13.581932 126:3 127:62 128:11089534 129:2 130:116 131:64034 132:13 133:3 134:0 135:0 136:0"; 

    const char* format = "%lf qid:%lf 1:%lf 2:%lf 3:%lf 4:%lf 5:%lf 6:%lf 7:%lf 8:%lf 9:%lf 10:%lf 11:%lf 12:%lf 13:%lf 14:%lf 15:%lf 16:%lf 17:%lf 18:%lf 19:%lf 20:%lf 21:%lf 22:%lf 23:%lf 24:%lf 25:%lf 26:%lf 27:%lf 28:%lf 29:%lf 30:%lf 31:%lf 32:%lf 33:%lf 34:%lf 35:%lf 36:%lf 37:%lf 38:%lf 39:%lf 40:%lf 41:%lf 42:%lf 43:%lf 44:%lf 45:%lf 46:%lf 47:%lf 48:%lf 49:%lf 50:%lf 51:%lf 52:%lf 53:%lf 54:%lf 55:%lf 56:%lf 57:%lf 58:%lf 59:%lf 60:%lf 61:%lf 62:%lf 63:%lf 64:%lf 65:%lf 66:%lf 67:%lf 68:%lf 69:%lf 70:%lf 71:%lf 72:%lf 73:%lf 74:%lf 75:%lf 76:%lf 77:%lf 78:%lf 79:%lf 80:%lf 81:%lf 82:%lf 83:%lf 84:%lf 85:%lf 86:%lf 87:%lf 88:%lf 89:%lf 90:%lf 91:%lf 92:%lf 93:%lf 94:%lf 95:%lf 96:%lf 97:%lf 98:%lf 99:%lf 100:%lf 101:%lf 102:%lf 103:%lf 104:%lf 105:%lf 106:%lf 107:%lf 108:%lf 109:%lf 110:%lf 111:%lf 112:%lf 113:%lf 114:%lf 115:%lf 116:%lf 117:%lf 118:%lf 119:%lf 120:%lf 121:%lf 122:%lf 123:%lf 124:%lf 125:%lf 126:%lf 127:%lf 128:%lf 129:%lf 130:%lf 131:%lf 132:%lf 133:%lf 134:%lf 135:%lf 136:%lf"; 

    double data[138]; 

    for (int i = 0; i < 500000; i++) 
    { 
     sscanf(test_str, format, 
      data+0, data+1, data+2, data+3, data+4, data+5, 
      data+6, data+7, data+8, data+9, data+10, data+11, 
      data+12, data+13, data+14, data+15, data+16, data+17, 
      data+18, data+19, data+20, data+21, data+22, data+23, 
      data+24, data+25, data+26, data+27, data+28, data+29, 
      data+30, data+31, data+32, data+33, data+34, data+35, 
      data+36, data+37, data+38, data+39, data+40, data+41, 
      data+42, data+43, data+44, data+45, data+46, data+47, 
      data+48, data+49, data+50, data+51, data+52, data+53, 
      data+54, data+55, data+56, data+57, data+58, data+59, 
      data+60, data+61, data+62, data+63, data+64, data+65, 
      data+66, data+67, data+68, data+69, data+70, data+71, 
      data+72, data+73, data+74, data+75, data+76, data+77, 
      data+78, data+79, data+80, data+81, data+82, data+83, 
      data+84, data+85, data+86, data+87, data+88, data+89, 
      data+90, data+91, data+92, data+93, data+94, data+95, 
      data+96, data+97, data+98, data+99, data+100, data+101, 
      data+102, data+103, data+104, data+105, data+106, data+107, 
      data+108, data+109, data+110, data+111, data+112, data+113, 
      data+114, data+115, data+116, data+117, data+118, data+119, 
      data+120, data+121, data+122, data+123, data+124, data+125, 
      data+126, data+127, data+128, data+129, data+130, data+131, 
      data+132, data+133, data+134, data+135, data+136, data+137); 
    } 
} 

C99は、見た目が良くなります。フォーマット文字列は、データセット形式に応じて、ループの前に一度動的に事前生成することができます。このサンプルでは、​​sscanfの戻り値が正確に138であることを確認してください。

EDIT：DietmarKühlのソリューションはきれいに見えますが、1つのsscanfよりも遅い場合はそれほど重要ではありません。上のコードは、ベンチマーク参照としてのみ使用してください。