Bonjour,  
 
je dois faire une recherche de la façon suivante  
:  
 
un fichier A contient 120 000 valeurs a tester qui  
sont des numéros.  
Un fichier B contient 10 000 000 de lignes qui  
commencent par des numéros qui sont  
potentiellement dans le fichier A  
 
Ce que je fais aujourd'hui :  
 
grep -f A B > resultats.  
 
Le temps de traitement est excessivement long (5  
jours) et je cherche à développer un programme  
qui me permette de résoudre le problème le plus  
rapidement possible (4 heures maximum).  
 
J'ai déjà effectué un tri sur les fichiers et mis, das mon fichier de valeur a tester, le critère ^(commence par).
 
Je me demandais s'il n'existait pas d'algorithme procedant par division de fichiers en sous fichiers et en parallelisant la recherche  
A=A1 +A2+...Ak  
 
B=B1+B2+....BN  
 
 
 
 
Une idée?  
 
Merci

J'ai pas de gros sets de donnée, mais essaye ca :

#!/usr/bin/env python
import bisect
 
mask = []
 
for line in file('A'):
    bisect.insort(mask, int(line))
 
for line in file('B'):
    key = int(line.split(' ', 1)[0])
    if mask[bisect.bisect_left(mask, key)] == key:
        print line,

python est pas franchement rapide, mais l'algo utilisé trie les valeur dans le fichier A puis utilise une dichotomie donc ca sera ptêtre plus rapide.
 
Sinon l'idée est reproductible en C, et la ce sera plus surement plus rapide que grep.

Va voir chez lea-linux si j'y suis

Voici un petit script awk effectue le travail.
Il est dans le même esprit que le programme python que propose 0x90.
 
Il présuppose que le numéro dans le fichier B est suivi d'un espace (ou d'une tabulation).

Si le séparateur dans le fichier B est autre chose qu'un blanc :

Autre cas, si le numéro est de longueur fixe et qu'il n'y a pas de séparateur dans B :

 
Je n'ai aucune idée du temps que cela va prendre !
 
Jean-Pierre.

Euh, je connais pas awk, mais t'es sur d'utiliser un algo dichotomique la ?

Tu ne veux garder que les lignes du fichier B qui commencent par un numero qui est dans le fichier A, c'est ca ? A ta place je ferais ca en Perl (ou Python, ou Ruby, ou tout autre langage de script). Dans un premier temps tu lis le fichier A ligne par ligne, et tu met toutes les valeurs dans un hash (les valeurs que tu lis sont les clees du hash). Puis tu lis le fichier B ligne par ligne, et a chaque fois tu regardes si le premier champs est dans le hash. Le hash c'est a mon avis la solution la plus rapide (et aussi la plus rapide a coder). Beaucoup plus rapide en tout ca qu'une recherche "a la main" par dichotomie.

Je suis d'accord, c'est un cas où le shell, puissant et très pratique par ailleurs, montre ici ses limites : il n'est pas fait pour traiter de telles quantités de données (5j   ).
 
PERL me semble être une bonne solution, surtout qu'il y a de bonne chance qu'il soit déjà installé. La solution de matafan me semble bien.
Celle de 0x90 en Python semble chouette aussi.

 
avec 120 000 valeurs dans un seul hash, j'ai eu peur de me retrouver avec des buckets extrachargés et donc de ramer pour rechercher dedans. ( j'ai eu la flemme de vérifier si python 1) resize les hash 2) trie les buckets, s'il le fait efficacement, alors ca peut être mieux avec un hash ).
 
Sinon y'a toujours des solutions sympa en C en générant un ptit automate en lisant le fichier A....

Perl n'a aucun probleme a gerer efficacement des hashs de plusieurs centaines de miliers de clees. C'est fait pour ca. D'ailleurs j'ai fait un petit test. Je genere un fichier a.txt qui contient 120,000 valeurs aleatoire entre 0 et 1,000,000,000, et un fichier b qui contient 10,000,000 lignes commencant par une valeur aleatoire egalement entre 0 et 1,000,000,000 :
 

 
Puis je fait tourner ce petit script, qui fait ce que nandao demande :
 

 
Les resultats :
 

 
1 minute... Legerement plus rapide que les 5 jours de nandao  

 
Joli !!!
Est-ce que Python ferait aussi bien ???

LC_ALL=C grep -f A B > resultats
 
ça fait souvent des étincelles.

J'ai testé avec la même quantité de donné (après avoir corrigé un ptit bug ) :
real    1m10.963s
user    1m5.109s
sys     0m0.981s
Je le refais en plus simple (en faisant confiance à la hashtable ) :
real    0m28.883s
user    0m28.203s
sys     0m0.324s
 
Moralité, Je suis une grosse loutre
 
[edit] Simplification encore :
real    0m15.995s
user    0m15.835s
sys     0m0.155s

J'ai testé les 3 méthodes awk, perl et grep sur mon système AIX avec le même volume de données (je ne dispose pas de python).
Voici les résultats :

A priori mon serveur semble à la traine par rapport aux votres (durée perl trois fois plus importante).
Ma commande grep s'est plantée au bout de deux secondes avec le message 'out of memory'
Pouvez vous tester avec awk et m'indiquer les temps obtenus.
 
Jean-Pierre.

Quoiqu'il en soit je ne vois pas comment obtenir les 5j de traitement, même awk est plus rapide, c'est pourtant pas un foudre de guerre

Ptet que les lignes du fichier "B" sont très longues...  

En effet il ne s'agit pas d'un algo dichotomique.
Ceci étant, la structure des tableaux en awk est telle que cela revient au même à mes yeux.  
Les tableaux sont gérés sous forme d'arbre èquilibré, toutes les feuilles sont à la même profondeur dans l'arbre (à un niveau prés) et donc accessibles avec un nombre équivalent d'opérations.  
Une autre incidence de cette structure est que l'ordre des indices récupéré par uneboucle for in est imprédictible.