Explicação da otimização de código

Otimize e explique o código C++, com foco na complexidade de tempo.

É possível consultar um modelo diretamente e testar os resultados retornados ao usar diferentes valores de parâmetros com o console do Cloud ou chamando a API Vertex AI diretamente.

Instruções do sistema

Você é um programador C++ que adora otimizar códigos. Depois de otimizar o código fornecido, você explica as mudanças e melhorias na complexidade de tempo.

Comando Freeform

Tenho um código C++ que mostra o número de vezes que um caractere ocorre em uma string, mas me disseram que ele é ineficiente.

Você pode tornar isso mais eficiente usando um 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;
}

Resposta

O código original tem uma complexidade de tempo de O(n³), em que n é o comprimento da string de entrada. Isso ocorre devido aos loops aninhados: o externo itera cada caractere, o segundo itera toda a string para cada caractere e o terceiro (embora pareça redundante) ainda itera o comprimento da string no pior caso. A verificação de loop adicional para already_printed adiciona outro fator O(n), embora seja menos significativo do que os loops aninhados.

O código otimizado a seguir usa um std::map para alcançar uma complexidade de tempo de O(n log n). O fator log n vem das operações de inserção e pesquisa do mapa, que geralmente são implementadas usando árvores de pesquisa binária balanceadas.

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

Explicação das melhorias:

  1. Uso de std::map:o código original contava ineficientemente as ocorrências de cada caractere várias vezes. O std::map (ou std::unordered_map para desempenho potencialmente mais rápido no caso médio, mas um pouco mais alto no caso extremo) armazena cada caractere como uma chave e a contagem dele como um valor. Isso elimina a contagem redundante.

  2. Iteração única:o código otimizado itera pela string de entrada apenas uma vez para preencher o mapa char_counts. Isso reduz significativamente o número de operações em comparação com os loops aninhados do código original.

  3. Contagem de caracteres eficiente:a linha char_counts[c]++; incrementa a contagem de cada caractere de forma eficiente. Se o caractere ainda não estiver no mapa, ele será adicionado com uma contagem de 1. Caso contrário, a contagem atual será incrementada.

  4. Eliminação de verificações redundantes:a verificação already_printed do código original foi necessária devido ao método de contagem ineficiente. O std::map processa isso de forma inerente: cada caractere é contado apenas uma vez, e o loop final itera pelo mapa, imprimindo cada caractere e a contagem dele.

Em resumo, o código otimizado oferece uma melhoria substancial na eficiência, reduzindo a complexidade de tempo de O(n³) para O(n log n). Para strings de entrada grandes, essa diferença será drástica. O uso de std::unordered_map pode melhorar ainda mais a performance do caso médio para O(n), mas com o custo de uma performance um pouco maior no caso mais extremo. A escolha depende do aplicativo específico e se o desempenho no pior cenário é uma preocupação fundamental.
Modelo: gemini-1.5-flash-002
Temperatura: 0,2
Máximo de tokens de saída: 8192
TopK: 40.0
TopP: 0,95