Comment grep fonctionne-t-il si vite?

Je suis vraiment étonné par la fonctionnalité de GREP dans le shell, auparavant, j'utilisais la méthode de sous-chaîne en java mais maintenant j'utilise GREP pour cela et il s'exécute en quelques secondes, il est incroyablement plus rapide que le code java que j'avais l'habitude d'écrire. (d'après mon expérience, je me trompe peut-être)

Cela étant dit, je n'ai pas été en mesure de comprendre comment cela se passe? il n'y a pas non plus beaucoup de disponible sur le Web.

Est-ce que quelqu'un peut m'aider avec ça?

En supposant que votre question concerne GNU grepspécifiquement. Voici une note de l'auteur, Mike Haertel:

GNU grep est rapide car il évite de regarder à chaque octet d'entrée.

GNU grep est rapide car il EXÉCUT TRÈS PEU D'INSTRUCTIONS POUR CHAQUE BYTE qu'il fait regarder.

GNU grep utilise l'algorithme bien connu de Boyer-Moore, qui recherche d'abord la dernière lettre de la chaîne cible, et utilise une table de recherche pour lui dire jusqu'où il peut sauter dans l'entrée chaque fois qu'il trouve un caractère non correspondant.

GNU grep déroule également la boucle interne de Boyer-Moore et configure les entrées de la table delta de Boyer-Moore de telle manière qu'il n'a pas besoin de faire le test de sortie de boucle à chaque étape déroulée. Le résultat de ceci est que, à la limite, GNU grep fait en moyenne moins de 3 instructions x86 exécutées pour chaque octet d'entrée qu'il regarde réellement (et il saute entièrement de nombreux octets).

GNU grep utilise des appels système d'entrée Unix bruts et évite de copier des données après les avoir lues. De plus, GNU grep ÉVITE DE BRISER L'ENTRÉE EN LIGNES. La recherche de nouvelles lignes ralentirait grep d'un facteur plusieurs fois, car pour trouver les nouvelles lignes, il faudrait regarder chaque octet!

Ainsi, au lieu d'utiliser une entrée orientée ligne, GNU grep lit les données brutes dans un grand tampon, recherche le tampon à l'aide de Boyer-Moore, et ce n'est que lorsqu'il trouve une correspondance qu'il recherche les nouvelles lignes de délimitation (Certaines options de ligne de commande comme - n désactiver cette optimisation.)

Cette réponse est un sous-ensemble des informations tirées d' ici .

Pour ajouter à l'excellente réponse de Steve.

Cela n'est peut-être pas très connu, mais grep est presque toujours plus rapide lorsqu'il recherche une chaîne de motif plus longue qu'une chaîne courte, car dans un motif plus long, Boyer-Moore peut avancer dans des foulées plus longues pour atteindre des vitesses sublinéaires encore meilleures :

Exemple:

# after running these twice to ensure apples-to-apples comparison
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log
28
0.168u 0.068s 0:00.26

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log
28
0.100u 0.056s 0:00.17

La forme la plus longue est 35% plus rapide!

Comment venir? Boyer-Moore consolide une table de saut en avant à partir de la chaîne de modèle, et chaque fois qu'il y a une discordance, il choisit le saut le plus long possible (du dernier caractère au premier) avant de comparer un seul caractère de l'entrée au caractère de la table de saut.

Voici une vidéo expliquant Boyer Moore (crédit à kommradHomer)

Une autre idée fausse courante (pour GNU grep) est que fgrepc'est plus rapide que grep. fin fgrepne signifie pas `` rapide '', cela signifie `` fixe '' (voir la page de manuel), et comme les deux sont le même programme, et les deux utilisent Boyer-Moore , il n'y a pas de différence de vitesse entre eux lors de la recherche de fixed- chaînes sans caractères spéciaux de regexp. L'utilisation seule raison I fgrepest quand il y a un caractère spécial regexp (comme ., []ou *) Je ne veux pas qu'il soit interprété comme tel. Et même dans ce cas, la forme la plus portable / standard grep -Fest préférée fgrep.