Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Unexpected performance metrics for "sorted_arrays_merge" in C++ #237

Open
ArshaShiri opened this issue Sep 1, 2022 · 0 comments
Open

Unexpected performance metrics for "sorted_arrays_merge" in C++ #237

ArshaShiri opened this issue Sep 1, 2022 · 0 comments

Comments

@ArshaShiri
Copy link

ArshaShiri commented Sep 1, 2022

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant