26

そのファイルに対して何らかの操作を行う前に、ファイルの行数を読み取る必要があります。ファイルを読み取ろうとすると、eof に到達するまで各反復で line_count 変数をインクリメントします。私の場合はそれほど速くはありませんでした。ifstream と fgets の両方を使用しました。どちらも遅かった。これを行うためのハッキーな方法はありますか。これは、たとえば BSD、Linux カーネル、または berkeley db でも使用されます (ビット単位の操作を使用する場合があります)。

前に言ったように、そのファイルには何百万もの行があり、サイズが大きくなり続けています。各行は約 40 または 50 文字です。私はLinuxを使用しています。

注: DB ばかを使用すると言う人がいると思います。しかし、簡単に言えば、私の場合、データベースを使用できません。

4

8 に答える 8

17

行数を見つける唯一の方法は、ファイル全体を読み取り、行末文字の数を数えることです。これを行う最も速い方法は、おそらく、1 回の読み取り操作でファイル全体を大きなバッファーに読み取り、次にバッファーを調べて '\n' 文字をカウントすることです。

現在のファイル サイズは約 60Mb であるため、これは魅力的なオプションではありません。ファイル全体を読み取るのではなく、チャンクで読み取ることで、ある程度の速度を得ることができます。たとえば、サイズは 1Mb です。また、データベースは問題外だとおっしゃっていますが、長期的には最善のソリューションのように見えます。

編集：これについて小さなベンチマークを実行したところ、バッファリングされたアプローチ（バッファサイズ1024K）を使用すると、getline（）で一度に1行読むよりも2倍以上速いようです。これがコードです - 私のテストは -O2 最適化レベルを使用して g++ で行われました:

#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>
using namespace std;

unsigned int FileRead( istream & is, vector <char> & buff ) {
    is.read( &buff[0], buff.size() );
    return is.gcount();
}

unsigned int CountLines( const vector <char> & buff, int sz ) {
    int newlines = 0;
    const char * p = &buff[0];
    for ( int i = 0; i < sz; i++ ) {
        if ( p[i] == '\n' ) {
            newlines++;
        }
    }
    return newlines;
}

int main( int argc, char * argv[] ) {
    time_t now = time(0);
    if ( argc == 1  ) {
        cout << "lines\n";
        ifstream ifs( "lines.dat" );
        int n = 0;
        string s;
        while( getline( ifs, s ) ) {
            n++;
        }
        cout << n << endl;
    }
    else {
        cout << "buffer\n";
        const int SZ = 1024 * 1024;
        std::vector <char> buff( SZ );
        ifstream ifs( "lines.dat" );
        int n = 0;
        while( int cc = FileRead( ifs, buff ) ) {
            n += CountLines( buff, cc );
        }
        cout << n << endl;
    }
    cout << time(0) - now << endl;
}
于 2009-05-09T11:37:24.540 に答える
11

C++ stl 文字列およびgetline(または C の fgets) を使用しないでください。C スタイルの raw ポインターのみを使用し、ページ サイズのチャンクでブロック読み取りを行うか、ファイルを mmap します。

次に、ワード内のバイトをテストするための魔法のアルゴリズム「レジスタ内の SIMD (SWAR) 操作」の1 つを使用して、システムのネイティブ ワード サイズ (つまり、 または のいずれuint32_tかuint64_t)でブロックをスキャンします。例はここにあります; を含むループは、改行をスキャンします。(そのコードは、ファイルの各行の正規表現に一致する入力バイトごとに約 5 サイクルになります)0x0a0a0a0a0a0a0a0aLL

ファイルが数十または 100 メガバイトにすぎず、成長し続ける (つまり、何かが書き込みを続ける) 場合、Linux がそのファイルをメモリにキャッシュしている可能性が高いため、ディスク IO が制限されることはありません。 、しかしメモリ帯域幅は限られています。

ファイルが追加されるだけの場合は、行数と以前の長さを覚えておいて、そこから開始することもできます。

C++ stl アルゴリズムで mmap を使用し、std::foreach に渡すファンクタを作成できることが指摘されています。そのようにできないからではなく、そうすべきではないことを提案しましたが、そうするために余分なコードを書くことには何のメリットもありません。または、boost の mmaped イテレータを使用して、すべてを処理することもできます。しかし、私がリンクしたコードがこれのために書かれた問題については、はるかに遅く、問題はスタイルではなく速度に関するものでした。

于 2009-05-09T11:38:04.213 に答える
4

