Spiegazione dell'ottimizzazione del codice

Ottimizza e spiega il codice C++, concentrandoti sulla complessità temporale.

Puoi eseguire query direttamente su un modello e testare i risultati restituiti quando utilizzi valori di parametro diversi con la console Cloud o richiamando direttamente l'API Vertex AI.

Istruzioni di sistema

Sei un programmatore C++ che ama ottimizzare il codice. Dopo aver ottimizzato il codice fornito, spiega le modifiche e i miglioramenti della complessità temporale.

Prompt In formato libero

Ho un codice C++ che stampa il numero di volte in cui un carattere si verifica in una stringa, ma mi è stato detto che non è efficiente.

Puoi renderlo più efficiente utilizzando una mappa?

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

Risposta

Il codice originale ha una complessità temporale di O(n³), dove n è la lunghezza della stringa di input. Questo è dovuto ai cicli nidificati: il ciclo esterno esegue l'iterazione di ogni carattere, il secondo ciclo esegue l'iterazione dell'intera stringa per ogni carattere e il terzo ciclo (sebbene apparentemente ridondante) esegue comunque l'iterazione della lunghezza della stringa nel peggiore dei casi. Il ciclo aggiuntivo di controllo di already_printed aggiunge un altro fattore O(n), anche se è meno significativo dei cicli nidificati.

Il seguente codice ottimizzato utilizza un std::map per ottenere una complessità temporale di O(n log n). Il fattore log n deriva dalle operazioni di inserimento e ricerca della mappa (che in genere vengono implementate utilizzando alberi di ricerca binari bilanciati).

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

Spiegazione dei miglioramenti:

  1. Utilizzo di std::map: il codice originale contava in modo inefficiente le occorrenze di ciascun carattere più volte. std::map (o std::unordered_map per un rendimento potenzialmente più rapido nel caso medio, ma leggermente superiore nel caso peggiore) memorizza ogni carattere come chiave e il relativo conteggio come valore. In questo modo viene eliminato il conteggio ridondante.

  2. Iterazione una volta:il codice ottimizzato esegue l'iterazione della stringa di input una sola volta per compilare la mappa char_counts. Ciò riduce notevolmente il numero di operazioni rispetto ai cicli nidificati del codice originale.

  3. Conteggio efficiente dei caratteri:la riga char_counts[c]++; incrementa in modo efficiente il conteggio di ciascun carattere. Se il carattere non è già presente nella mappa, viene aggiunto con un conteggio pari a 1; in caso contrario, il conteggio esistente viene incrementato.

  4. Eliminazione dei controlli ridondanti: il controllo already_printed del codice originale era necessario a causa del suo metodo di conteggio inefficiente. std::map gestisce questo problema in modo intrinseco: ogni carattere viene conteggiato una sola volta e il ciclo finale esegue l'iterazione della mappa, stampando ogni carattere e il relativo conteggio.

In sintesi, il codice ottimizzato offre un miglioramento sostanziale dell'efficienza riducendo la complessità temporale da O(n³) a O(n log n). Per stringhe di input di grandi dimensioni, questa differenza sarà notevole. L'utilizzo di std::unordered_map potrebbe migliorare ulteriormente le prestazioni nel caso medio fino a O(n), ma a scapito di un peggioramento delle prestazioni nel caso peggiore. La scelta dipende dall'applicazione specifica e dal fatto che il rendimento peggiore sia un problema critico.
Modello: gemini-1.5-flash-002
Temperatura: 0,2
Numero massimo di token di output: 8192
TopK: 40,0
TopP: 0,95