C++ Comment rendre ce code plus efficace?

Question

J'ai un tableau de mots, et j'ai un fichier texte. Ce que je veux faire est d'utiliser le tableau de mots et de rechercher dans le fichier texte, compter le nombre de fois que chaque mot dans le tableau apparaît dans le fichier texte.

J'ai envisagé d'utiliser une boucle For, mais cela m'a donné le total du nombre de mots et non le nombre de mots individuels pour chacun. Je ne peux pas mettre le fichier texte dans un tableau car il y a environ 40000 mots dans le fichier texte. Après le comptage, je souhaite diviser chaque compte par une valeur entière appelée "échelle". Et puis mulitply une chaîne par le nouveau nombre de compte.

Donc, je le fais actuellement comme indiqué ci-dessous. Y at-il de toute façon je peux rendre cela plus efficace?

Toute aide est grandement appréciée.

Tableau de mots = mots de test.

Nom du fichier = testF.

inWord = chaque mot du fichier.

while(testF >> inWord) 
    {if (inWord == testwords[0]){ 
      count1++; 
      } 
     if (inWord == testwords[1]){ 
      count2++; 
      } 
     if (inWord == testwords[2]){ 
      count3++; 
      } 
     if (inWord == testwords[3]){ 
      count4++; 
      } 
     if (inWord == testwords[4]){ 
      count5++; 
      } 
     if (inWord == testwords[5]){ 
      count6++; 
      } 
     if (inWord == testwords[6]){ 
      count7++; 
      } 
     if (inWord == testwords[7]){ 
      count8++; 
      } 
} 
cout << testwords[0] << " " << count1 << " " << s1.append(count1/scale, '*') << endl; 
cout << testwords[1] << " " << count2 << " " << s2.append(count2/scale, '*') << endl; 
cout << testwords[2] << " " << count3 << " " << s3.append(count3/scale, '*') << endl; 
cout << testwords[3] << " " << count4 << " " << s4.append(count4/scale, '*') << endl; 
cout << testwords[4] << " " << count5 << " " << s5.append(count5/scale, '*') << endl; 
cout << testwords[5] << " " << count6 << " " << s6.append(count6/scale, '*') << endl; 
cout << testwords[6] << " " << count7 << " " << s7.append(count7/scale, '*') << endl; 
cout << testwords[7] << " " << count8 << " " << s8.append(count8/scale, '*') << endl; 

Answer 1

Avant de vous soucier de l'efficacité, vous devriez vous inquiéter de l'approche. Vous n'utilisez pas de structures de données logiques. Au lieu d'avoir 8 comptes séparés, gardez un tableau de comptes. Ou mieux encore, gardez une carte de mot -> compte. Heureusement dans cette situation, un code plus propre correspondra à une exécution beaucoup plus rapide. En particulier, utilisez un std::map<std::string, size_t>. Alternativement, si vous utilisez C++ 11, vous pouvez utiliser un std :: unordered_map pour de meilleures performances.

En supposant que vous lisez vos mots de cin:

std::map<std::string, size_t> counts; 

std::string word; 

while (std::cin >> word) { 
    ++counts[word]; 
} 

for (std::map<std::string, size_t::const_iterator it = counts.begin(), 
    end = counts.end(); it != end; ++it) { 
    std::cout << "The word '" << it->first << " appeared " 
       << it->second << " times" << std::endl; 
} 

Documentation pour std :: carte.

Documentation pour std :: unordered_map. Pour ce que ça vaut, std :: unordered_map est implémenté comme un hash map, et std :: map est implémenté (probablement toujours) en utilisant une structure binaire équilibrée comme structure de support.

Answer 2

Mettre en place un std::map<std::string, unsigned long long>, parcourons le mot de documents par mot, et incrémenter le compteur pour chaque mot:

std::map<std::string, unsigned long long> wordMap; 

std::string word; // read words into this string 
... 
wordMap[word]++; // increase counter each time a word is found. First call will insert 0. 

Ensuite, vous pouvez boucler sur votre tableau de mots, de vérifier les entrées de la carte:

for (unsigned int i = 0; i < nWords; ++i) 
{ 
    std::cout << "Word " << testWords[i] << " was found " << wordMap[testWords[i]] << " times\n"; 
} 

Chaque fois qu'un nouveau mot est trouvé, myMap[word] insérera une paire clé-valeur word : 0.

Si vous avez C++ 11, vous pouvez essayer avec un std::unordered_map et choisir celui qui fonctionne le mieux.

Answer 3

Avec seulement 8 valeurs à comparer, vous pouvez probablement trouver un meilleur algorithme de hachage, que dans std. Il ne peut se compose des deux premiers caractères, ou le dernier caractère, ou la chaîne longueur:

while (std::cin >> word) { 
    int i=my_hash(word); 
    if (word==my_sparse_hash_table[i].word) my_sparse_hash_table[i].count++; 
} 

Tout en utilisant votre méthode:

while (std::cin >> word) { 
    for (int i=0;i<N;i++) 
    if (word == myTable[i].word) { myTable[i].count++; break; } 
} // earlies break out of the loop 

micro-optimisations comprennent le déplacement d'une entrée trouvée vers le début du tableau myTable.

Answer 4

Toutes les autres réponses ici sont de très bonnes suggestions. Une petite optimisation que vous pourriez faire est d'utiliser sinon dans votre code existant.

if (inWord == testwords[0]) 
{ 
    count1++; 
} 
if (inWord == testwords[1]) 
{ 
    count2++; 
} 

pourrait être remplacé par

if (inWord == testwords[0]) 
{ 
    count1++; 
} 
else if (inWord == testwords[1]) 
{ 
    count2++; 
} 

Le concept est que si inword fait élément match 0, il est peu probable correspond à aucun des autres éléments. En aucun cas Profilers êtes-vous ami.