[C++] Recherche d'1 motif
arthix
Messages postés
53
Date d'inscription
Statut
Membre
Dernière intervention
-
batmat Messages postés 1871 Date d'inscription Statut Membre Dernière intervention -
batmat Messages postés 1871 Date d'inscription Statut Membre Dernière intervention -
Salut !
Recherche d'idées ingénieuses : j'ai deux tableaux, un qui peut être relativement énorme, et un autre contenant un motif à rechercher dans le premier tableau.
Quelle méthode utiliseriez vous pour rechercher le plus rapidement possible, et en utilisant le - de ressources possibles aussi, pour rechercher combien de fois on a les fameux motif dans le premier tableu ?
Thanks !
Recherche d'idées ingénieuses : j'ai deux tableaux, un qui peut être relativement énorme, et un autre contenant un motif à rechercher dans le premier tableau.
Quelle méthode utiliseriez vous pour rechercher le plus rapidement possible, et en utilisant le - de ressources possibles aussi, pour rechercher combien de fois on a les fameux motif dans le premier tableu ?
Thanks !
A voir également:
- [C++] Recherche d'1 motif
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Rechercher ou entrer l'adresse mm - recherche google - Guide
- Recherche photo - Guide
- Je recherche une chanson - Guide
- Rechercher ou entrer l'adresse 4 - recherche google ✓ - Forum Windows
6 réponses
il ya des algo de recheche ds 1 tableau, la complexite allant de n² a n, tu as par ex le quicksort(nlog(n)) , l'algo combinaison (n) , n etant la taille du tableau.
tafiscobar
tafiscobar
Pour effectuer cette recherche, il faut utiliser l'algo de grep.
@++
Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
@++
Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
batmat, reagrdes bien son poste, il a un tableau, il n'a pas de listes du genre renvoye par un pipe du genre : ls -l | grep "toto".
bien sur que le quicksort fait un tri, desole arthix pour cette erreur, je voulais dire recherche dichotomique, merci batmat, now si grep est une fct de biblio qui le fait tant mieux.
tafiscobar
bien sur que le quicksort fait un tri, desole arthix pour cette erreur, je voulais dire recherche dichotomique, merci batmat, now si grep est une fct de biblio qui le fait tant mieux.
tafiscobar
C'est toi qui devrait bien regarder mon post :-)
J'ai dit "algo de grep", pas grep :)
Je l'ai codé pour un mini-projet donné en 1ere année de DUT. Je sais donc qu'il est faisable et bien plus performant (on devait sortir un tableau suivant le nb de caractères à rechercher, le nombre de car. de la chaine dans laquelle rechercher etc.)
l'algo est évidemment plus complexe que la première chose qui vient à l'esprit, mais il n'est pas non plus très compliqué, loin de là.
@++
Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
J'ai dit "algo de grep", pas grep :)
Je l'ai codé pour un mini-projet donné en 1ere année de DUT. Je sais donc qu'il est faisable et bien plus performant (on devait sortir un tableau suivant le nb de caractères à rechercher, le nombre de car. de la chaine dans laquelle rechercher etc.)
l'algo est évidemment plus complexe que la première chose qui vient à l'esprit, mais il n'est pas non plus très compliqué, loin de là.
@++
Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
Salut à tous & merci pour vous réponses !
Un élément important que je n'avais pas cité parceque je voyais mon pb d'un oeil différent, c'est qu'après chaque motif trouvé dans la source de données, il faut insérer une autre quantité de données fixe. Explication, je ne me sens pas clair :
- on recherche le motif "1 2"
- on veut insérer "3 4" après ce motif
- la chaine d'entrée est "1 3 5 1 2 5 1 2 9"
en sortie, on aura donc "1 3 5 1 2 3 4 5 1 2 3 4 9"
Tout le problème réside en fait dans l'allocation de mémoire...
Pour effectuer cette opération, malgrès la taille qui peut parfois être TRES importante du tableau "source, on va retenir l'indice du début du motif dans un nveau tableau, puis dans un second temps, on va générer le nouveau buffer de sortie...
A priori on peut bourriner sur la ram donc tout ca bien ...
merci & A+
Un élément important que je n'avais pas cité parceque je voyais mon pb d'un oeil différent, c'est qu'après chaque motif trouvé dans la source de données, il faut insérer une autre quantité de données fixe. Explication, je ne me sens pas clair :
- on recherche le motif "1 2"
- on veut insérer "3 4" après ce motif
- la chaine d'entrée est "1 3 5 1 2 5 1 2 9"
en sortie, on aura donc "1 3 5 1 2 3 4 5 1 2 3 4 9"
Tout le problème réside en fait dans l'allocation de mémoire...
Pour effectuer cette opération, malgrès la taille qui peut parfois être TRES importante du tableau "source, on va retenir l'indice du début du motif dans un nveau tableau, puis dans un second temps, on va générer le nouveau buffer de sortie...
A priori on peut bourriner sur la ram donc tout ca bien ...
merci & A+