Pourquoi 'grep -i' est-il si lent? Comment faire plus vite pour ASCII?

2

Considérer:

$ time lzop -d < tvtropes-index.lzo | egrep -B 5 '[Dd][eE][sS][cC][eE][nN][dD] ?[Ff][rR][oO][mM]'
real    0m0.438s

$ time lzop -d < tvtropes-index.lzo | egrep -B 5 'descend ?from' -i
real    0m11.294s

Les deux casse de manière insensible. Pourquoi la -iversion est-elle si lente? Comment je fais grep -ivite sans entrer des choses comme [iI] [nN] [tT] [hH] [iI] [sS] [wW] [aA] [Yy]?

Par exemple,

perl -ne 'print if /descend ?from/i'

fonctionne vite, mais '-B 5' n'est pas aussi simple à implémenter que dans grep (ainsi que d'autres options).

linux grep Vi.
la source
1
L’insensibilité à la casse est difficile, surtout si vous le faites sur une entrée Unicode.
Phogg
Comment rendre insensible à la casse rapide, par exemple comme "Remplacer chaque x par [xX] dans le motif"?
Vi.

Réponses:

7

Le pliage de la caisse est difficile

Le mappage simple de [az] à [AZ] fonctionne pour la plupart des documents texte simples uniquement ASCII. Cependant, il commence à s'effriter à mesure que nous explorons d'autres langues qui utilisent des caractères supplémentaires. En outre, il ne tient pas compte du fait que les mappages de cas dans certaines langues ne sont pas toujours algorithmiques ou statiques.

Par exemple, si vous êtes plié [az] -> [AZ], une chaîne telle que "Dürst" ou "résumé" peut paraître un peu bizarre: "DüRST" ou "RéSUMé".

Vous pourriez peut-être accélérer le processus en persuadant grep que le monde est de nouveau en ASCII, soit en utilisant un ancien grep, soit en jouant avec les paramètres régionaux (LC_ALL = C?).

Cette conversation mentionne "des ralentissements massifs des environnements locaux UTF8" mais n'aide pas.

RedGrittyBrick
la source
Existe-t-il un mode insensible à la casse rapide uniquement avec ASCII pour grep? LANG=C grep -iéchoue (lent).
Vi.
@Vi: lzop -d < thingy | tr '[A-Z]' '[a-z]' | grep ... peut-être?
RedGrittyBrick
1
Désolé, "LANG = C grep -i" fonctionne (testé à nouveau correctement).
Vi.
2

Hypothèse

Cela explique ce résultat contre-intuitif. Votre expression rationnelle n'est pas la même, grep -icar elle grep -iest plus générale, en tenant compte de la gestion complexe des chaînes multi-octets, du moins lorsqu'elle est compilée avec le symbole du préprocesseur MBS_SUPPORT.

Jetez un coup d'oeil ici:

http://cvs.savannah.gnu.org/viewvc/grep/grep/src/search.c?revision=1.42&view=markup

Cherchez match_icaseet MBS_SUPPORT.

Kaz
la source
0

Si le cas réel de la découverte n'est pas critique, vous pouvez utiliser trà plier [A-Z]pour [a-z]avant grep.

Xenoactive
la source
Je ne ferais cela que pour avoir un regex plus simple à écrire. Bien que la regex insensible à la casse atteigne un plus grand DFA, ce n'est probablement pas un gros problème. Cela dépend du nombre de correspondances. Si le fichier contient beaucoup de faux positifs ou de correspondances complètes qui utilisent beaucoup des combinaisons de cas possibles, le graphe d'état se mettra en cache dans la CPU. Cela ne se produit probablement pas. Il n’y aura probablement que quelques cas comme DESCEND, Descend et Descend qui traversent les mêmes chemins "parcourus" à travers la DFA regex.
Kaz