Codeoptimierung

Ich habe einen C++-Code, der die Häufigkeit anzeigt, mit der ein Zeichen in einem String vorkommt. Mir wurde gesagt, dass er ineffizient ist.

Können Sie das mit einer Karte effizienter gestalten?

#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;
}

Der ursprüngliche Code hat eine Zeitkomplexität von O(n³), wobei n die Länge des Eingabestrings ist. Das liegt an den verschachtelten Schleifen: Die äußere Schleife durchläuft jedes Zeichen, die zweite Schleife durchläuft für jedes Zeichen den gesamten String und die dritte Schleife (obwohl scheinbar redundant) durchläuft im schlimmsten Fall die Länge des Strings. Die zusätzliche Schleife, die nach already_printed sucht, fügt einen weiteren O(n)-Faktor hinzu, der jedoch weniger signifikant ist als die verschachtelten Schleifen.

Im folgenden optimierten Code wird ein std::map verwendet, um eine Zeitkomplexität von O(n log n) zu erreichen. Der Faktor log n stammt aus den Einfüge- und Suchvorgängen der Map, die in der Regel mithilfe von ausgewogenen binären Suchbäumen implementiert werden.

#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;
}

Erläuterung der Verbesserungen:

1. std::map verwenden: Im ursprünglichen Code wurden die Vorkommen jedes Zeichens ineffizient mehrmals gezählt. Bei der std::map (oder std::unordered_map für eine potenziell schnellere durchschnittliche Leistung, aber etwas höhere Worst-Case-Leistung) wird jedes Zeichen als Schlüssel und seine Anzahl als Wert gespeichert. So wird eine redundante Zählung vermieden.

2. Einmal iterieren: Der optimierte Code durchläuft den Eingabestring nur einmal, um die char_counts-Map zu füllen. Dadurch wird die Anzahl der Vorgänge im Vergleich zu den verschachtelten Schleifen des ursprünglichen Codes erheblich reduziert.

3. Effiziente Zeichenzählung: In Zeile char_counts[c]++; wird die Anzahl der Zeichen effizient erhöht. Wenn das Zeichen noch nicht in der Zuordnung enthalten ist, wird es mit einer Häufigkeit von 1 hinzugefügt. Andernfalls wird die vorhandene Häufigkeit erhöht.

4. Redundante Prüfungen entfernen: Die already_printed-Prüfung des ursprünglichen Codes war aufgrund der ineffizienten Zählmethode erforderlich. Das übernimmt std::map automatisch: Jedes Zeichen wird nur einmal gezählt und die letzte Schleife durchläuft die Zuordnungstabelle und druckt jedes Zeichen und seine Häufigkeit aus.

Zusammenfassend lässt sich sagen, dass der optimierte Code die Effizienz erheblich verbessert, da die Zeitkomplexität von O(n³) auf O(n log n) reduziert wird. Bei großen Eingabestrings ist dieser Unterschied enorm. Mit std::unordered_map lässt sich die durchschnittliche Leistung auf O(n) weiter verbessern, allerdings auf Kosten einer etwas höheren Leistung im Worst-Case-Szenario. Die Wahl hängt von der jeweiligen Anwendung und davon ab, ob die Leistung im Worst-Case-Szenario ein kritisches Problem darstellt.