Stay organized with collections
Save and categorize content based on your preferences.
Optimize and explain C++ code, focusing on time complexity.
You can query a model directly and test the results returned when using
different parameter values with the Cloud console, or by calling the
Vertex AI API directly.
I have a C++ code that prints the number of times a character occurs in a string, but I was told it's inefficient.
Can you make it more efficient using a map?
#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;
}
Response
The original code has a time complexity of O(n³), where n is the length of the input string. This is because of the nested loops: the outer loop iterates through each character, the second loop iterates through the entire string for each character, and the third loop (though seemingly redundant) still iterates through the string's length in the worst case. The additional loop checking for already_printed adds another O(n) factor, although it's less significant than the nested loops.
The following optimized code uses an std::map to achieve a time complexity of O(n log n). The log n factor comes from the map's insertion and lookup operations (which are typically implemented using balanced binary search trees).
#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;
}
Explanation of Improvements:
Using std::map: The original code inefficiently recounted the occurrences of each character multiple times. The std::map (or std::unordered_map for potentially faster average-case performance, but slightly higher worst-case) stores each character as a key and its count as a value. This eliminates redundant counting.
Iterating Once: The optimized code iterates through the input string only once to populate the char_counts map. This significantly reduces the number of operations compared to the original code's nested loops.
Efficient Character Counting: The line char_counts[c]++; efficiently increments the count for each character. If the character is not already in the map, it's added with a count of 1; otherwise, its existing count is incremented.
Eliminating Redundant Checks: The original code's already_printed check was necessary because of its inefficient counting method. The std::map inherently handles this; each character is counted only once, and the final loop iterates through the map, printing each character and its count.
In summary, the optimized code provides a substantial improvement in efficiency by reducing the time complexity from O(n³) to O(n log n). For large input strings, this difference will be dramatic. Using std::unordered_map could further improve the average-case performance to O(n), but at the cost of slightly higher worst-case performance. The choice depends on the specific application and whether worst-case performance is a critical concern.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Hard to understand","hardToUnderstand","thumb-down"],["Incorrect information or sample code","incorrectInformationOrSampleCode","thumb-down"],["Missing the information/samples I need","missingTheInformationSamplesINeed","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-10-31 UTC."],[],[]]