[C++]Recherche rapide dans une série de fichiers

xevius · Février 3, 2009, 2:48

Bonjour à tous!

J’ai fais au préalable quelques recherches sur le sujet mais je n’ai rien trouvé de potable ou correspondant à ce que je cherche.

Ce que je cherche c’est coder une recherche d’une chaine précise dans une série de fichiers.

Actuellement je fais la recherche “manuellement”: j’ouvre chaque fichier à la recherche de ma chaine, jusqu’à ce que je la trouve (ou pas…)

Le problème c’est que je fais ça dans des dossiers de plus de 200 fichiers textes de plus de 500 lignes et c’est long…

Y-a-t’il une solution rapide en C/C++?

Merci!

Berzehk · Février 3, 2009, 2:54

Approche matérielle:
si le contexte le permet, un mapping des fichiers en RAM peut se révéler intéressant.
Selon l’OS, si tu prends les fonctions de mapping des librairies systeme, il arrive qu’elles remettent a jour le cache d’un fichier mappé lorsqu’il est modifié. Il me semble que c’est le cas des libraires système de nunux. A vérifier cependant, mon cours date un peu.

C’est donc tres mechant en conso mémoire.

Approche algorithmique:
euh… Pour une approche algo il faudrait qu’il y ait une relation “mathématique” ou modélisable mathématiquement pour rendre la recherche plus efficace.

sinon, une recherche en faisant un pool de threads?

avec comme methode:
1/Mise en mémoire d’un fichier X
2/parsing

les threads seront lancés les un apres les autre vu qu’ils vont attendre la libération du disque
des qu’un fichier est chargé, un thread est chargé de parser son contenu.

AnA-l · Février 3, 2009, 2:56

Je vois difficilement comment tu peux trouver une chaine de caracteres dans un fichier sans l’ouvrir. Et si tu dois verifier sur 200 fichiers, ya surement pas d’autres facons. En tout cas, pas que je connaisse. Mais si ca existe, ca m’interesse. Par contre, tu peux certainement optimiser ton algo (genre eviter le sequentiel, tout lire, puis chercher dans tout, ou multithreader ca, mais ca va pas t’eviter de forcement lire tout les fichier) Par contre, tu peux ptet maintenir une DB du contenu des fichiers, ou ce genre de gruge.

Ben · Février 3, 2009, 2:57

ca depends du format de tes fichiers.
Si c’est du texte, tu fais une boucle sur ta liste de fichier, tu les ouvres avec un fopen ou equivalent, et tu cherches ta chaine a l’interieur.

Si c’est des formats proprio (word, excel …), ca va etre plus compliquer, car il faudra :

soit implementer l’ouverture du format
soit piloter le lancement de l’application qui comprends le format.

Dans les deux cas, c’est pas trivial.

LodeRunner · Février 3, 2009, 2:57

Multi-threader le bouzin ?

Sinon, quelle methode tu utilises pour reconnaitre ta requete. Tu fais des strncmp(), caractère par caractère sur ton fichier?

Et aussi, fais des tests avec différentes tailles de buffer de lecture pour tes fichiers. Cherche le bon compromis.

BioGeek · Février 3, 2009, 3:07

Pareil que tout le monde, je ne pense pas qu’il y ait de solution miracle.
Comme palliatif il y a cette petite librairie qui implémente des regex (Perl Compatible Regular Expression) peut-être que les algos de comparaison seront bien optimisés.
Enfin des tests de différentes tailles de buffer me semblent importants.
Quand tu as trouvé la solution miracle, tu nous tiens au courant (moi et mon intérêt pour la question)

xevius · Février 3, 2009, 3:08

Ce sont des fichiers txt générés par une machine.

Ils contiennent une série de 500/1000/2000 ID de 16 caractères.

Actuellement j’ouvre un fichier, je lis les lignes une à une et je compare avec la valeur recherchée. Et ça prend beaucoup (trop) de temps.

Avec windows quand on fait rechercher, on peut rechercher dans le contenu du fichier, et c’est beaucoup plus rapide. C’est ce que je cherche à faire en fait.

Ravine · Février 3, 2009, 3:18

Euh, bon, c’est pas du c/cpp mais la commande unix grep c’est pas fait pour ça ? en environnement win, c’est “find”

Alors c’est pas du homemade a la wannagaine en c/cpp, mais bon, faire un batch basé sur ces commande devrait pas prendre plus de quelques minutes, non ? Maintenant, ça ne répond vraiment qu’a la problématique que tu poses en début de thread. Si derriere y’a d’autres besoins, plus évolués que simplement rechercher cette ligne, ça répond probablement pas entierement a ta question.

Ben · Février 3, 2009, 3:18

ok, alors stop, vous melangez tout

Il y a trois chose a separer :

le format des fichiers
le mecanisme de listage des fichiers et leur ouverture
la recherche de la chaine dans les fichiers.
: c’est du txt, donc pas de pb, tu pourras l’ouvrir avec n’importe quoi.
: solution la plus simple, une bete boucle basé sur un listage des fichiers de ton arboresence et filtre sur leur nom ou leur type
: la recherche de la chaine dans les fichiers. la tu as plein de trucs qui existe. plein d’algo deja existant de recherche de pattern sont dispo. C’est un probleme non trivial, et ya vraiment plein de solution. L’aglo connu pour etre le plus efficace est le KMP (Knuth, Morris et Prat).
Tu peux aussi pas t’emmerder et utiliser des regexp qui feront le boulot pour toi.

