Rapide de chaîne de recherche dans un fichier très volumineux

Quelle est la méthode la plus rapide pour la recherche de lignes dans un fichier contenant une chaîne de caractères. J'ai un fichier contenant des chaînes de caractères à rechercher. Ce petit fichier (smallF) contient environ 50 000 lignes et ressemble:

stringToSearch1
stringToSearch2
stringToSearch3

Je recherche l'ensemble de ces chaînes dans un fichier de plus grande taille (environ de 100 millions de lignes). Si une ligne dans ce fichier contient la chaîne de recherche de la ligne est imprimée.

La meilleure méthode que j'ai mis au point jusqu'à présent est

grep -F -f smallF largeF

Mais ce n'est pas très rapide. Avec seulement 100 chaînes de recherche dans smallF il faut environ 4 minutes. Pour plus de 50.000 chaînes de recherche, il va prendre beaucoup de temps.

Est-il une méthode plus efficace?

Pas de. C'est la méthode la plus efficace, à moins que vous pouvez parallélisation de la recherche, ou d'écrire une fin particulière de programme.
Voir: plus Rapide possible grep
fgrep au lieu de grep -F devrait être un peu plus vite...
de GNU grep de la page de manuel: "fgrep est le même que grep -F"
Pour clarifier ce qui est du contenu de /usr/bin/fgrep #!/bin/sh exec grep -F "$@"

OriginalL'auteur user262540 | 2016-06-08

16

Une fois, j'ai remarqué que l'utilisation de -E ou plusieurs -e paramètres est plus rapide que l'utilisation -f. Notez que cela peut ne pas être applicable à votre problème et que vous êtes à la recherche pour 50.000 chaîne de caractères dans un fichier de plus grande taille. Cependant, je voulais vous montrer ce qui peut être fait et ce qui pourrait être une valeur de test:

Voici ce que j'ai remarqué dans le détail:

Ont 1.2 GO de fichier rempli avec des chaînes aléatoires.
```
>ls -has | grep string
1,2G strings.txt

>head strings.txt
Mfzd0sf7RA664UVrBHK44cSQpLRKT6J0
Uk218A8GKRdAVOZLIykVc0b2RH1ayfAy
BmuCCPJaQGhFTIutGpVG86tlanW8c9Pa
etrulbGONKT3pact1SHg2ipcCr7TZ9jc
.....
```
Maintenant je recherche des chaînes "ab", "cd" et "ef" à l'aide de différents grep approches:
1. À l'aide de grep, sans drapeaux, de la recherche à la fois:
  
  grep "ab" strings.txt > m1.hors
  
  2,76 s utilisateur 0,42 s système de 96% de cpu à 3 313 total
  
  grep "cd" strings.txt >> m1.hors
  
  2,82 s utilisateur 0,36 s système de 95% de cpu 3,322 total
  
  grep "ef" strings.txt >> m1.hors
  
  2,78 s utilisateur 0,36 s système de 94% de cpu 3,360 total
Donc, au total, la recherche prend près de 10 secondes.
1. À l'aide de grep avec -f drapeau avec les chaînes de recherche en search.txt
```
>cat search.txt
 ab
 cd
 ef

>grep -F -f search.txt strings.txt > m2.out  
31,55s user 0,60s system 99% cpu 32,343 total
```
Pour certaines raisons, cela prend près de 32 secondes.
1. Maintenant à l'aide de plusieurs modèles de recherche avec -e
```
grep -E "ab|cd|ef" strings.txt > m3.out  
3,80s user 0,36s system 98% cpu 4,220 total
```
  ou
```
grep --color=auto -e "ab" -e "cd" -e "ef" strings.txt > /dev/null  
3,86s user 0,38s system 98% cpu 4,323 total
```
La troisième methode utilisant -E seulement pris 4.22 secondes pour rechercher le fichier.

Maintenant permet de vérifier si les résultats sont les mêmes:
```
cat m1.out | sort | uniq > m1.sort  
cat m3.out | sort | uniq > m3.sort
diff m1.sort m3.sort
#
```
La diff ne produit aucune sortie, ce qui signifie que les résultats sont les mêmes.

Peut-être envie de l'essayer, sinon, je vous conseille de regarder le fil "le plus Rapide possible grep", voir le commentaire de Cyrus.

OriginalL'auteur cb0

Note: je réalise que la suivante n'est pas bash en fonction de la solution, mais compte tenu de votre grand espace de recherche, une solution parallèle, est justifiée.

Si votre machine a plus d'un core/processeur, que vous pourriez appeler la fonction suivante dans Pythran, de parallélisation de la recherche:

#!/usr/bin/env python

#pythran export search_in_file(string, string)
def search_in_file(long_file_path, short_file_path):
    _long = open(long_file_path, "r")

    #omp parallel for schedule(guided)
    for _string in open(short_file_path, "r"):
        if _string in _long:
            print(_string)

if __name__ == "__main__":
    search_in_file("long_file_path", "short_file_path")

Remarque: les coulisses, Pythran prend le code Python et tenter activement de le compiler en C très rapide++.

OriginalL'auteur boardrider

1

Vous pouvez essayer de tamiser ou ag. Tamiser en particulier, les listes de certains assez impressionnants repères rapport à grep.

OriginalL'auteur ajfabbri

Vous devez vous connecter pour publier un commentaire.