3

ファイルから200,000レコードを読み取ってから、を使用tokenizerして文字列を解析し、各部分の前後にある引用符を削除しようとしています。ただし、実行時間は、通常の文字列の読み取りに比べて非常に長くなります。これらのレコードを読み取るだけで25秒かかりました（レコードあたり0.0001秒????）。私のプログラミングに問題はありますか、そうでない場合はこれを行うためのより速い方法がありますか？

int main()
{
    int counter = 0;
    std::string getcontent;
    std::vector<std::string> line;
    std::vector< std::vector<std::string> > lines;

    boost::escaped_list_separator<char> sep( '\\', '*', '"' ) ;
    boost::tokenizer<> tok(getcontent);

    std::ifstream openfile ("test.txt");

    if(openfile.is_open())
    {
        while(!openfile.eof())
        {
            getline(openfile,getcontent);

            // THIS LINE TAKES A LOT OF TIME
            boost::tokenizer<> tok(getcontent); 

            for (boost::tokenizer<>::iterator beg=tok.begin(); beg!=tok.end(); ++beg){
                line.push_back(*beg);
            }

            lines.push_back(line);
            line.clear();
            counter++;
        }
        openfile.close();
    }
    else std::cout << "No such file" << std::endl;

    return 0;
}
4

3 に答える 3

4

少なくともこれを正しく読んでいれば、もっとCのようなアプローチをとると思います。行を読み取ってからトークンに分割し、不要な文字を削除する代わりに、一度に1文字ずつ読み取り、読み取った文字に基づいて、現在の文字に追加するかどうかを決定します。トークン、トークンを終了して現在の行に追加するか、行を終了して行のベクトルに追加します。

#include <vector>
#include <string>
#include <stdio.h>
#include <time.h>

std::vector<std::vector<std::string> > read_tokens(char const *filename) {
    std::vector<std::vector<std::string> > lines;
    FILE *infile= fopen(filename, "r");

    int ch;

    std::vector<std::string> line;
    std::string token;

    while (EOF != (ch = getc(infile))) {
        switch(ch) {
            case '\n':
                lines.push_back(line);
                line.clear();
                token.clear();
                break;
            case '"':
                break;
            case '*':
                line.push_back(token);
                token.clear();
                break;
            default:
                token.push_back(ch);
        }
    }
    return lines;
}

int main() {
    clock_t start = clock();
    std::vector<std::vector<std::string> > lines = read_tokens("sample_tokens.txt");
    clock_t finish = clock();
    printf("%f seconds\n", double(finish-start)/CLOCKS_PER_SEC);
    return 0;
}

コメントで指定したサンプルの200Kを少し超えるコピーを含むファイルでこれを使用して簡単なテストを行うと、gccでは約3.5秒、VC ++では約4.5秒でデータが読み取られ、（明らかに）トークン化されます。何かがずっと速くなるのを見て少し驚いたでしょう（少なくともより速いハードウェアがなければ）。

余談ですが、これは元々行っていたようにメモリを処理しています。これは、（少なくとも私の意見では）ベクターでメモリを管理することがおそらく大きなボトルネックではないことを示す非常に強力な証拠です。

于 2012-09-10T03:16:50.297 に答える
2

の代わりにboost::tokenizer<> tok(getcontent);、へのboost::tokenizerすべての呼び出しを作成しgetlineます。assignメンバー関数を使用します。

boost::escaped_list_separator<char> sep( '\\', '*', '"' ) ;
boost::tokenizer<boost::escaped_list_separator<char>> tok(getcontent, sep);

// Other code
while(getline(openfile,getcontent))
{
    tok.assign(getcontent.begin(), getcontent.end()); // Use assign here
    line.assign(tok.begin(), tok.end()); // Instead of for-loop
    lines.push_back(line);
    counter++;
}

それが役立つかどうかを確認してください。また、可能であれば事前にベクトルメモリを割り当ててみてください。

于 2012-09-10T02:58:54.097 に答える
2

さて、コメントから、あなたはできるだけ速い解決策を望んでいるようです。

その要件に近い何かを達成するために私がすることは次のとおりです。

おそらくメモリプールアロケータを使って文字列を割り当てることはできますが、STLは私の強みではないので、手作業で行います。これは必ずしもC++で行う方法ではないことに注意してください。そのため、C++の頭が少ししわが寄る可能性があります。少し専門的なものが必要な場合は、これを行う必要がある場合があります。

したがって、データファイルは約10GBです...1つのブロックに割り当てるのはお勧めできません。ほとんどの場合、OSは拒否します。しかし、それをかなり大きなブロックの束に分割することは問題ありません。ここにマジックナンバーがあるかもしれませんが、約64MBとしましょう。ページングの専門家である人々はここにコメントできますか？正確なページサイズの倍数より少し小さいものを使用するのが良いことを一度読んだことを覚えています（理由は思い出せませんが）。それでは、数kBを取り除いてみましょう。

const size_t blockSize = 64 * 1048576 - 4096;

さて、あなたの記憶を追跡するための構造はどうですか？それらをすべて一緒に投げることができるように、それをリストにすることもできます。

struct Block {
    SBlock *next;
    char *data;    // Some APIs use data[1] so you can use the first element, but
                   // that's a hack that might not work on all compilers.
} SBlock;

そうです、ブロックを割り当てる必要があります。メモリの大きなチャンクを割り当て、最初の少しを使用して情報を格納します。dataメモリを調整する必要がある場合は、ポインタを変更できることに注意してください。

