1
\$\begingroup\$

I am working with this assignment of optimizing a radix sort code in C++ and I need to reduce the execution time. My code is working and it looks like this:

void RadixSort::RadixSortNaive(std::vector<long> &Arr) {

long Max_Value = findMax(Arr);

    int Max_Radix = 1;
while (1) {
  if (Max_Radix >= Max_Value) break;
  Max_Radix = Max_Radix*radix_;
}

for (int i = 1; i < Max_Radix; i = i*radix_) {
  for (int j = 0; j < key_length_; j++) {
    int K;
    if (Arr[j] < i) K = 0;
    else K = (Arr[j] / i) % radix_;
    Q[K].push(Arr[j]);
  }

  int idx = 0;
  for (int j = 0; j < radix_; j++) {
    while (Q[j].empty() == 0) {
      Arr[idx] = Q[j].front();
      Q[j].pop();
      idx++;
    }
  }
}
class RadixSort{
public :

  void setConfig(int key_length, int radix) {
    key_length_ = key_length;
    radix_ = radix;
    for (int i = 0; i < radix_; i++) {
      Q.push_back(std::queue<long>());
    }
  }

  long findMax(std::vector<long> Arr) const {
    long Max = 0;
    for (int i = 0; i < key_length_; i++) {
      if (Max < Arr[i])
        Max = Arr[i];
    }
    return Max;
  }

  void RadixSortNaive(std::vector<long> &Arr);
  void RadixSortStudent(std::vector<long> &Arr);

private:
  int key_length_;
  int radix_;
  std::vector<std::queue<long>> Q;
};

}

However, I am sure that there is still room for improvement. I have been trying to implement parallelization with OMP library but nothings seemed to work. Is there any way where I can improve the previous code? Maybe improving the loops or any other code optimization technique.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Please fix the indentation \$\endgroup\$
    – klutt
    Dec 14, 2021 at 19:59
  • 1
    \$\begingroup\$ RadixSortStudent is also missing. Some usage examples might be useful. \$\endgroup\$
    – jdt
    Dec 15, 2021 at 22:32

2 Answers 2

1
\$\begingroup\$

Firstly, please put the headers:

#include <vector>
#include <algorithm>
#include <queue>

I wonder if you could may be do this set up in a constructor or something. Because otherwise you are just telling the user to do a two-phase initialization. If the user of this class misses this, the function won't work.

void setConfig(int key_length,int radix) {
            key_length =key_length;
            radix_ = radix;
            for (int i = 0; i < radix_; i++) {
                Q.push_back(std::queue<long>());
            }
        }

Thirdly, find max does not consider negative numbers for some reason. It is also public. Ideally, one can replace it with a call to a library function:

long findMax(std::vector<long> Arr) const {
        return *max_element(Arr.begin(), Arr.end());
       
    }

Fourthly, you are basically calculating the maxRadix from maxValue and using for the iteration:

while (1) {
            countNumber++;
            if (Max_Radix >= Max_Value) break;
            Max_Radix = Max_Radix * radix_;
        }

When in reality you can use MaxValue as the limit to your final iteration. I hope you get the idea, I have not tested this, but I guess this should work fine.

for (int i = 1; i < Max_Value; i = i * radix_)
 

       
       
\$\endgroup\$
0
\$\begingroup\$

Most books/algorithm focus on optimizing without taking into account caching (data locality) and branch prediction. Those aspects are very important to performance on a (large) CPU. So the next things you need to do is understand how your input data is organized (which helps you optimize branch prediction and dat locality)and to start measuring your code performance using a profiler.

Just to give you an idea on how weird sorting data can be watch this : CppCon 2019: Andrei Alexandrescu “Speed Is Found In The Minds of People" https://www.youtube.com/watch?v=FJJTYQYB1JQ.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.