You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Hello and thank you for this great resource.
I implemented a simple brute-force solution for "sorted_arrays_merge" problem in C++ as below:
vector<int> MergeSortedArrays(const vector<vector<int>> &sorted_arrays)
{
auto result = std::vector<int>{};
for (const auto &sortedArray : sorted_arrays)
result.insert(result.end(), sortedArray.begin(), sortedArray.end());
std::sort(result.begin(), result.end());
return result;
}
I get the following metrics on my machine for this solution and use the default compiler flags:
Test PASSED (152/152) [ 9 ms]
Average running time: 153 us
Median running time: 44 us
If I run the provided solution, I get these metrics:
Test PASSED (152/152) [ 19 ms]
Average running time: 377 us
Median running time: 155 us
I tried to improve the runtime of the provided solution by using a class like this to avoid iterator indirections:
struct ArrayInfo
{
bool operator>(const ArrayInfo &other) const { return el > other.el; }
const vector<int> *array;
size_t arraySize{ 0 };
int arrayIdx{ 0 };
int el{ 0 };
};
However, that did not change the duration that much. I was wondering what the issue could be that the optimized algorithm runs slower than the brute-force one. Thank you very much for your time and help.
The text was updated successfully, but these errors were encountered:
Hello and thank you for this great resource.
I implemented a simple brute-force solution for "sorted_arrays_merge" problem in C++ as below:
I get the following metrics on my machine for this solution and use the default compiler flags:
If I run the provided solution, I get these metrics:
I tried to improve the runtime of the provided solution by using a class like this to avoid iterator indirections:
However, that did not change the duration that much. I was wondering what the issue could be that the optimized algorithm runs slower than the brute-force one. Thank you very much for your time and help.
The text was updated successfully, but these errors were encountered: