Explication de l'optimisation du code

Restez organisé à l'aide des collections Enregistrez et classez les contenus selon vos préférences.

J'ai un code C++ qui affiche le nombre de fois où un caractère apparaît dans une chaîne, mais on m'a dit que ce n'était pas efficace.

Pouvez-vous l'améliorer à l'aide d'une carte ?

#include <iostream>
#include <string>

using namespace std;

int main() {
  string input;
  cout << "Enter a string: ";
  getline(cin, input);

  for (int i = 0; i < input.length(); ++i) {
    char current_character = input[i];
    int count = 0;
    for (int j = 0; j < input.length(); ++j) {
      for (int k = 0; k < input.length(); ++k) {
        if (input[j] == current_character && j == k) {
          ++count;
        }
      }
    }

    bool already_printed = false;
    for (int k = 0; k < i; ++k) {
      if (input[k] == current_character) {
        already_printed = true;
        break;
      }
    }

    if (!already_printed) {
      cout << current_character << ": " << count << endl;
    }
  }

  return 0;
}

Le code d'origine présente une complexité temporelle de O(n³), où n est la longueur de la chaîne d'entrée. Cela est dû aux boucles imbriquées : la boucle externe parcourt chaque caractère, la deuxième boucle parcourt la chaîne entière pour chaque caractère, et la troisième boucle (bien que redondante) parcourt toujours la longueur de la chaîne dans le pire des cas. La vérification de la boucle supplémentaire pour already_printed ajoute un autre facteur O(n), bien qu'il soit moins important que les boucles imbriquées.

Le code optimisé suivant utilise un std::map pour obtenir une complexité temporelle de O(n log n). Le facteur log n provient des opérations d'insertion et de recherche de la carte (généralement implémentées à l'aide d'arborescences de recherche binaires équilibrées).

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
  string input;
  cout << "Enter a string: ";
  getline(cin, input);

  map<char, int> char_counts;
  for (char c : input) {
    char_counts[c]++;
  }

  for (auto const& [key, val] : char_counts) {
    cout << key << ": " << val << endl;
  }

  return 0;
}

Explication des améliorations :

1. Utilisation de std::map : le code d'origine ne comptait pas efficacement les occurrences de chaque caractère plusieurs fois. std::map (ou std::unordered_map pour des performances moyennes potentiellement plus rapides, mais légèrement plus élevées dans le cas le plus défavorable) stocke chaque caractère en tant que clé et son nombre en tant que valeur. Cela élimine le décompte redondant.

2. Itération unique : le code optimisé n'itère que la chaîne d'entrée une seule fois pour renseigner la carte char_counts. Cela réduit considérablement le nombre d'opérations par rapport aux boucles imbriquées du code d'origine.

3. Comptage efficace des caractères : la ligne char_counts[c]++; incrémente efficacement le nombre de caractères. Si le caractère ne figure pas déjà dans la carte, il est ajouté avec un nombre de 1. Sinon, son nombre existant est incrémenté.

4. Élimination des vérifications redondantes : la vérification already_printed du code d'origine était nécessaire en raison de sa méthode de comptage inefficace. std::map gère cela de manière inhérente. Chaque caractère n'est compté qu'une seule fois, et la boucle finale parcourt la carte, imprimant chaque caractère et son nombre.

En résumé, le code optimisé améliore considérablement l'efficacité en réduisant la complexité temporelle de O(n³) à O(n log n). Pour les chaînes d'entrée volumineuses, cette différence est considérable. L'utilisation de std::unordered_map peut améliorer les performances dans le cas moyen à O(n), mais au prix de performances légèrement supérieures dans le cas le plus défavorable. Le choix dépend de l'application spécifique et de la question de savoir si les performances dans le pire des cas sont un problème critique.