17

*NIX でテールを実装する効率的な方法は何ですか? 私は 2 つの単純な解決策を考え出しました (書きました)。どちらも一種の循環バッファを使用して行を循環構造 (配列 | 二重にリンクされた循環リスト - 楽しみのために) にロードします。ビジーボックスの古い実装の一部を見たことがありますが、私が理解したことから、彼らは fseek を使用して EOF を見つけ、「後方」に読み込んでいました。よりクリーンで高速なものはありますか？面接でこう聞かれましたが、質問者は満足していないようでした。前もって感謝します。

4

4 に答える 4

16

「データを前方に読みながら最新のN行を保持する」または「最後から開始してN行目を読み取るまで逆方向に進む」以外の解決策はないと思います。

ポイントは、コンテキストに基づいてどちらかを使用することです。

tail がランダム アクセス ファイルにアクセスする場合、またはデータがメモリに配置できるほど小さい場合は、「最後まで行って逆方向に進む」方が適切です。この場合、出力する必要があるデータをスキャンするため、ランタイムが最小化されます (つまり、「最適」です)。

テールにパイプラインが供給されている場合、またはデータが巨大な場合は、ソリューション (最新の N 行を保持する) の方が優れています。この場合、他の解決策は大量のメモリを浪費するため、実用的ではありません。また、ソースがテールよりも遅い場合 (これはおそらくそうです)、すべてのファイルをスキャンしてもそれほど重要ではありません。

于 2012-04-15T18:10:58.207 に答える
8

N改行が読み取られるか、ファイルの先頭に到達するまで、ファイルの末尾から逆方向に読み取ります。

次に、今読んだものを印刷します。

ここでは、凝ったデータ構造は必要ないと思います。

興味のある方は、テールのソースコードをご覧ください。

于 2012-04-15T18:03:11.780 に答える
6

最初に を使用fseekしてファイルの終わりを見つけ、次に 512 を減算fseekしてそのオフセットを取得し、そこから最後まで順方向に読み取ります。改行の数を数えます。数が少なすぎる場合は、1024 の減算オフセットで同じことを行う必要がありますが、99% のケースでは 512 で十分です。

これにより、(1)ファイル全体を前方に読み取ることが回避されます。(2)これがおそらく最後から後方に読み取るよりも効率的である理由は、前方に読み取る方が一般的に高速であるためです。

于 2013-06-27T05:36:26.630 に答える
0

/*This example implements the option n of tail command.*/

#define _FILE_OFFSET_BITS 64
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <errno.h>
#include <unistd.h>
#include <getopt.h>

#define BUFF_SIZE 4096

FILE *openFile(const char *filePath)
{
  FILE *file;
  file= fopen(filePath, "r");
  if(file == NULL)
  {
    fprintf(stderr,"Error opening file: %s\n",filePath);
    exit(errno);
  }
  return(file);
}

void printLine(FILE *file, off_t startline)
{
  int fd;
  fd= fileno(file);
  int nread;
  char buffer[BUFF_SIZE];
  lseek(fd,(startline + 1),SEEK_SET);
  while((nread= read(fd,buffer,BUFF_SIZE)) > 0)
  {
    write(STDOUT_FILENO, buffer, nread);
  }
}

void walkFile(FILE *file, long nlines)
{
  off_t fposition;
  fseek(file,0,SEEK_END);
  fposition= ftell(file);
  off_t index= fposition;
  off_t end= fposition;
  long countlines= 0;
  char cbyte;

  for(index; index >= 0; index --)
  {
    cbyte= fgetc(file);
    if (cbyte == '\n' && (end - index) > 1)
    {
      countlines ++;
      if(countlines == nlines)
      {
    break;
      }
     }
    fposition--;
    fseek(file,fposition,SEEK_SET);
  }
  printLine(file, fposition);
  fclose(file);
}

int main(int argc, char *argv[])
{
  FILE *file;
  file= openFile(argv[2]);
  walkFile(file, atol(argv[1]));
  return 0;
}

/*Note: take in mind that i not wrote code to parse input options and arguments, neither code to check if the lines number argument is really a number.*/
于 2013-06-27T05:22:04.160 に答える