コードの最適化の説明

文字列内の文字の出現回数を出力する 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;
}

改善点の説明:

1. std::map の使用: 元のコードでは、各文字の出現回数が複数回カウントされていました。std::map（または std::unordered_map。平均ケースのパフォーマンスは向上するが、最悪ケースのパフォーマンスはわずかに低下する）は、各文字をキーとして、その数を値として格納します。これにより、重複したカウントを排除できます。

2. 1 回反復処理: 最適化されたコードでは、入力文字列を 1 回だけ反復処理して char_counts マップを入力します。これにより、元のコード内のネストされたループと比較してオペレーション数が大幅に削減されます。

3. 効率的な文字カウント: char_counts[c]++; 行は、各文字のカウントを効率的にインクリメントします。文字がマップにまだない場合は、カウント 1 で追加されます。それ以外の場合は、既存のカウントがインクリメントされます。

4. 冗長なチェックの排除: 元のコードでは、カウント方法が非効率的だったため、already_printed チェックが必要でした。std::map は、この問題を本質的に処理します。各文字は 1 回だけカウントされ、最後のループでマップを反復処理して、各文字とその数を印刷します。

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