4

私はファイルから巨大なデータを次のように読んでいます：

//abc.txt

10  12  14  15  129

-12 14 -18  -900 -1234

145 12 13
12

32 68 51 76 -59 -025 

- - - - etc

fun(char *p, int x, int y, int z) {

}

atoi、を使用しようとしましstrtokたが、配列が大きすぎてsscanf非常に遅い場合、リアルタイムで時間がかかります。

巨大なデータのパフォーマンスを向上させるにはどうすればよいですか？

strtok解析に使用しています。各行を解析するための高速な方法を探しています。

私は各行として読んでから、各行を次のように解析しています。

 char * ptr;
 ptr = strtok (str," ");
 while (ptr != NULL)
 {
    int value1 = atoi(ptr) ;
    ptr = strtok (NULL, " ");
 }
  • 文字列を解析して変換する高速な方法はありますintか？
  • 上記のコードよりも高速な代替アプローチはありますか？atoiに変換するために使用しchar *ていますint。
  • 他の高速な方法を使用して変換char *できintますか？
4

5 に答える 5

3

あなたは間違った場所を見ています。本当に奇妙なことをしていない限り、問題は解析ではありません。最新の N Ghz CPU では、1 行に必要なサイクルはごくわずかです。パフォーマンスを低下させるのは物理 I/O です。回転するものは 10 秒 / 秒で実行される傾向があります。

また、問題はファイル システム キャッシュに効率的にキャッシュされるため、ファイルの物理的な読み取りであるとは思えません。

いいえ、samy.vilarが示唆しているように、問題はほぼ確実に仮想メモリの問題です。

...配列が大きすぎます...

システム モニター/psinfo/top を使用してアプリを確認します。ほぼ確実に、メモリ内配列を構築し、OS がこれをディスクにページングしているため、大きなワーキング セットが成長しています。

したがって、問題として読むことを忘れてください。あなたの本当の問題は、メモリ内の巨大なデータセットを操作する方法です。ここでのアプローチはさまざまです。

  • しないでください。データをバッチ処理し、バッチを操作します。
  • スペース効率の良いストレージを使用してください (コンパクトな要素など)。
  • より多くのメモリ リソースを割り当てます。

これについては、SO に関する多くの議論があります。

于 2012-06-18T09:22:10.240 に答える
3

ASCII 文字列を整数値に変換する場合、実行しているものよりもはるかに高速になることatoiはありませんが、インラインで使用する変換関数を実装することで高速化できる場合があります。以下のバージョンでは、スキャンされた数字を超えてポインターがインクリメントされるため、セマンティクスは一致しませんatoiが、以下に示すように、パーサーの効率を向上させるのに役立つはずです。（エラーチェックは明らかに不足しているので、必要に応じて追加してください。）

static inline int my_parsing_atoi(const char *&s) {
    if (s) {
        bool neg = false;
        int val = 0;
        if (*s == '-') { neg = true; ++s; }
        for (;isdigit(*s);++s) val = 10*val + (*s - '0');
        return neg ? -val : val;
    }
    return 0;
}

const char *p = input_line;
if (p) {
    p += strspn(p, " ");
    while (*p) {
        int value1 = my_parsing_atoi(p);
        p += strspn(p, " ");
    }
}

ルーチンが I/O バウンドではなく計算バウンドであることを確認できるように、コードを適切にプロファイリングしたことを確認してください。ほとんどの場合、I/O バウンドになりますが、以下の提案はそれを軽減する方法です。

freadまたは などの CまたはC++ ファイル読み取りルーチンを使用している場合、fstreamバッファリングされた読み取りを取得する必要がありますが、これはすでにかなり効率的であるはずですが、 POSIX などの基になる OS 呼び出しを使用してread、より大きなブロックでファイルを読み取ることができます。一度にファイルの読み取り効率を高速化します。非常に凝った方法として、スレッドを使用するか、aio_read. . _ mmap_ munmap_mmap

上記の解析ルーチンと、次のようなコードを使用して OP のルーチンをベンチマークしました。

clock_t before_real;
clock_t after_real;
struct tms before;
struct tms after;
std::vector<char *> numbers;
make_numbers(numbers);
before_real = times(&before);
for (int i = 0; i < numbers.size(); ++i) {
    parse(numbers[i]);
}
after_real = times(&after);
std::cout << "user: " << after.tms_utime - before.tms_utime
          << std::endl;
