Question Comment implémenteriez-vous la queue efficacement?


Quel est le moyen efficace d'implémenter tail dans * NIX? Je suis arrivé (écrit) avec deux solutions simples, toutes deux utilisant une sorte de tampon circulaire pour charger les lignes dans une structure circulaire (tableau | liste circulaire à double liaison - pour le fun). J'ai vu une partie de l'ancienne implémentation dans busybox et d'après ce que j'ai compris, ils ont utilisé fseek pour trouver EOF et ensuite lire des choses "à l'envers". Y a-t-il quelque chose de plus propre et de plus rapide? On m'a demandé cela lors de l'interview et le demandeur n'a pas l'air satisfait. Merci d'avance.


12
2018-04-15 18:00


origine


Réponses:


Je ne pense pas qu'il existe des solutions différentes de "conserver les dernières lignes N lors de la lecture des données" ou "commencer à la fin et revenir en arrière jusqu'à ce que vous lisiez la ligne N".

Le fait est que vous utiliseriez l’un ou l’autre en fonction du contexte.

Le "aller à la fin et aller en arrière" est mieux lorsque la queue accède à un fichier à accès aléatoire, ou lorsque les données sont assez petites pour être mises en mémoire. Dans ce cas, le runtime est minimisé, puisque vous analysez les données à sortir (donc, il est "optimal")

Votre solution (conserver les dernières lignes) est préférable lorsque la queue est alimentée par un pipeline ou lorsque les données sont énormes. Dans ce cas, l'autre solution gaspille trop de mémoire, donc ce n'est pas pratique et, dans le cas où la source est plus lente que la queue (ce qui est probable), l'analyse de tous les fichiers n'a pas d'importance.


14
2018-04-15 18:10



Lire en arrière à partir de la fin du fichier jusqu'à ce que N les sauts de ligne sont lus ou le début du fichier est atteint.

Ensuite, imprimez ce qui vient d'être lu.

Je ne pense pas que des infrastructures de données sophistiquées soient nécessaires ici.

Voici le code source de la queue si vous êtes intéressé.


6
2018-04-15 18:03



Première utilisation fseek pour trouver la fin de fichier, soustrayez 512 et fseek à ce décalage, puis lire à partir de là pour terminer. Comptez le nombre de sauts de ligne, car s'il y en a trop peu, vous devrez faire la même chose avec un décalage soustrait de 1024 ... mais dans 99% des cas, 512 suffiront.

Ce (1) évite de lire tout le fichier en avant et (2) La raison pour laquelle cela est probablement plus efficace que de lire à rebours à partir de la fin est que la lecture avant est généralement plus rapide.


5
2018-06-27 05:36



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

0
2018-06-27 05:22