すべての fstream がバッファリングされることに注意してください。したがって、実際にはチャンクで実際に読み取るため、この機能を再作成する必要はありません。したがって、バッファをスキャンするだけです。ただし、getline() は使用しないでください。文字列のサイズを変更する必要があります。したがって、STL の std::count およびストリーム イテレータを使用するだけです。

#include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>


struct TestEOL
{
    bool operator()(char c)
    {
        last    = c;
        return last == '\n';
    }
    char    last;
};

int main()
{
    std::fstream  file("Plop.txt");

    TestEOL       test;
    std::size_t   count   = std::count_if(std::istreambuf_iterator<char>(file),
                                          std::istreambuf_iterator<char>(),
                                          test);

    if (test.last != '\n')  // If the last character checked is not '\n'
    {                       // then the last line in the file has not been 
        ++count;            // counted. So increement the count so we count
    }                       // the last line even if it is not '\n' terminated.
}
于 2009-05-09T19:16:42.750 に答える
3

アルゴリズムが原因で遅いのではなく、IO 操作が遅いため遅いのです。ファイルを順番に処理する単純な O(n) アルゴリズムを使用していると思います。その場合、プログラムを最適化できるより高速なアルゴリズムはありません。

ただし、より高速なアルゴリズムはないと言いましたが、「メモリ マップ ファイル」と呼ばれるより高速なメカニズムがあります。マップ ファイルにはいくつかの欠点があり、場合によっては適切ではない可能性があります。そのため、それについて読む必要があります。と自分で判断してください。

メモリ マップ ファイルでは、O(n) よりも優れたアルゴリズムを実装することはできませんが、IO アクセス時間が短縮される可能性があります。

于 2009-05-09T11:37:23.403 に答える
3

ファイル全体をスキャンして改行文字を探すことによってのみ、決定的な答えを得ることができます。それを回避する方法はありません。

ただし、考慮したい可能性がいくつかあります。

1/ 単純なループを使用している場合、一度に 1 文字を読み取って改行をチェックするのはやめてください。I/O がバッファリングされている場合でも、関数呼び出し自体は時間的にコストがかかります。

より良いオプションは、ファイルの大きなチャンク (5M など) を 1 回の I/O 操作でメモリに読み込み、それを処理することです。C ランタイム ライブラリはとにかく最適化されるため、特別なアセンブリ命令についてあまり心配する必要はおそらくないでしょうstrchr()。

2/ 一般的な行の長さが約 40 ～ 50 文字であり、正確な行数が必要ない場合は、ファイル サイズを取得して 45 (または使用すると思われる平均値) で割ります。

3/ これがログ ファイルのようなもので、1 つのファイルに保存する必要がない場合 (システムの他の部分で再作業が必要になる場合があります)、ファイルを定期的に分割することを検討してください。

たとえば、5M になったらx.log、日付の付いたファイル名 (たとえば ) に移動しx_20090101_1022.log、その時点で何行あるかを計算します ( に格納してx_20090101_1022.countから、新しいx.logログ ファイルを開始します。 ログの特性ファイルは、作成されたこの日付のセクションが変更されないことを意味するため、行数を再計算する必要はありません。

ログ「ファイル」を処理するにcat x_*.logは、cat x.log. 「ファイル」の行数を取得するwc -lには、現在の x.log に対して a を実行し (比較的高速)、それをx_*.countファイル内のすべての値の合計に追加します。

于 2009-05-09T12:10:25.450 に答える
1

時間がかかるのは、40 MB 以上をメモリにロードすることです。これを行う最も速い方法は、メモリマップするか、一度に大きなバッファにロードすることです。何らかの方法でメモリに格納すると、文字を探してデータを横断するループ\nは、実装方法に関係なく、ほぼ瞬時に実行されます。

つまり、最も重要な秘訣は、ファイルをできるだけ速くメモリにロードすることです。そして、それを行う最も速い方法は、単一の操作として行うことです。

それ以外の場合は、アルゴリズムを高速化するための多くのトリックが存在する可能性があります。行が追加されるだけで、変更も削除もされず、ファイルを繰り返し読み取る場合は、以前に読み取った行をキャッシュし、次にファイルを読み取る必要があるときに、新しく追加された行のみを読み取ることができます。

または、既知の '\n' 文字の位置を示す別のインデックス ファイルを維持して、ファイルのそれらの部分をスキップできるようにすることもできます。

ハードドライブから大量のデータを読み取るのは遅いです。それを回避する方法はありません。

于 2009-05-09T12:16:09.877 に答える