Ensuite mettre en ram, mutli threader tout ca, c’est que de l’optimisation. A voir si tu as des pb de perf ou pas.
Mais commence deja par mettre en place du code pour chaque etape, et ca prendra forme tout seul.

Ben · Février 3, 2009, 3:19

[quote=“Ravine, post:8, topic: 49051”]Euh, bon, c’est pas du c/cpp mais la commande unix grep c’est pas fait pour ça ? en environnement win, c’est “find”

Alors c’est pas du homemade a la wannagaine en c/cpp, mais bon, faire un batch basé sur ces commande devrait pas prendre plus de quelques minutes, non ? Maintenant, ça ne répond vraiment qu’a la problématique que tu poses en début de thread. Si derriere y’a d’autres besoins, plus évolués que simplement rechercher cette ligne, ça répond probablement pas entierement a ta question.[/quote]

Ah oui effectivement, j’ai repondu a la question “comment on le fait en C / C++”, mais oui, un pauvre find . -name | grep marchera tres bien.

AnA-l · Février 3, 2009, 3:24

Show us the code !

ZGoblin · Février 3, 2009, 3:48

Et en perl ? Ce langage a été conçu à la base pour faire ce genre de manipulation sur les fichiers.

[code]#!/usr/bin/perl

for my $arg (@ARGV) {
open(MONFICHIER, $arg) || die (“Erreur d’ouverture : $arg”);

while (<MONFICHIER>) {
	if ($_ =~ /machaine/) {
		print "ma chaine a été trouvé dans $arg\n";
	}
}

close(MONFICHIER)

}[/code]

Coldorak · Février 3, 2009, 4:25

[quote=“Ravine, post:8, topic: 49051”]Euh, bon, c’est pas du c/cpp mais la commande unix grep c’est pas fait pour ça ? en environnement win, c’est “find”

Alors c’est pas du homemade a la wannagaine en c/cpp, mais bon, faire un batch basé sur ces commande devrait pas prendre plus de quelques minutes, non ? Maintenant, ça ne répond vraiment qu’a la problématique que tu poses en début de thread. Si derriere y’a d’autres besoins, plus évolués que simplement rechercher cette ligne, ça répond probablement pas entierement a ta question.[/quote]

grep -R “chaine à trouver” *

et hop

GloP · Février 3, 2009, 5:06

Ou livre en std avec les outils de devel, findstr FTW!

ZGoblin · Février 3, 2009, 7:33

Totalement hors-sujet, mais j’ai voulu faire une recherche google sur std, j’ai été très surpris par le premier résultat.

GloP · Février 3, 2009, 8:10

Ha ca les abreviations… c’est sur que si standard pouvait se raccourcir en francais en MST ca serait plus choquant

kaneloon · Février 3, 2009, 10:10

Idée conne d’un pseudo dev, tu peux pas plutôt coder un truc qui fout automatiquement tes fichiers dans une BDD (qui aura les fonctions de hash quivontbien™ ) ? La recherche d’un élément sur 400k devrait pas être un soucis…

Berzehk · Février 4, 2009, 7:19

si effectivement il peut changer le support de recherche, je lui conseille de faire un arbre avec les IDs plutot que des fichiers. Mais les foutres en BDD puis lancer la recherche, c’est probablement plus long que faire la recherche tout court.

Moloch · Mars 25, 2009, 4:51

[quote=« xevius, post:1, topic: 49051 »]Bonjour à tous!
Actuellement je fais la recherche « manuellement »: j’ouvre chaque fichier à la recherche de ma chaine, jusqu’à ce que je la trouve (ou pas…)

Le problème c’est que je fais ça dans des dossiers de plus de 200 fichiers textes de plus de 500 lignes et c’est long…

Y-a-t’il une solution rapide en C/C++?[/quote]

Ouvre un ficher, ensuite fait un recherche dedans avec un algorithme non naïf :
[ul]
[li]Algo KMP[/li][li]Algo Rabin Karp[/li][li]Algo Boyer Moor[/li][li]Et d’autres…[/li][/ul]

Le substring matching a des enjeux énormes, tu trouveras donc une littérature abondante sur le sujet. Je pense que dans ton cas tu peux opter pour l’un des trois algorithmes cités ci-dessus, à toi de voir lequel est le plus adapté à ton cas.

Pour de bonnes performances tu peux mapper ton fichier en mémoire virtuelle avec mmap ou CreateFileMapping (selon ton OS). Si tes fichiers sont petits tu peux par exemple avoir un thread qui fait la recherche dans un buffer mémoire pendant qu’un autre prépare les buffers des fichiers suivants.

Je ne pense pas que multithreader à outrance sera très utile, ton goulot d’étranglement deviendra rapidement les I/O.

Si tu as besoin de faire régulièrement des recherches tu peux créer des index de tes fichiers.

Bref…

Vaste sujet.