CODEWITHSUNDEEP
c++qtsorting
user3830784
user3830784

Reputation: 355

Looking for a better way to sort data

I have an algorithm which processes a file across 6 different variable parameters. The algorithm produces a true/false result for the file on each parameter set. I run this algorithm across a set of files, getting the resulting true/false's in a vector (as well as some additional, irrelevant data).

Once that algorithm runs, I then want to count the number of true results for each parameter set, as well as the number of files processed. The way that I do that right now is as follows:

while(!results.isEmpty()){ //results being a vector of the individual file results
  for (long i = 0; i < params.size(); i++){ //params being a vector of the parameters
    if (results.first().params... == params[i].params...){
       params[i].numFiles++;
       if (results.first().result){
         params[i].numTrue++;
       }
       results.pop_front();
       break;
    }
  }
}

This accomplishes the job, but now that I've optimized my algorithm, this is the last chokepoint in my code, and I am looking for ways to speed this up. What would be the best way to quckly sort through this data? If this is relevant, at the moment I am using Qt, and my vectors are currently QVector.

Upvotes: 0

Views: 83

Answers (2)

Sparrow
Sparrow

Reputation: 88

If there are ready params for comparison

if (results.first().params... == params[i].params...)

in each result, you can store 6 params in a hash table and search through a hash table each iteration of

while(!results.isEmpty())

which gives O(N) complexity

but actually real performance depends on hash function. Sometimes O( N log M ) may be better; it depends on operations time. So it's better to check performance in practice after optimization.

Additional note: current complexity is O(N) anyway because number of params (6 params) is a constant.

Upvotes: 0

Brahim
Brahim

Reputation: 838

Your algorithm has a complexity of O(NxM), where N is the size of result and M is the size of param.

If what you are comparing here:

if (results.first().params... == params[i].params...){

supports the less operator you can sort params before the first loop. And instead of going through all its elements, just do a binary search. The complexity will be then O(Nxlog(M)).

Upvotes: 1

Related Questions