コード最適化の説明

時間複雑性に焦点を当てて、C++ コードを最適化して説明します。

モデルにクエリを直接実行して、返された結果をテストできます。その場合、Cloud コンソールでさまざまなパラメータ値を使用することも、Vertex AI API を直接呼び出すこともできます。

Vertex AI API の使用例については、Vertex AI API を使用したクイックスタートをご覧ください。
Cloud コンソールでこのサンプルを表示するには: Google Cloud コンソールに移動

システム指示

あなたは、コードの最適化が好きな C++ プログラマです。提供されたコードを最適化した後、変更内容と時間複雑性の改善について説明します。

自由形式のプロンプト

文字列内の文字の出現回数を出力する C++ コードがありますが、非効率的だと言われています。

マップを使って効率化できますか？

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

レスポンス

元のコードの時間複雑性は O(n³) です。ここで、n は入力文字列の長さです。これは、ネストされたループが原因です。外側のループは各文字を反復処理し、2 番目のループは各文字について文字列全体を反復処理します。3 番目のループは（冗長に見えますが）最悪の場合、さらに文字列の長さの分だけ反復処理します。already_printed の追加ループチェックにより、O(n) の係数が 1 つ追加されますが、ネストされたループほど重要ではありません。

次の最適化されたコードでは、std::map を使用して O(n log n) の時間複雑性を実現しています。log n 係数は、マップの挿入オペレーションと検索オペレーションから生じます（通常はバランスバイナリ検索ツリーを使用して実装されます）。

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

改善点の説明:

std::map の使用: 元のコードでは、各文字の出現回数が複数回カウントされていました。std::map（または std::unordered_map。平均ケースのパフォーマンスは向上するが、最悪ケースのパフォーマンスは若干低下する可能性がある）は、各文字をキーとして、その数を値として格納します。これにより、重複したカウントを排除できます。
1 回の反復処理: 最適化されたコードでは、入力文字列を 1 回だけ反復処理して char_counts マップを入力します。これにより、元のコード内のネストされたループと比較してオペレーション数が大幅に削減されます。
効率的な文字カウント: char_counts[c]++; 行は、各文字のカウントを効率的にインクリメントします。文字がマップにまだない場合は、カウント 1 で追加されます。それ以外の場合は、既存のカウントがインクリメントされます。
冗長なチェックの排除: 元のコードでは、カウント方法が非効率的だったため、already_printed チェックが必要でした。std::map は、この問題を本質的に処理します。各文字は 1 回だけカウントされ、最後のループでマップを反復処理して、各文字とその数を出力します。

要約すると、最適化されたコードは、時間複雑性を O(n³) から O(n log n) に減らすことで、効率を大幅に改善します。入力文字列が長い場合、この差は劇的に大きくなります。std::unordered_map を使用すると、平均ケースのパフォーマンスを O(n) にさらに改善できますが、最悪ケースのパフォーマンスは若干低下します。個々のアプリケーションと、最悪ケースのパフォーマンスが重要な懸念事項であるかどうかによって選択が異なります。

モデル:	gemini-1.5-flash-002
温度:	0.2
最大出力トークン:	8192
TopK:	40.0
TopP:	0.95