std::cout << "real: " << after_real - before_real
          << std::endl;

realとの違いuserはrealウォール クロック時間であり、userは OS がプロセスを実行するのに実際に費やした時間です (したがって、コンテキスト スイッチは実行時間に対してカウントされません)。

私のテストでは、ルーチンが OP のルーチン ( g++ -O364 ビット Linux システムでコンパイル) のほぼ 2 倍の速さで実行されました。

于 2012-06-18T06:06:06.063 に答える
1

ファイルが本当に巨大な場合、解析ではなく IO が問題です。行を読み取るたびに、システム コールが実行されますが、これは非常にコストがかかる可能性があります。

より効率的な代替手段は、Memory-Mapped File IOを使用することです。Linux などの POSIX システムで作業している場合はmmap、ファイルを一度にすべてロードし、メモリ内のその場所へのポインターを返すコマンドを使用できます。次に、メモリマネージャーは、そのポインターを介してデータにアクセスするときに、ファイルの読み取りとスワップイン/スワップアウトを処理します。

これは次のようになります

#include <sys/mman.h>
int fd = open( 'abc.txt' , O_RDONLY );
char *ptr = mmap( NULL , length , PROT_READ , MAP_PRIVATE , fd , 0 );

ただし、man ページを読んで、自分に最適なオプションを見つけることを強くお勧めします。

于 2012-06-18T09:44:52.063 に答える
0

  1. ファイルに int 数値が含まれている場合、operator>>を使用できますが、これは c++ のみのソリューションです。何かのようなもの ：

    std::fstream f("abc.txt");
int value = 0;
f >> value

  2. 2 進数表現を含むようにファイルを変換すると、パフォーマンスを向上させるためのオプションが増えます。文字列から型への数値の解析を回避するだけでなく、データにアクセスするための別のオプションもあります (たとえば、mmapを使用するなど)。

于 2012-06-18T05:57:11.007 に答える
0

まず、一般的な推奨事項は、常にプロファイリングを使用して、実際に遅いのは変換であり、ディスクからファイルを物理的に読み取るなどの他のものではないことを確認することです。

独自の最小限の数値解析関数を作成することで、パフォーマンスを改善できる場合があります。strtok は文字列を変更するため、最適な速度ではありません。すべての数値が 10 進整数であり、エラー チェックが不要であることがわかっている場合は、翻訳を少し単純化できます。

それが実際に変換であり、(たとえば) 問題である I/O ではない場合、行の処理を高速化する可能性のある strtok のない一部のコード。

void handle_one_number(int number) {
    // ....
}

void handle_numbers_in_buffer(char *buffer) {
    while (1) {
        while (*buffer != '\0' && isspace(*buffer))
            ++buffer;
        if (*buffer == '\0')
            return;
        int negative = 0;
        if (*buffer == '-') {
            negative = 1;
            ++buffer;
        }
        int number = 0;
        while (isdigit(*buffer)) {
            number = number * 10 + *buffer - '0';
            ++buffer;
        }
        if (negative)
            number = -number;
        handle_one_number(number);
    }
}

実際に行って、いくつかのベンチマークを実行しました。I/O が支配的であると予想していましたが、(「特定のシステムで、特定のコンパイラを使用する」という通常の警告に従って) 数値の解析にかなりの時間がかかることがわかりました。

strtok バージョンから上記のコードに変更することで、1 億個の数字 (テキストは既にメモリ内にある) の翻訳時間を 5.2 秒から約 1.1 秒に改善することができました。遅いディスク (Caviar Green) から読み取ると、5.9 秒から 3.5 秒に改善されました。SSD から読み取ると、5.8 秒から 1.8 秒に改善されました。

を使用してファイルを直接読み取ろうとwhile (fscanf(f, "%d", ....) == 1) ....しましたが、おそらく fscanf がスレッドセーフであり、より多くの呼び出しがより多くのロックを必要とするため、はるかに遅くなることが判明しました (10 秒)。

(-O2 最適化を使用した Ubuntu 11.04 上の GCC 4.5.2、各バージョンの複数回の実行、実行間のディスク キャッシュのフラッシュ、i7 プロセッサ。)

于 2012-06-18T06:11:55.880 に答える