Les utilitaires Unix sont-ils intelligents?

8

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?

kamaal
la source
4
Ils sont si intelligents qu'ils prendront un jour le contrôle de la Terre. Mais pour l' instant , vous devez décider quels sont ceux que vous allez utiliser, comme grep, egrepou fgrep.
Keith
1
Mais si vous utilisez egrep régulièrement et que vous passez soudainement à fgrep, il pourrait décider de vous tuer dans votre sommeil pour avoir été infidèle.
Shadur
1
Ils sont aussi intelligents que les mains qui les manient.
luis.espinal

Réponses:

7

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.

Šimon Tóth
la source
2
Pour compléter votre réponse: gnu.org/software/coreutils
sahid
Pourquoi auriez-vous besoin de regarder le code source? les algorithmes de greps sont bien connus et documentés. C'est même dans la page Wikipedia pour grep. link
Compte supprimé
@ Supprimé Je pense que vous confondez les principes avec la mise en œuvre.
Šimon Tóth
@Let_Me_Be: L'algorithme et même l'implémentation sont bien connus et documentés. link link
Compte supprimé
@Deleted Peut-être que je ne comprends pas ce que vous essayez de dire, mais que le grep Linux de coreutils utilise un algorithme spécifique, ne signifie pas que toutes les implémentations utilisent cet algorithme. Et oui, vous avez raison en ce que les algorithmes ont tendance à être bien connus (puisque c'est le point de les concevoir).
Šimon Tóth
2

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)

Pas certain
la source
1

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 .

Shinnok
la source
0

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?

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.

Grep change-t-il intelligemment d'algorithmes lors de la recherche de différents ensembles de données?

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 wcand diff.

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.

luis.espinal
la source
2
Le thème ici est plus de Non, ils sont en fait stupides! . Vous devez leur dire exactement ce que vous devez faire. Quoi qu'il en soit, nous ne voulons pas qu'ils soient trop intelligents avec nous, vous savez.
tshepang
0

Grep change-t-il intelligemment d'algorithmes lors de la recherche de différents ensembles de données?

Je ne pense pas, mais il passe à l'algorithme non-RE "rapide" lorsqu'il reçoit l'indicateur -f (ou est invoqué comme fgrep).

kmarsh
la source
c'est-à-dire pas vraiment intelligent :)
tshepang