6
\$\begingroup\$

I am writing a routine to calculate median using the minimum of the numbers and then changing the value of the minimum to a large value outside the range of numbers (assuming you know the nature of the numbers). I know I could use many other proven techniques, but have chosen to play around with this one.

I don't see why the performance is poor. There are 3 loops, however only two are nested at any one time. There is no sorting involved, only finding the first occurrence of a minimum and making the new value outside the range. If it finds the same number a second time, it ignores the number until the next iteration. It iterates for half of the total series before the median is found. It works dandy except for the speed.

How do I improve the efficiency of this code?

float trashMin(float array[], unsigned int length, float median){
    //what we want to do in this routine is find the lowest in the array
    //we then make the lowest number, the same as the highest possible number and 
    //after iteratively going through the array 1/2 of the full length we will find the median

    unsigned int halflength = (length / 2) + 1;
    unsigned int i = 0;
    unsigned int j = 0;
    unsigned int k = 0;
    float highNumber = 999.0;//this is an arbitrary number, well outside of range of the number series
    float median = 0;

    for (i = 0; i < halflength; ++i)
    {
        float lowestInArray = array[0];
        bool firstTime = true;// is it the first time we see this number
        
        for (j = 0; j < length; ++j)
        {// find the lowest and highest number in the array
            float comparitor = array[j];
            lowestInArray = (lowestInArray < comparitor) ? lowestInArray : comparitor;
        }//end j

        // now that we know which is the smallest number, eliminate only 1st occurance of it            
        for (k = 0; k < length; ++k)
        {
            float comparitor = array[k];                
            if (comparitor == lowestInArray && firstTime == true)
            {
                array[k] = highNumber;
                firstTime = false;
            }
        }//end k
        median = lowestInArray;
    }//end i
    return median;
}
\$\endgroup\$
3
  • \$\begingroup\$ Comment "// find the lowest and highest number in the array" is confusing. Suspect you want "// find the lowest number in the array". \$\endgroup\$ Apr 26, 2015 at 15:57
  • \$\begingroup\$ You are absolutely correct with that chux. That comment was left over from another routine I was writing and I forgot to adjust the comment. In that routine, I was trying to trim both the min and max from the array and found that it performed even worse. \$\endgroup\$ Apr 26, 2015 at 21:05
  • \$\begingroup\$ Thought it might be so - classic case where code updates yet comments fall behind. \$\endgroup\$ Apr 26, 2015 at 21:47

2 Answers 2

5
\$\begingroup\$

The structure of your function is

for (i = 0; i < halflength; ++i)    // N/2 iterations
{
    ...

    for (j = 0; j < length; ++j)    // N iterations
    {
        ... 
    }

    for (k = 0; k < length; ++k)    // N iterations
    {
        ...
    }
}

this makes \$ N/2 (N+N) = N^2\$ iterations, where \$ N \$ is the length of the array.

There are small improvements possible: In the k-loop, if a matching element has been found, you can break-out early:

    // now that we know which is the smallest number, eliminate only 1st occurance of it            
    for (k = 0; k < length; ++k)
    {
        float comparitor = array[k];                
        if (comparitor == lowestInArray)
        {
            array[k] = highNumber;
            break;
        }
    }

But actually this loop is not needed at all: In the j-loop, remember the index where the lowest element has been found, and then set to a "large" number directly:

    float lowestInArray = array[0];
    unsigned int indexOfLowest = 0;

    for (unsigned int j = 1; j < length; ++j) {
        float comparitor = array[j];
        if (comparitor < lowestInArray) {
            lowestInArray = comparitor;
            indexOfLowest = j;
        }
    }
    array[indexOfLowest] = FLT_MAX;

Also FLT_MAX is a better choice than 999.0 for a "large number". This reduces the number of iterations by a factor of 2.

If it finds the same number a second time, it ignores the number until the next iteration.

Yes, but the j-loop still traverses over the entire array. Instead of replacing the found minimal element by FLT_MAX, you could replace it by the last array element, and then reduce the upper bound for the j-loop accordingly:

for (unsigned int i = 0; i < halflength; ++i)
{
    float lowestInArray = array[0];
    unsigned int indexOfLowest = 0;

    for (unsigned int j = 0; j < length - i; ++j) {
        float comparitor = array[j];
        if (comparitor < lowestInArray) {
            indexOfLowest = comparitor;
            indexOfLowest = j;
        }
    }
    array[indexOfLowest] = array[length - i - 1];
    median = lowestInArray;
}

This reduces the number of iterations again. But it is still \$ O(N^2) \$, and I doubt that much more is possible with this algorithm.

As you already noticed, sorting the array first and then taking the middle element is faster. This is no surprise since sorting can typically be done in \$ O(N \log N) \$ operations.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thank you. That is a very elegant and complete explanation. \$\endgroup\$ Apr 25, 2015 at 15:47
  • \$\begingroup\$ I just got around to making your suggested changes and the performance is been increased 4 fold. The original routine ran in 4641ms, with the break in the k loop, it decreased to 2687ms. When I added FLTMAX, it decreased to 2672ms. When I added the if statement it decreased to 2344ms. Finally, when I used the indexOfLowest, the routine finally ran at 1453ms more than 3 times faster! \$\endgroup\$ Apr 26, 2015 at 10:50
2
\$\begingroup\$

Use the smallest possible scope

unsigned int i = 0;
unsigned int j = 0;
unsigned int k = 0;

At the top are confusing, instead using C99 declare them inside the loop statement:

for (unsigned int j = 0; j < length; ++j)

Remove noise

}//end j

Ok, I know loop scoping rules and so does every other programmer that has been programming more than a month, please remove such comments.

\$\endgroup\$
1
  • \$\begingroup\$ I did originally have initialization of the variable loop, just as you have suggested, However, the root of the problem is speed. I'm not quite sure why it slow. Which is found in the "Remove noise" For some odd reason, it's faster to sort the array and select the middle value, rather than just purge 1/2 of the lowest values. \$\endgroup\$ Apr 25, 2015 at 11:18

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.