Come implementeresti la coda in modo efficiente?

Question

Qual è il modo efficace per implementare tail in * NIX? Mi sono avvicinato (scritto) con due semplici soluzioni, entrambe usando un tipo di buffer circolare per caricare le linee in una struttura circolare (array - elenco circolare doppiamente collegato - per divertimento). Ho visto parte della vecchia implementazione in busybox e da quello che ho capito, hanno usato fseek per trovare EOF e poi leggere "backwards". C'è qualcosa di più pulito e veloce là fuori? L'ho chiesto all'intervista e asker non sembrava soddisfatto. Grazie in anticipo.

Answer 1

Non penso che ci siano soluzioni diverse da "mantieni le ultime N righe mentre leggi i dati in avanti" o "parti dalla fine e vai indietro finché non leggi la riga N".

Il punto è che utilizzeresti l'uno o l'altro in base al contesto.

"go to end and go backwards" è migliore quando tail accede a un file di accesso casuale o quando i dati sono abbastanza piccoli da essere messi in memoria. In questo caso il runtime è ridotto al minimo, poiché si scansionano i dati che devono essere emessi (quindi, è "ottimale")

La soluzione (mantenere le ultime N righe) è migliore quando la coda viene alimentata con una tubazione o quando i dati sono enormi. In questo caso, l'altra soluzione spreca troppa memoria, quindi non è pratica e, nel caso in cui la sorgente sia più lenta della coda (che è probabile) la scansione di tutto il file non è poi così importante.

Answer 2

Leggere indietro dalla fine del file fino a N interruzioni di riga vengono lette o viene raggiunto l'inizio del file.

Quindi stampare ciò che è stato appena letto.

Non penso che qui siano necessarie eventuali strutture dati fantasiose.

Here is the source code of tail se sei interessato.

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

Primo utilizzo fseek per trovare il file di fine poi sottrarre 512 e fseek a quella offset, quindi leggere l'ora da lì alla fine. Contare il numero di interruzioni di linea perché se ce ne sono troppe si dovrà fare lo stesso con un offset sottratto di 1024 ... ma nel 99% dei casi 512 sarà sufficiente.

Questo (1) evita leggere l'intero file in avanti e (2) il motivo per cui questo è probabilmente più efficiente di lettura a ritroso a partire dalla fine è che la lettura in avanti è in genere più veloce.