Les utilitaires Unix comme sort, find, grep, diff et al sont très pratiques pour effectuer des tâches rapides, parfois sans écrire de code du tout.
Je voulais savoir quels algorithmes utilisent-ils en interne et comment décider intelligemment un algorithme spécifique pour une tâche spécifique? Par exemple, si le tri obtient un énorme fichier d'entrée, utilisera-t-il différents algorithmes pour différentes tailles de données?
Grep change-t-il intelligemment d'algorithmes lors de la recherche de différents ensembles de données?
text-processing
grep
sort
coreutils
kamaal
la source
la source
grep
,egrep
oufgrep
.Réponses:
Unix est juste un standard, il spécifie ce que les implémentations doivent faire, mais pas comment elles doivent le faire.
Par conséquent, les implémentations de grep / sort / find utiliseront très probablement différentes approches sur différents systèmes (et même un système, comme Linux, il existe des implémentations simultanées).
Pour Linux, vous pouvez toujours consulter le code source.
la source
Vous pouvez être intéressé par cet article de la liste de diffusion de l'auteur original de GNU grep qui explique quelques-unes des optimisations de GNU grep. Une autre exploration agréable par ridiculous_fish (auteur de Hex Fiend)
la source
La norme UNIX ne spécifie pas les détails d'implémentation des outils système standard, sauf dans de très rares cas. Vous pouvez trouver la dernière version de la spécification Unix unique ici (avertissement: inscription requise).
Dans cet esprit, chaque UNIX (System V et descendants directs comme BSD, Solaris, Mac OS X, etc.) ou système d'exploitation basé sur UNIX (descendants lointains ou similaires: Linux, Minix) a ses propres implémentations des utilitaires décrits dans la spécification UNIX. Par exemple. jetez un oeil à FreeBSD et Linux / GNU Coreutils . Attention, certains outils sont des projets entiers séparés par eux-mêmes comme GNU diff ou GNU grep . Un autre fait est également que certaines implémentations de ces outils pourraient trouver leur chemin dans d'autres systèmes de type UNIX en standard que ceux pour lesquels ils ont été initialement écrits, par exemple certains gnu coreutils dans freebsd ou GCC.
Bonus: pour enrouler votre tête autour de l'arbre généalogique UNIX, jetez un œil à ce graphique .
la source
C'est une question intéressante (+1 pour ça). Je n'ai aucune idée de la réponse, mais si j'étais vous, je regarderais le code source des utilitaires GNU typiques pour avoir une idée de leurs algorithmes.
Je ne pense pas. Ne me citez pas car je ne peux pas vraiment vous le dire avec 100% de certitude, mais je ne le pense vraiment pas. La philosophie UNIX des choses est qu'une chose fait une chose et une seule chose. Voilà pourquoi nous avons plusieurs versions de grep (
grep
,egrep
,fgrep
).De plus, l'idée est de faire une seule et unique chose au moment de l'exécution. Différents comportements et algorithmes peuvent être configurés comme arguments de ligne de commande, de sorte que le même programme puisse agir légèrement différemment (et peut-être légèrement plus optimisé) entre les exécutions. Les bons exemples sont la commande
wc
anddiff
.Cependant, l'adaptation comportementale est basée sur la configuration (via les arguments de ligne cmd); ils ne modifient / adaptent pas le comportement au moment de l'exécution. Il s'agit généralement d'une complexité inutile pour le type d'artefacts que les outils UNIX visent à être.
Une telle complexité est plus appropriée des outils OMI plus complexes et moins généraux.
la source
Je ne pense pas, mais il passe à l'algorithme non-RE "rapide" lorsqu'il reçoit l'indicateur -f (ou est invoqué comme fgrep).
la source