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

Question

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

Answer 1

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

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

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

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

Answer 2

Прочитать назад с конца файла до N считываются строки или начинается начало файла.

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

Я не думаю, что здесь нужны какие-либо причудливые данные.

Here is the source code of tail Если вам интересно.

Answer 3

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

Answer 4

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

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