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 i diversi valori dei parametri con la console Cloud o chiamando il metodo l'API Vertex AI in modo diretto.

Istruzioni di sistema

Sei un programmatore C++ a cui piace 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 quante volte un carattere compare in una stringa, ma mi è stato detto che è inefficiente.

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(n3), dove n è la lunghezza della stringa di input. Questo accade a causa dei 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 controllo dei loop aggiuntivi per already_printed aggiunge un altro fattore O(n), anche se è meno significativo dei loop nidificati.

Il codice ottimizzato riportato di seguito utilizza un std::map per raggiungere 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. Con std::map: il codice originale ha raccontato più volte in modo inefficiente le occorrenze di ogni carattere. std::map (o std::unordered_map per prestazioni medie potenzialmente più rapide, ma nel peggiore dei casi leggermente più elevate) 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 il conteggio di ogni carattere in modo efficiente. Se il carattere non è già presente nella mappa, viene aggiunto contando 1. altrimenti, il conteggio esistente viene incrementato.

  4. Eliminazione dei controlli ridondanti: il controllo already_printed del codice originale è stato necessario a causa del suo metodo di conteggio inefficiente. std::map gestisce intrinsecamente tutto questo: ogni carattere viene contato una sola volta e il ciclo finale ripercorre la 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 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