Wie würden Sie den Schwanz effizient umsetzen?

Question

Wie kann Tail in * NIX effizient implementiert werden? Ich kam (schrieb) mit zwei einfachen Lösung, beide mit Art von Ringpuffer, um Linien in kreisförmige Struktur (Array | doppelt verknüpfte kreisförmige Liste - zum Spaß) zu laden. Ich habe einen Teil der älteren Implementierung in busybox gesehen und von dem, was ich verstanden habe, fseek verwendet, um EOF zu finden und dann Zeug "rückwärts" zu lesen. Gibt es etwas saubereres und schneller da draußen? Ich wurde dies auf Interview gefragt und Asker sah nicht zufrieden aus. Vielen Dank im Voraus.

Answer 1

Ich glaube nicht, gibt es Lösungen, anders als „hält die neuesten Linien N, während sie darauf, die Daten zu lesen“ oder „vom Ende beginnen und gehe nach hinten, bis Sie die N-ten Zeile lesen“.

Der Punkt ist, dass Sie den einen oder anderen basierend auf dem Kontext verwenden würden.

Die „bis zum Ende gehen und gehen nach hinten“ ist besser, wenn Schwanz eine zufällige Access-Datei zugreift, oder wenn die Daten klein genug, um auf Speicher abgelegt werden. In diesem Fall wird die Laufzeit minimiert, da Sie die auszugebenden Daten scannen (also "optimal")

Ihre Lösung (halten Sie die N neuesten Zeilen) ist besser, wenn Schwanz mit einer Pipeline oder gefüttert wird wenn die Daten riesig sind. In diesem Fall verschwendet die andere Lösung zu viel Speicher, so dass es nicht praktisch ist und in dem Fall, dass die Quelle langsamer ist als der Schwanz (was wahrscheinlich ist) ist das Scannen der gesamten Datei nicht so wichtig.

Answer 2

Lesen rückwärts vom Ende der Datei bis N Zeilenumbrüche gelesen oder der Anfang der Datei erreicht ist.

Dann drucken, was gerade gelesen wurde.

Ich denke nicht, irgendwelche Phantasie Datenstrukturen hier gebraucht werden.

Here is the source code of tail wenn Sie interessiert sind.

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

Erster Einsatz fseek die End-of-Datei 512 und fseek dann subtrahieren versetzt, das zu finden, dann vorwärts von dort gelesen zu beenden. Zählen Sie die Anzahl der Zeilenumbrüche, denn wenn es zu wenige gibt, müssen Sie dasselbe mit einem subtrahierten Offset von 1024 ... machen, aber in 99% der Fälle sind 512 genug.

Diese (1) vermeidet die gesamte Datei nach vorne zu lesen und (2) der Grund, warum dies wahrscheinlich effizienter ist als rückwärts vom Ende zu lesen ist, dass nach vorn Lesen der Regel schneller ist.