Recherche d'un string dans un vector<string>

Version imprimable

Bonjour à tous !

Je bloque sur une partie de mon code.

Je m'explique : J'ai un fichier CSV que je copie dans un vector<string> via le code suivant :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 void extractionCSV (ifstream& fichComp,vector<string>& vecCSV) { string ligneCourante(""); if(fichComp) { fichComp.seekg(0,ios::beg);//on se place au début du fichier while (getline(fichComp,ligneCourante)) { vecCSV.push_back(ligneCourante); } } }
Ensuite, l'idée est de rechercher un string nom contenue dans un élément de mon vecCSV.

Par exemple, si
nom="toto",
et que
vecCSV[0] = "tot1"
vecCSV[1] = "tot2"
vecCSV[2] = "le toto est à l'eau"
vecCSV[3] = "tot6"
etc...

Alors, je veux pouvoir récupérer vecCSV[2].

Je n'ai pas réussi à y parvenir, j'ai essayé avec std::find, mais il ne me renvoie rien (il me semble que find fait simplement une comparaison de type if(nom == vecCSV[i])).

J'ai le bout de code suivant, qui ne marche donc pas :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 string rechercheLigneComp(string nom, std::vector<std::string> vecCSV) { std::vector< std::string >::iterator it = vecCSV.begin(); for( ; ; ) { it = std::find(it, vecCSV.end(), nom); if ( it == vecCSV.end() ) return ""; else return vecCSV[std::distance( vecCSV.begin(), it++ )]; } }
Si quelqu'un avait des pistes pour m'aiguiller, je suis preneur !

Je précise par ailleurs que je dois effectuer la recherche de "nom" plusieurs centaines de fois. J'ai testé de rechercher "nom" directement dans le CSV (code ci-dessous), ça fonctionne bien mais la recherche est bien trop longue, c'est pourquoi je tente cette 2nde méthode.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 string rechercheLigneComp(string nom, ifstream& fichComp) { string ligneCourante(""), ligneSortie(""); if(fichComp) { fichComp.seekg(0,ios::beg);//on se place au début du fichier while (getline(fichComp,ligneCourante)) { if(ligneCourante.find(nom) != std::string::npos) { ligneSortie=ligneCourante; break; } } } return ligneSortie; }

Salut

Utilise find_if

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
#include <algorithm>
 
int main() {
  std::vector<std::string> vecCSV {{
    "tot1"
      , "tot2"
      , "le toto est a l'eau"
      , "tot6"
  }};
 
  std::string key = "toto";
  auto elem = std::find_if(begin(vecCSV), end(vecCSV), [&key](std::string const& elem) { return elem.find(key) != std::string::npos; });
  if (elem != end(vecCSV)) {
    std::cout << "Found \"" << (*elem) << "\" at pos " << std::distance(begin(vecCSV),elem) << "\n";
  }
  return 0;
}

01/04/2015, 11h13
El_bennito

Nickel, c'est exactement ce que je voulais !:merci:

Cela dit, cela ne règle pas mon problème initial : le temps d'exécution du programme. Il reste très long à exécuter...

Pour information, mon fichier CSV fait environ 17000 lignes (donc mon vector vecCSV a 17000 éléments), et je dois le parcourir à peu près 800 fois.

Je m'y prend peut-être pas de la manière optimale pour effectuer ces recherches, y-a-t-il une méthode plus optimisée ?
01/04/2015, 11h17
ternel

Si l'ordre des éléments n'est pas contraint d'être celui du fichier, tu peux préférer un set.
Tu peux aussi trier le vector, puis utiliser std::binary_search

Hello,

Si ce que tu recherches est bien délimité (UN mot par exemple), il est possible de stocker ton texte dans une (unordered)map.

La création de cette map sera plus longue qu'une simple création de vecteur, mais la recherche devrait être plus rapide.

Création de la map

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef std::vector<int> line_t;
typedef std::unordered_map<std::string, line_t> map_t;
 
void insert(map_t & map, std::string const& word, int line) {
	using std::begin;
	using std::end;
 
	auto it = std::find(begin(map), end(map), word);
	if(it == end(map)) { // nouveau mot
		it = map.insert(std::make_pair(word, line_t())).first;
	}
	it->second.push_back(line);
}
 
std::unordered_map<std::string, std::vector<int>> words;
//vecCSV[0] = "tot1" devient
insert(words, "tot1", 0);
//vecCSV[2] = "le toto est à l'eau" devient
insert(words, "le", 2);
insert(words, "toto", 2);
insert(words, "est", 2);
insert(words, "à", 2);
insert(words, "l'eau", 2);
// etc...

Et recherche

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// recherche de toto
line_t const& search(map_t const& map, std::string const& word) {
	using std::begin;
	using std::end;
	auto it = std::find(begin(map), end(map), word);
	if(it == end(map)) {
		return line_t(); // pas de problème de durée de vie vu qu'on retourne une ref constante ?
	}
	return it->second;
}
 
auto results = search(words, "toto");
for(int i: results) {
	std::cout << "'toto' à la ligne: " << i << '\n';
}

01/04/2015, 13h38
El_bennito

Merci pour toutes ces pistes !

Citation:

Si ce que tu recherches est bien délimité (UN mot par exemple), il est possible de stocker ton texte dans une (unordered)map

Hélas, non, ce n'est pas le cas, la chaîne que je recherche peut contenir des espaces, des tirets, etc.

Citation:

Si l'ordre des éléments n'est pas contraint d'être celui du fichier, tu peux préférer un set.
Tu peux aussi trier le vector, puis utiliser std::binary_search

le truc avec binary_search, c'est qu'il te renvoie simplement un booléen qui t'indique si la chaîne est présente dans mon vecteur (ou la sous-chaine dans mon cas, en adaptant la fonction Compare), mais pas à quel index. Je ne pourrais donc pas récupérer la chaine vecCSV[index] qui contient ma sous-chaine.

De plus, pour effectuer le tri, je ne sais pas trop comment m'y prendre, sachant que ma sous-chaine n'est pas en 1ère place de la chaine dans le vecteur.

Je reprécise, ça sera sans doute plus clair.

1 - J'ai un fichier CSV d'entrée, de 17 000 lignes environ, au format suivant :
101A,"TOTAL-X 204M","392","FR","22.60","33","406","398","","0","2015-02-17","commentaire eventuel"

2 - J'ai des string que je récupère en parcourant un fichier *.txt (avec d'autres infos également). Ces strings correspondent en fait au 2ème champ du CSV (TOTAL-X 204M dans mon exemple).

3 - Je voudrais donc récupérer la ligne complète du CSV qui correspond au string "courant".

4 - Je fais ensuite un traitement par la suite sur ces données.

Le point bloquant est donc la partie 3, où je n'arrive pas à récupérer rapidement la ligne du CSV.
01/04/2015, 14h04
ternel

Alors tu devrais faire un map du N° champ vers la ligne entière.
Ca n'est pas difficile de chercher ce champ, avec std::getline(stream, string, delimiter).

Mieux encore, tu pourrais avoir une classe représentant cette ligne
01/04/2015, 14h30
jblecanard

Citation:

Envoyé par leternel

Alors tu devrais faire un map du N° champ vers la ligne entière. Ca n'est pas difficile de chercher ce champ, avec std::getline(stream, string, delimiter)Mieux encore, tu pourrais avoir une classe représentant cette ligne

Oui mais attention, on voit que dans le format de l'op, il y a des quotes, or si le 2ème champs contient une virgule dans le champ entre quotes, je supppose que l'op est censé bien l'interpréter ? Si oui, alors il va falloir faire plus malin qu'un simple getline

Citation:

Envoyé par leternel

Mieux encore, tu pourrais avoir une classe représentant cette ligne

Heu, est-ce que ça vaut vraiment la peine ? C'est juste un tableau de chaînes, un std::array fait amplement l'affaire pour ce qu'on connaît du besoin actuel. Une classe n'aurait du sens que s'il y a vraiment une intelligence de traitement derrière.
01/04/2015, 14h35
ternel

En effet, mais c'est une question à se poser.
01/04/2015, 20h24
CedricMocquillon

Mon conseil: mesure bien où tu perds ton temps. J'ai pas l'impression que ce soit vraiment énorme comme recherche. Vérifie bien que tes tests sont réalisés en release et que tu ne fais pas de copies inutiles (dans ton post d'origine, tu passes le vecteur de string en copie de ta fonction recherche par exemple). Après avoir identifié d'où provient ton bottleneck, tu pourras ensuite envisager des solutions.
01/04/2015, 21h12
jo_link_noir

Pour le tri et la recherche:

std::sort
std::lower_bounds
02/04/2015, 01h07
JolyLoic

Tes chaînes elles-mêmes dans le tableau sont-elles longues ou courtes ?

Pourquoi veux-tu faire 800 recherches ? Connais-tu dès le début la liste de toutes les recherches à effectuer (rechercher 800 strings dans 1 string peut être fait de manière plus intelligente qu'en recommençant 800 fois une recherche d'une string, comme par exemple les algos Aho–Corasick ou Rabin–Karp).

Tu mets combien de temps pour l'instant ? Il faudrait que tu en mettes combien ?
02/04/2015, 09h15
stendhal666

Je plussoie la réponse de JolyLoic.

La recherche naïve a un complexité P * M * N, avec P = 17000, M = moy_len(ligne) et N = 800 * moy_len(mot)

La complexité géométrique est inévitable mais M et N peuvent être réduits:
- pour M: je verrais, simple et en une passe, la création d'un vecteur de paires (int = ligneDansLeTabInitial, std::string deuxiemeChampDeLaLigne) -> M + P * (M/4) * N (à peu près)
- pour M * N: l'algorithme de Aho-Corasick est le plus prometteur et le mieux documenté. La complexité finale est M+N+O où O est le nombre de correspondances

Au total ça ferait:
M + P * (M/4 + N + O)

Je mets un lien vers un article qui m'a paru bien:
https://www.informit.com/guides/cont...net&seqNum=769
02/04/2015, 09h53
ternel
Si tu as la liste des 800 avant celles des 17000, tu peux procéder dans l'autre sens.
```
constituer un set des 800 lignes.
Pour chaque 17000 entrées
    extraire le second champ.
    si cette valeur est dans le set des 800
        stocker/utiliser cette ligne.
```
Note que cette approche fonctionne aussi bien en lisant les entrée directement du fichier ou dans un vecteur

La complexité est celle du set plus celle des recherches, c'est à dire: (K log K) + N * (extraction + log K), avec K = 800 et N = 17000.
Sachant que l'extraction est de l'ordre de 1 comparaison de chaînes (=un parcours de chaine bien fait), ca donne donc environ N log K.

Ce qui est franchement mieux que le N * K requis pour matcher chaque 800 lignes avec chaque 17000 entrées.

C'est la même idée sous-jacente que la map: utiliser le tri à la construction pour réduire le temps de recherche.

Par comparaison, la map<2e champ, ligne>, coûterait N log N + K log N, ce qui revient à N log N.
C'est moins bon, mais tu disposes pour la suite de toutes les lignes du fichier, triées par ce deuxième champ.
02/04/2015, 11h17
stendhal666
Citation:
Envoyé par leternel

si cette valeur est dans le set des 800 stocker/utiliser cette ligne.
Oui mais d'après ce que j'ai compris, il ne s'agit pas seulement de savoir si un des 800 mots apparaît dans cette ligne mais de répertorier les couples: mot / ligne, c'est-à-dire d'obtenir une hash-map:
{ toto : [1,8,425,10021] , etc. } // les entiers sont les numéros de ligne, of course

j'imagine une fonction:

void feedMatches( const AhoCorasikTree& act, std::unordered_map<std::string, std::vector<int>>& matches, const std::string& src, unsigned index);

où:
- act est la forme "compilée" des 800 mots à matcher
- matches une map qui permet de retrouver les lignes associées à chaque mot
- src le champ à regarder et index son rang dans le vecteur de lignes extrait du fichier

Chill guys ! On peut essayer des trucs plus simples avant de vouloir bourriner avec des algos poussés.

Du coup histoire de se remettre dans le débat, j'ai fait le test. J'ai comparé le parcours multiple du vector avec la construction d'une unordered_map puis son parcours. Le résultat est sans appel : pour un CSV de 20000 lignes et 800 clés à rechercher le parcours du vecteur est de l'ordre de 1000ms, la construction de la hash map de l'ordre de 25ms et son parcours de 0ms. Bien sûr, ce qui compte c'est la différence, pas les performances brutes qui dépendent de la machine et de l'optimisation choisie. En debug ou en optimisé, les perfs restent à peu près les mêmes.

Voici le code:

Code:

1
2
3
4
5
6
7
8
9
10
11
#!/usr/bin/env python
 
upper=20000
nb_to_search=800
step=upper/nb_to_search
with open("file1.csv","w") as f1:
  with open("file2.txt","w") as f2:
    for i in range(0,upper):
      f1.write('%dA,"TOTAL-X %dM","%d","FR","%f","%d","%d","%d","","0","2015-02-17","commentaire eventuel"\n' % (i,i+100,i+33,i/2.3,i+20,i/55,i/254))
      if i%step == 0:
        f2.write('TOTAL-X %dM\n' % (i+100))

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <unordered_map>
 
int main() {
  using namespace std;
  using namespace std::chrono;
 
  ifstream data_if("file1.csv");
  ifstream key_if("file2.txt");
 
  if(data_if && key_if) {
    vector<string> data;
    string line;
    while(getline(data_if,line))
      data.emplace_back(line);
 
    vector<string> keys;
    while(getline(key_if,line))
      keys.emplace_back(line);
 
 
    {
      int nb_found = 0;
      auto t0 = high_resolution_clock::now();
      for(auto const& key : keys) {
        auto item = find_if(begin(data),end(data),[&key](string const& value) { return value.find(key) != string::npos; });
        if (item != end(data))
          ++nb_found;
      }
      auto t1 = high_resolution_clock::now();
      std::cout << "Found " << nb_found << " items in " << duration_cast<milliseconds>(t1-t0).count() << "ms" << std::endl;
    }
 
    {
      unordered_map<string,vector<size_t>> dictionary;
      auto t0 = high_resolution_clock::now();
      for(size_t index=0; index < data.size(); ++index) {
        string const& dataline = data[index];
        istringstream linestream(dataline);
        string f1, f2;
        getline(linestream,f1,',');
        getline(linestream,f2,',');
        // Remove quotes
        if (f2[0] == '"' && f2[f2.size()-1] == '"')
          f2 = f2.substr(1,f2.size()-2);
 
        dictionary[f2].emplace_back(index);
      }
 
      auto t1 = high_resolution_clock::now();
      std::cout << "Dictionary built in " << duration_cast<milliseconds>(t1-t0).count() << "ms" << std::endl;
 
      int nb_found = 0;
      auto t2 = high_resolution_clock::now();
      for(auto const& key : keys) {
        if (dictionary[key].size())
          ++nb_found;
      }
      auto t3 = high_resolution_clock::now();
      std::cout << "Found " << nb_found << " items in " << duration_cast<milliseconds>(t3-t2).count() << "ms" << std::endl;
    }
  }
 
  return 0;
}

Code:

1
2
3
Found 800 items in 1049ms
Dictionary built in 24ms
Found 800 items in 0ms

Si ça n'est pas encore assez rapide, alors peut-être faudra-t-il explorer d'autres algos, mais le gain est déjà énorme.

02/04/2015, 16h25
ternel

C'est rassurant.
En général, il vaut toujours mieux chercher dans une collection triée, tu passes de N à log N. (c'est à dire 10 au lieu de 1000, et 20 au lieu de 1 million)
C'est le cas des std::map et autres std::set.
02/04/2015, 17h05
stendhal666

Citation:

for (auto const& key : keys) {
if (dictionary[key].size())
++nb_found;
}

Le gain est énorme mais là ça ne répond pas à la question posée: ton programme ne fonctionne que si le texte recherché correspond à l'intégralité du champ 2 de la ligne csv.

Mettons que j'aie besoin des champs de totaux, des champs de 2015, et des champs des mois de février ("total" "2015" "02"), pcq je veux calculer mon chiffre d'affaires depuis la création de l'entreprise, en 2015, et pendant les mois de février.
Il faut donc qu'il y ait 3 matches pour "total-02-2015". C'est à ça que sert l'algo-très-compliqué.
Sinon on est réduit à faire 3*17000 passes, et comme la fonction de hachage ne peut pas être appliquée puisqu'il s'agit d'une sous-chaîne, unordered_map ne sert à rien...

@leternel: unordered_map, comme son nom l'indique, n'est pas triée... normalement c'est du temps constant

EDIT::

Citation:

2 - J'ai des string que je récupère en parcourant un fichier *.txt (avec d'autres infos également). Ces strings correspondent en fait au 2ème champ du CSV (TOTAL-X 204M dans mon exemple).

:roll::oops:
02/04/2015, 17h19
jblecanard

Citation:

Envoyé par stendhal666

Le gain est énorme mais là ça ne répond pas à la question posée: ton programme ne fonctionne que si le texte recherché correspond à l'intégralité du champ 2 de la ligne csv.

Oui bien évidemment, il me semble que l'op faisait du matching de pattern pour trouver la ligne sans faire l'effort d'exploiter son formatage, alors que l'égalité peut être utilisée. Si ce n'est pas le cas, en effet, c'est foutu.