Explicación de la optimización de código

Tengo un código C++ que imprime la cantidad de veces que un carácter aparece en una cadena, pero me dijeron que no es eficiente.

¿Puedes hacerlo más eficiente con un mapa?

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

El código original tiene una complejidad temporal de O(n³), donde n es la longitud de la cadena de entrada. Esto se debe a los bucles anidados: el bucle externo itera por cada carácter, el segundo bucle itera por toda la cadena para cada carácter y el tercer bucle (aunque parezca redundante) aún itera por la longitud de la cadena en el peor de los casos. El bucle adicional que verifica already_printed agrega otro factor O(n), aunque es menos significativo que los bucles anidados.

El siguiente código optimizado usa un std::map para lograr una complejidad temporal de O(n log n). El factor log n proviene de las operaciones de inserción y búsqueda del mapa (que suelen implementarse con árboles de búsqueda binaria equilibrados).

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

Explicación de las mejoras:

1. Con std::map: El código original contaba de forma ineficiente las ocurrencias de cada carácter varias veces. std::map (o std::unordered_map para un rendimiento potencialmente más rápido en el caso promedio, pero ligeramente más alto en el peor caso) almacena cada carácter como una clave y su recuento como un valor. Esto elimina el recuento redundante.

2. Iteración una vez: El código optimizado itera a través de la cadena de entrada solo una vez para propagar el mapa char_counts. Esto reduce significativamente la cantidad de operaciones en comparación con los bucles anidados del código original.

3. Cálculo eficiente de caracteres: La línea char_counts[c]++; incrementa de manera eficiente el recuento de cada carácter. Si el carácter aún no está en el mapa, se agrega con un recuento de 1. De lo contrario, se incrementa su recuento existente.

4. Eliminación de verificaciones redundantes: La verificación already_printed del código original era necesaria debido a su método de recuento ineficiente. std::map controla esto de forma inherente; cada carácter se cuenta solo una vez, y el bucle final itera por el mapa, imprime cada carácter y su recuento.

En resumen, el código optimizado proporciona una mejora sustancial en la eficiencia, ya que reduce la complejidad temporal de O(n³) a O(n log n). En el caso de cadenas de entrada grandes, esta diferencia será significativa. El uso de std::unordered_map podría mejorar aún más el rendimiento del caso promedio a O(n), pero a costa de un rendimiento ligeramente más alto en el caso peor. La elección depende de la aplicación específica y de si el rendimiento en el peor de los casos es una preocupación fundamental.