Penjelasan pengoptimalan kode

Mengoptimalkan dan menjelaskan kode C++, dengan berfokus pada kompleksitas waktu.

Anda dapat membuat kueri model secara langsung dan menguji hasil yang ditampilkan saat menggunakan parameter value yang berbeda dengan Konsol Cloud, atau dengan memanggil Vertex AI API secara langsung.

Petunjuk sistem

Anda adalah programmer C++ yang suka mengoptimalkan kode. Setelah mengoptimalkan kode yang diberikan, Anda menjelaskan perubahan dan peningkatan dalam kompleksitas waktu.

Perintah Freeform

Saya memiliki kode C++ yang mencetak frekuensi kemunculan karakter dalam string, tetapi saya diberi tahu bahwa kode tersebut tidak efisien.

Dapatkah Anda membuatnya lebih efisien menggunakan peta?

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

Respons

Kode asli memiliki kompleksitas waktu O(n³), dengan n adalah panjang string input. Hal ini karena loop bertingkat: loop luar melakukan iterasi pada setiap karakter, loop kedua melakukan iterasi pada seluruh string untuk setiap karakter, dan loop ketiga (meskipun tampaknya berlebihan) masih melakukan iterasi pada panjang string dalam kasus terburuk. Pemeriksaan loop tambahan untuk already_printed menambahkan faktor O(n) lainnya, meskipun kurang signifikan dibandingkan loop bertingkat.

Kode yang dioptimalkan berikut menggunakan std::map untuk mencapai kompleksitas waktu O(n log n). Faktor log n berasal dari operasi penyisipan dan pencarian peta (yang biasanya diterapkan menggunakan hierarki penelusuran biner seimbang).

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

Penjelasan Peningkatan:

  1. Menggunakan std::map: Kode asli tidak efisien dalam menghitung kemunculan setiap karakter beberapa kali. std::map (atau std::unordered_map untuk performa kasus rata-rata yang berpotensi lebih cepat, tetapi kasus terburuknya sedikit lebih tinggi) menyimpan setiap karakter sebagai kunci dan jumlahnya sebagai nilai. Hal ini menghilangkan penghitungan yang berlebihan.

  2. Iterasi Satu Kali: Kode yang dioptimalkan melakukan iterasi melalui string input hanya sekali untuk mengisi peta char_counts. Hal ini secara signifikan mengurangi jumlah operasi dibandingkan dengan loop bertingkat kode asli.

  3. Penghitungan Karakter yang Efisien: Baris char_counts[c]++; menambahkan jumlah untuk setiap karakter secara efisien. Jika karakter belum ada di peta, karakter tersebut akan ditambahkan dengan jumlah 1; jika tidak, jumlah yang ada akan bertambah.

  4. Menghapus Pemeriksaan yang Tidak Diperlukan: Pemeriksaan already_printed kode asli diperlukan karena metode penghitungannya yang tidak efisien. std::map secara inheren menangani hal ini; setiap karakter dihitung hanya sekali, dan loop terakhir melakukan iterasi melalui peta, mencetak setiap karakter dan jumlahnya.

Singkatnya, kode yang dioptimalkan memberikan peningkatan efisiensi yang signifikan dengan mengurangi kompleksitas waktu dari O(n³) menjadi O(n log n). Untuk string input yang besar, perbedaan ini akan sangat signifikan. Penggunaan std::unordered_map dapat lebih meningkatkan performa kasus rata-rata menjadi O(n), tetapi dengan mengorbankan performa kasus terburuk yang sedikit lebih tinggi. Pilihannya bergantung pada aplikasi tertentu dan apakah performa terburuk merupakan masalah yang penting.
Model: gemini-1.5-flash-002
Suhu: 0,2
Token output maks: 8192
TopK: 40,0
TopP: 0,95