SBlock * NewBlock( size_t blockSize, SBlock *prev = NULL )
{
    SBlock * b = (SBlock*)new char [sizeof(SBlock) + blockSize];
    if( prev != NULL ) prev->next = b;
    b->next = NULL;
    b->data = (char*)(blocks + 1);      // First char following struct
    b->length = blockSize;
    return b;
}

今、あなたは読むつもりです...

FILE *infile = fopen( "mydata.csv", "rb" );  // Told you C++ers would hate me

SBlock *blocks = NULL;
SBlock *block = NULL;
size_t spilloverBytes = 0;

while( !feof(infile) ) {
    // Allocate new block.  If there was spillover, a new block will already
    // be waiting so don't do anything.
    if( spilloverBytes == 0 ) block = NewBlock( blockSize, block );

    // Set list head.
    if( blocks == NULL ) blocks = block;

    // Read a block of data
    size_t nBytesReq = block->length - spilloverBytes;
    char* front = block->data + spilloverBytes;
    size_t nBytes = fread( (void*)front, 1, nBytesReq, infile );
    if( nBytes == 0 ) {
        block->length = spilloverBytes;
        break;
    }

    // Search backwards for a newline and treat all characters after that newline
    // as spillover -- they will be copied into the next block.
    char *back = front + nBytes - 1;
    while( back > front && *back != '\n' ) back--;
    back++;

    spilloverBytes = block->length - (back - front);
    block->length = back - block->data;

    // Transfer that data to a new block and resize current block.
    if( spilloverBytes > 0 ) {
        block = NewBlock( blockSize, block );
        memcpy( block->data, back, spilloverBytes );
    }
}

fclose(infile);

さて、そのようなもの。あなたはジストを取得します。この時点で、を複数回呼び出すよりもかなり速くファイルを読み取った可能性があることに注意してくださいstd::getline。キャッシュを無効にできれば、さらに高速になります。Windowsでは、CreateFileAPIを使用して、実際の高速読み取り用に微調整できます。したがって、データブロックを（ディスクセクターサイズに）整列させる可能性についての私の以前のコメント。Linuxやその他のOSについてはよくわかりません。

したがって、これはファイル全体をメモリに丸呑みする一種の複雑な方法ですが、アクセス可能で適度に柔軟性があるほど単純です。うまくいけば、私はあまり多くの間違いをしませんでした。ここで、ブロックのリストを調べて、インデックスの作成を開始します。

ここではあまり詳しく説明しませんが、一般的な考え方はこれです。適切な場所でNULL値をブリットし、各トークンがどこから始まったかを追跡することにより、インプレースでトークン化します。

SBlock *block = blocks;

while( block ) {
    char *c = block->data;
    char *back = c + block->length;
    char *token = NULL;

    // Find first token
    while( c != back ) {
        if( c != '"' && c != '*' ** c != '\n' ) break;
        c++;
    }
    token = c;

    // Tokenise entire block
    while( c != back ) {
        switch( *c ) {
            case '"':
                // For speed, we assume all closing quotes have opening quotes.  If
                // we have closing quote without opening quote, this won't be correct
                if( token != c) {
                    *c = 0;
                    token++;
                }
                break;

            case '*':
                // Record separator
                *c = 0;
                tokens.push_back(token);  // You can do better than this...
                token = c + 1;
                break;

            case '\n':
                // Record and line separator
                *c = 0;
                tokens.push_back(token);  // You can do better than this...
                lines.push_back(tokens);  // ... and WAY better than this...
                tokens.clear();           // Arrrgh!
                token = c + 1;
                break;
        }

        c++;
    }

    // Next block.
    block = block->next;
}

最後に、上記のベクトルのような呼び出しが表示されます。さて、もしあなたがあなたのベクトルをメモリプールすることができれば、それは素晴らしくて簡単です。しかし、繰り返しになりますが、メモリを直接操作する方がはるかに直感的であるため、私は決してそれを行いません。ファイルチャンクで行ったのと同様のことを行うことができますが、配列（またはリスト）用のメモリを作成します。このメモリ領域にすべてのトークン（8バイトのポインタ）を追加し、必要に応じて新しいメモリチャンクを追加します。

これらのトークン配列の1つに含まれるアイテムの数を追跡する小さなヘッダーを作成することもできます。重要なのは、追加費用なしで後で計算できるものを一度計算することではありません（つまり、配列サイズ-最後の要素を追加した後でのみ計算する必要があります）。

線でも同じことをします。必要なのは、トークンチャンク内の関連部分へのポインターだけです（配列のインデックス付けが必要な場合は、行が新しいチャンクに食い込んだ場合にスピルオーバーを実行する必要があります）。

最終的には、トークンの配列を指す行の配列になります。これは、ファイルから丸呑みしたメモリを直接指します。メモリの浪費は少しありますが、おそらく過度ではありません。これは、コードを高速化するために支払う価格です。

いくつかの簡単なクラスですべてを美しくまとめることができると確信していますが、ここで生で提供しました。大量のSTLコンテナーをメモリー・プールにしたとしても、それらのアロケーターとコンテナー自体のオーバーヘッドにより、私が提供したものよりも遅くなると思います。本当に長い答えでごめんなさい。私はこのようなものを楽しんでいると思います。楽しんでください、そしてこれが役立つことを願っています。

于 2012-09-10T05:25:00.820 に答える