9

`_IOFBF~ モードでstdin使用して から効率的に読み込もうとしています。setvbuf私はバッファリングが初めてです。私は実用的な例を探しています。

入力は 2 つの整数 ( n、k) で始まります。入力の次のn行には、1 つの整数が含まれます。目的は、 で割り切れる整数の数を出力することkです。

#define BUFSIZE 32
int main(){
  int n, k, tmp, ans=0, i, j;
  char buf[BUFSIZE+1] = {'0'};
  setvbuf(stdin, (char*)NULL, _IONBF, 0);
  scanf("%d%d\n", &n, &k);
  while(n>0 && fread(buf, (size_t)1, (size_t)BUFSIZE, stdin)){
    i=0; j=0;
    while(n>0 && sscanf(buf+j, "%d%n", &tmp, &i)){
    //printf("tmp %d - scan %d\n",tmp,i); //for debugging
      if(tmp%k==0)  ++ans;
      j += i; //increment the position where sscanf should read from
      --n;
    }
  }
  printf("%d", ans);
  return 0;
}

問題は、 number が境界にある場合、バッファー bufが23から読み取られることです。2354\n読み取りが必要な場合2354(読み取れない)、または何もない場合です。

この問題を解決するにはどうすればよいですか?

編集
解決済み (分析あり) .

完全な問題仕様の編集

4

11 に答える 11

3

setvbufと distchingでフル バッファリングを試すことをお勧めしfreadます。仕様が 1 行に 1 つの数値である場合、私はそれを当然のことと見なし、使用fgetsして行全体を読み取り、それを渡してstrtoulその行にあるはずの数値を解析します。

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INITIAL_BUFFER_SIZE 2 /* for testing */

int main(void) {
    int n;
    int divisor;
    int answer = 0;
    int current_buffer_size = INITIAL_BUFFER_SIZE;
    char *line = malloc(current_buffer_size);

    if ( line == NULL ) {
        return EXIT_FAILURE;
    }

    setvbuf(stdin, (char*)NULL, _IOFBF, 0);

    scanf("%d%d\n", &n, &divisor);

    while ( n > 0 ) {
        unsigned long dividend;
        char *endp;
        int offset = 0;
        while ( fgets(line + offset, current_buffer_size, stdin) ) {
            if ( line[strlen(line) - 1] == '\n' ) {
                break;
            }
            else {
                int new_buffer_size = 2 * current_buffer_size;
                char *tmp = realloc(line, new_buffer_size);
                if ( tmp ) {
                    line = tmp;
                    offset = current_buffer_size - 1;
                    current_buffer_size = new_buffer_size;
                }
                else {
                    break;
                }
            }
        }
        errno = 0;
        dividend = strtoul(line, &endp, 10);
        if ( !( (endp == line) || errno ) ) {
            if ( dividend % divisor == 0 ) {
                answer += 1;
            }
        }
        n -= 1;
    }

    printf("%d\n", answer);
    return 0;
}

gcc version 3.4.5 (mingw-vista special r3)Perl スクリプトを使用して 0 から 1,000,000 までの 1,000,000 個のランダムな整数を生成し、Windows XP ラップトップでこのプログラムをコンパイルした後、それらが 5 で割り切れるかどうかを確認しました。全体で 0.8 秒もかかりませんでした。

を使ってバッファリングをオフにするsetvbuf(stdin, (char*)NULL, _IONBF, 0);と、時間は約 15 秒になりました。

于 2010-03-04T00:54:00.953 に答える
2

バージョン 1 : getchar_unlockedR Samuel Klatchko の提案に従って使用 (コメントを参照)

#define BUFSIZE 32*1024
int main(){
  int lines, number=0, dividend, ans=0;
  char c;
  setvbuf(stdin, (char*)NULL, _IOFBF, 0);// full buffering mode
  scanf("%d%d\n", &lines, ÷nd);
  while(lines>0){
    c = getchar_unlocked();
    //parse the number using characters
    //each number is on a separate line
    if(c=='\n'){
      if(number % dividend == 0)    ans += 1;
      lines -= 1;
      number = 0;
    }
    else
      number = c - '0' + 10*number;
  }

  printf("%d are divisible by %d \n", ans, dividend);
  return 0;
}

バージョン 2:freadブロックを読み取り、そこから数値を解析するために使用します。

#define BUFSIZE 32*1024
int main(){
int lines, number=0, dividend, ans=0, i, chars_read;
char buf[BUFSIZE+1] = {0}; //initialise all elements to 0
scanf("%d%d\n",&lines, &dividend);

while((chars_read = fread(buf, 1, BUFSIZE, stdin)) > 0){
  //read the chars from buf
  for(i=0; i < chars_read; i++){
    //parse the number using characters
    //each number is on a separate line
    if(buf[i] != '\n')
      number = buf[i] - '0' + 10*number;
    else{
      if(number%dividend==0)    ans += 1;
      lines -= 1;
      number = 0;
    }       
  }

if(lines==0)  break;
}

printf("%d are divisible by %d \n", ans, dividend);
return 0;
}

結果: (11 で割り切れるかどうかテストされた 1000 万の数)

実行 1: (バージョン 1 setvbuf なし) 0.782 秒
実行 2: (バージョン 1 setvbuf あり) 0.684 秒
実行 3: (バージョン 2) 0.534

PS - -O1 フラグを使用して GCC でコンパイルされたすべての実行

于 2010-03-04T10:38:54.303 に答える
2

私が混乱していることの 1 つは、 への呼び出しを介してストリーム オブジェクト内でフル バッファリングを有効にしsetvbuf、フル バッファを に読み込むことによって独自のバッファリングを実行している理由ですbuf。

バッファリングを行う必要性は理解していますが、それは少しやり過ぎです。

独自のバッファリングに固執しsetvbufて削除することをお勧めします。その理由は、独自のバッファリングを実装するのは難しい場合があるためです。問題は、トークン(あなたの場合は数値)がバッファ境界をまたぐときに何が起こるかです。たとえば、バッファーが 8 バイト (末尾の NULL は合計 9 バイト) で、入力ストリームが次のようになっているとします。

12345 12345

初めてバッファを埋めると、次のようになります。

"12345 12"

2回目にバッファを埋めると、次のようになります。

"345"

適切なバッファリングでは、このケースを処理する必要があるため、バッファを 3 つの数値 {12345, 12, 234} ではなく、2 つの数値 {12345, 12345} として扱います。

stdio はすでにそれを処理しているので、そのまま使用してください。を呼び出し続けsetvbuf、 を取り除き、freadを使用scanfして入力ストリームから個々の数値を読み取ります。

于 2010-03-04T00:41:43.557 に答える
1

絶対的な速度を求めていて、POSIX 風のプラットフォームで作業している場合は、メモリ マッピングの使用を検討してください。標準 I/O を使用して Sinan の回答を取得し、時間を計り、メモリ マッピングを使用して以下のプログラムを作成しました。データ ソースがファイルではなく端末またはパイプである場合、メモリ マッピングは機能しないことに注意してください。

0 から 10 億までの 100 万の値 (および 17 の固定除数) を使用した場合、2 つのプログラムの平均タイミングは次のようになりました。

  • 標準 I/O: 0.155 秒
  • メモリ マップ: 0.086 秒

おおよそ、メモリ マップド I/O は標準 I/O の 2 倍の速さです。

いずれの場合も、ウォームアップランを無視した後、計時を 6 回繰り返しました。コマンドラインは次のとおりです。

time fbf < data.file    # Standard I/O (full buffering)
time mmf < data.file    # Memory mapped file I/O

#include <ctype.h>
#include <errno.h>
#include <limits.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/stat.h>

static const char *arg0 = "**unset**";
static void error(const char *fmt, ...)
{
    va_list args;
    fprintf(stderr, "%s: ", arg0);
    va_start(args, fmt);
    vfprintf(stderr, fmt, args);
    va_end(args);
    exit(EXIT_FAILURE);
}

static unsigned long read_integer(char *src, char **end)
{
    unsigned long v;
    errno = 0;
    v = strtoul(src, end, 0);
    if (v == ULONG_MAX && errno == ERANGE)
        error("integer too big for unsigned long at %.20s", src);
    if (v == 0 && errno == EINVAL)
        error("failed to convert integer at %.20s", src);
    if (**end != '\0' && !isspace((unsigned char)**end))
        error("dubious conversion at %.20s", src);
    return(v);
}

static void *memory_map(int fd)
{
    void *data;
    struct stat sb;
    if (fstat(fd, &sb) != 0)
        error("failed to fstat file descriptor %d (%d: %s)\n",
              fd, errno, strerror(errno));
    if (!S_ISREG(sb.st_mode))
        error("file descriptor %d is not a regular file (%o)\n", fd, sb.st_mode);
    data = mmap(0, sb.st_size, PROT_READ, MAP_PRIVATE, fileno(stdin), 0);
    if (data == MAP_FAILED)
        error("failed to memory map file descriptor %d (%d: %s)\n",
              fd, errno, strerror(errno));
    return(data);
}

int main(int argc, char **argv)
{
    char *data;
    char *src;
    char *end;
    unsigned long k;
    unsigned long n;
    unsigned long answer = 0;
    size_t i;

    arg0 = argv[0];
    data = memory_map(0);

    src = data;

    /* Read control data */
    n = read_integer(src, &end);
    src = end;
    k = read_integer(src, &end);
    src = end;

    for (i = 0; i < n; i++, src = end)
    {
        unsigned long v = read_integer(src, &end);
        if (v % k == 0)
            answer++;
    }

    printf("%lu\n", answer);
    return(0);
}
于 2010-03-06T17:21:30.553 に答える
1

リダイレクトを使用していない場合の問題は、EOF を引き起こしていないことです。

これは (gcc を使用しているという事実に基づいて) Posix のように見えるので、入力するだけですctrl-D(つまり、コントロール ボタンを押しながら d を押す/放す) と、EOF に到達します。

Windows を使用している場合は、ctrl-Z代わりに使用すると思います。

于 2010-03-03T23:47:23.810 に答える
0

の値を使用して、整数を確認nした後で入力の読み取りを停止できます。n

外側のwhileループの状態を次のように変更します。

while(n > 0 && fread(buf, sizeof('1'), BUFSIZE, stdin))

内側の本体を次のように変更します。

{
  n--;
  if(tmp%k == 0)  ++ans;
}

あなたが抱え続けている問題は、あなたがbuf内側のwhileループで調整することは決してないのでsscanf、同じ数を何度も読み続けるということです。

strtol()の代わりに使用するように切り替えるとsscanf()、出力パラメーターを使用してendptr、数値が読み取られるときにバッファー内を移動できます。

于 2010-03-03T23:17:47.377 に答える
0

まず、scanf("%d%d",&n,&k) は n のみに値を押し込み、k を未設定のままにします。これは、scanf() の戻り値を確認するとわかります。埋められた変数の数を示します。scanf("%d %d",&n,&k) にスペースが必要だと思います。

次に、n は実行する反復回数ですが、"n>0" をテストしますが、減分することはありません。したがって、n>0 は常に true であり、ループは終了しません。

他の誰かが述べたように、stdin にパイプを介して供給するとループが終了します。これは、stdin の最後に EOF があるためです。これにより、fread() は NULL を返し、ループを終了します。おそらく、「n=n-1」または「n--」をどこかに追加したいと思うでしょう。

次に、sscanf では、%n は実際には標準的なものではありません。何をするのかはわかりませんが、何もしない可能性があります: scanf() は通常、認識されていない最初のフォーマット識別子で解析を停止します (既にデータを取得しているため) ここでは何もしませんが、悪い習慣です。

最後に、パフォーマンスが重要な場合は、fread() などをまったく使用しない方がよいでしょう。それらは実際には高性能ではないからです。isdigit(3) と iscntrl(3) を見て、read(2) で読み取った生データ バッファから数値を解析する方法を考えてみてください。

于 2010-03-04T00:44:10.900 に答える
-1

最も外側のループは、読み取り元がを返しwhile()たときにのみ終了します。これは、入力ファイルの実際のファイルの終わりに到達した場合、または入力パイプへの書き込みプロセスが終了した場合にのみ発生する可能性があります。したがって、ステートメントは実行されません。これはへの呼び出しとは何の関係もないと思います。stdinEOFprintf()setvbuf()

于 2010-03-03T13:24:31.040 に答える
-1

Mabe は、この getline 実装も見てください。

http://www.cpax.org.uk/prg/portable/c/libs/sosman/index.php

(長さ不明のデータ行をストリームから取得するための ISO C ルーチン。)

于 2010-03-03T13:36:09.983 に答える
-2

このすべてのパーマチュア最適化がランタイムにほとんど影響を与えない理由は、* nix および Windows タイプのオペレーティング システムでは、OS がファイル システムとの間のすべての I/O を処理し、これを行うために 30 年分の研究、トリック、および不正行為を実装するためです。非常に効率的に。

制御しようとしているバッファリングは、プログラムが使用するメモリのブロックにすぎません。したがって、速度の増加は最小限に抑えられます (1 つの大きな「mov」命令と 6 つまたは 7 つの小さな「mov」命令を実行した場合の効果)。

これを本当に高速化したい場合は、ファイル システム バッファ内のデータに直接アクセスできる "mmap" を試してください。

于 2010-03-04T02:17:13.103 に答える
-2

これが私のバイトごとの見方です：

/*

Buffered reading from stdin using fread in C,
http://stackoverflow.com/questions/2371292/buffered-reading-from-stdin-for-performance

compile with:
gcc -Wall -O3  fread-stdin.c

create numbers.txt:
echo 1000000 5 > numbers.txt
jot -r 1000000 1 1000000 $RANDOM >> numbers.txt

time -p cat numbers.txt | ./a.out

*/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define BUFSIZE 32

int main() {

   int n, k, tmp, ans=0, i=0, countNL=0;
   char *endp = 0;

   setvbuf(stdin, (char*)NULL, _IOFBF, 0);       // turn buffering mode on
   //setvbuf(stdin, (char*)NULL, _IONBF, 0);     // turn buffering mode off

   scanf("%d%d\n", &n, &k);

   char singlechar = 0;
   char intbuf[BUFSIZE + 1] = {0};

   while(fread(&singlechar, 1, 1, stdin))     // fread byte-by-byte
   {
      if (singlechar == '\n') 
      {
         countNL++;
         intbuf[i] = '\0';
         tmp = strtoul(intbuf, &endp, 10);
         if( tmp % k == 0) ++ans;
         i = 0;
      } else {
         intbuf[i] = singlechar; 
         i++;
      }
      if (countNL == n) break;
   }

   printf("%d integers are divisible by %d.\n", ans, k);
   return 0;

}
于 2010-03-04T19:28:40.007 に答える