¿Cómo implementaría la cola de manera eficiente?

Question

¿Cuál es la forma más eficiente de implementar cola en * NIX? Vine (escribí) con dos soluciones simples, ambas usando un tipo de memoria intermedia circular para cargar líneas en una estructura circular (matriz | lista circular doblemente unida - para divertirse). He visto parte de una implementación anterior en busybox y, por lo que entendí, usaron fseek para encontrar EOF y luego leer cosas "al revés". ¿Hay algo más limpio y más rápido? Me preguntaron esto en una entrevista y Asker no se veía satisfecho. Gracias de antemano.

Answer 1

No creo que haya soluciones diferentes a "mantener las últimas N líneas mientras lee los datos" o "comenzar desde el final e ir hacia atrás hasta que lea la línea enésima".

El punto es que usarías uno u otro según el contexto.

El "ir al final e ir hacia atrás" es mejor cuando la cola accede a un archivo de acceso aleatorio, o cuando los datos son lo suficientemente pequeños como para ponerlos en la memoria. En este caso, el tiempo de ejecución se minimiza, ya que escanea los datos que se deben generar (por lo tanto, es "óptimo")

Su solución (mantenga las N últimas líneas) es mejor cuando la cola se alimenta con una tubería o cuando los datos son enormes En este caso, la otra solución desperdicia demasiada memoria, por lo que no es práctica y, en el caso de que la fuente sea más lenta que la cola (lo que es probable), escanear todo el archivo no importa demasiado.

Answer 2

Lea hacia atrás desde el final del archivo hasta que N se lean los saltos de línea o se llegue al principio del archivo.

A continuación, imprima lo que acaba de leer.

No creo que se necesiten estructuras de datos sofisticadas aquí.

Here is the source code of tail si te interesa.

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

Primer uso fseek para buscar el archivo de fin de luego restar 512 y fseek a ese desplazamiento, a continuación, lea a partir de ahí hasta el final. Cuente el número de saltos de línea porque si hay muy pocos, tendrá que hacer lo mismo con un desplazamiento restado de 1024 ..., pero en el 99% de los casos, 512 será suficiente.

Este (1) evita leer todo el archivo hacia delante y (2) la razón por la que esto es probablemente más eficaz que la lectura hacia atrás desde el final es que la lectura hacia adelante es generalmente más rápido.