Как бы вы эффективно реализовали хвост?

Каков эффективный способ реализации хвоста в * NIX? Я подошел (написал) двумя простыми решениями, используя как круглый буфер для загрузки строк в круговую структуру (массив | дважды связанный круговой список - для удовольствия). Я видел часть старой реализации в busybox и из того, что я понял, они использовали fseek для поиска EOF, а затем читали материал "назад". Есть ли что-нибудь более чистое и быстрое там? Меня спросили об этом на собеседовании, и искатель не выглядел удовлетворенным. Заранее благодарю вас.

Ответ 1

Я не думаю, что есть решения, отличные от "держать последние N строк при чтении вперед данных" или "начинать с конца и идти назад, пока вы не прочтете N-ю строку".

Дело в том, что вы использовали бы тот или иной, основанный на контексте.

"Идите в конец и идите назад" лучше, когда хвост обращается к файлу произвольного доступа или когда данные достаточно малы, чтобы их можно было поместить в память. В этом случае время выполнения сводится к минимуму, поскольку вы сканируете данные, которые должны быть выведены (так что это "оптимально" )

Ваше решение (сохранить N последних строк) лучше, когда хвост питается конвейером или когда данные огромны. В этом случае другое решение тратит слишком много памяти, поэтому это непрактично, и в случае, если источник медленнее, чем хвост (что является вероятным), сканирование всего файла не так важно.

Ответ 2

Прочитать назад от конца файла до тех пор, пока N не будут прочитаны строки, или не будет достигнуто начало файла.

Затем распечатайте то, что было просто прочитано.

Я не думаю, что здесь нужны какие-то фантастические структуры данных.

Вот вам исходный код хвоста, если вам интересно.

Ответ 3

Сначала используйте fseek, чтобы найти конец файла, а затем вычесть 512 и fseek на это смещение, а затем читать вперед оттуда до конца. Подсчитайте количество разрывов строк, потому что, если их слишком мало, вам придется сделать то же самое с вычитаемым смещением 1024 ..., но в 99% случаев 512 будет достаточно.

Этот (1) избегает чтения всего файла вперед и (2), почему это, вероятно, более эффективно, чем чтение назад с конца, заключается в том, что чтение вперед обычно быстрее.

Ответ 4

/*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.*/