2
\$\begingroup\$

I am trying to come up with the most performant way of calculating the statistical Modes of a std::vector, obeying two conditions:

1) my function should not duplicate memory usage (which would required for most usually mentioned faster methods of calculating mode);

2) my function should be able to handle multi-modality. It means, it should be able to return more than one mode when apropriate (i.e. in case the elements in the passed vactor have more than one mode).

Here is my function so far. It works, but I have the feeling that it could be further improved and reviewed, so I brought it here:

#include <vector>
#include <math.h>

std::vector<int> Mode(std::vector<int> &myvector)
{
int vectorsize = myvector.size();
int max = 0;
std::vector<int> maxs;
int counter = 1;
std::sort(myvector.begin(), myvector.end());

for (int i = 0; i < vectorsize - 1; i++)
{
    int currentnum = myvector[i];

    if (currentnum == myvector[i + 1])
    {
        counter++;

        if (counter > max)
        {
            if (counter > vectorsize - i) break; //early exit when the mode found so far appears more than the number of elements still to be evaluated
            max = counter;
            if (maxs.size() > 0) maxs.clear();
            maxs.push_back(currentnum);
        }
        else if (counter == max)
        {
            bool alreadyin = false;
            for (int j = 0; j < maxs.size(); j++)
            {
                if (maxs[j] == currentnum)
                {
                    alreadyin = true;
                    break;
                }
            }
            if (alreadyin == false)
                maxs.push_back(currentnum);
        }

    }
    else counter = 1; //reset the counter
}

return (maxs.size() > 0) ? maxs : myvector; //if all elements appear only once, return the whole initial vector; otherwise return the the modes that were found
}

Corrections, improvements an even suggestions of algorithm changes are very welcome.

\$\endgroup\$
  • \$\begingroup\$ Can you specify what mode means for you. Are "mode" unique elements, what does it describe. Also please add #includes, so the code is compilable. There also seems to be a leftover from you original code in line 7 _vector.begin() \$\endgroup\$ – miscco Aug 29 '16 at 7:27
  • \$\begingroup\$ @miscco Thanks for pointing out the leftover. But I don't quite get what you mean by "specify what mode means" for me. I don't see how mode could have different meanings besides the standard statistical one. \$\endgroup\$ – user2019840 Aug 29 '16 at 8:02
  • 1
    \$\begingroup\$ there are quite some possibilities: en.wikipedia.org/wiki/Mode \$\endgroup\$ – miscco Aug 29 '16 at 8:07
  • \$\begingroup\$ @miscco Although I don't see how the description of my problem could in any point of view fit into any of the ideas listed in such link besides the concept of statistical mode, I added a specification in the question: "statistical mode". Thanks! \$\endgroup\$ – user2019840 Aug 29 '16 at 8:13
  • \$\begingroup\$ I have updated my answers accordingly. One thing that has less to do with review is that you pass the vector by reference and then sort. This will modify the data, which is generally not what one would expect. \$\endgroup\$ – miscco Aug 29 '16 at 9:31
2
\$\begingroup\$

So without really understanding what you mean with mode I would suggest the following purely based on your code:

  1. Add includes. The code as is doesn't compile, which makes it harder for reviewers.
  2. Premature Optimization. You are doing a lot of it. There is no reason to assign vectorsize to myvector.size(). The compiler will take care of that. Also currentnum is unnecessary.
  3. Be consistent with your style. Putting else clauses at the same line with the code makes the code incredibly hard to read. Also parentheses really help in tracing the control flow. Generally nested control flow should utilize parentheses.
  4. Naming. Consider camelCase or scores, but do not just add lowercaseletters as in alreadyin
  5. alreadyin == false should be !alreadyin

So know that I know what you mean we can optimize the code.

The first thing would be naming. The vector containing the modes should be named modes rather than maxs. Similarly I would rather name max as currentMode or better modeStrength.

The second point would be the update of the vector. Currently you always clear it. However, if it only has one mode you can just change that value.

if (modes.size() == 1) 
    modes[0] = myVector[i];
else if (modes.size() > 1)  {
    modes.clear();
    modes.push_back(myVector[i]);
} else {
    modes.push_back(myVector[i]);
}

The third idea would be to increment your loop based on the found matches so you do not reiterate already processed data

unsigned counter;
unsigned modeStrength = 0;
for (unsigned i=0; i < myVector.size() - 1; i += counter) {
    counter = 1;
    while ((counter + i != myVector.size()) && 
           (myVector[i] == myVector[i+counter])) {
        counter++;
    }
    if (counter == modeStrength) {
        modes.push_back(myVector[i]);
    } else if (counter > modeStrength) {
        modeStrength = counter;
        if (modes.size() == 1) {
            modes[0] = myVector[i];
        } else {
            modes.clear();
            modes.push_back(myVector[i]);
        }
    }
}

That would also turn the check for existence unnecessary.

\$\endgroup\$
  • \$\begingroup\$ Many thanks! I specially like your first and second ideas. Indeed it's easy to avoid clearing the whole vector all the time and just clear when its size is greater than 1 (however, notice that your snippet is wrong: there is no push back for the final "else": when counter > max, the maxs vector has to be either cleared or substituted in the case of size 1). \$\endgroup\$ – user2019840 Aug 30 '16 at 5:12
  • \$\begingroup\$ As for the 3rd idea, I don't get it. You made a confusion in what regards what the counter was really counting. It's utility in the code is not to index myvector, but rather to count the number of repetitions of a given int, so we can compare to max and whether a greater mode was found \$\endgroup\$ – user2019840 Aug 30 '16 at 5:15
  • \$\begingroup\$ The point is, that you are searching a sorted vector for repetitive elements. Once you have found "counter" elements at positions [i, .... i+"counter"-1], there is no need to start searching again at position i+1, as you already searched it. Therefore, start at the first unchecked position i+"counter". \$\endgroup\$ – miscco Aug 30 '16 at 6:32
  • \$\begingroup\$ Oh, I see what you mean. For instance, if at a given iteration the mode is a number that appeared n times, then for each case i in the original vector, if(i!=i-1) there is no need to test if(i==i+1), since then we become only interested in the cases that are at least if(i==i+(n-1)). Is that what you are suggesting? \$\endgroup\$ – user2019840 Aug 31 '16 at 3:06
  • \$\begingroup\$ Not really. Lets take an example. Your sortet vector looks like this: [0 1 1 1 2 3] So For i==0 we check i=0+1 => false and increment by counter =1 to i=1. For i=1 we check i=1+1 => true =>counter=2, i=1+2->true =>counter=3, and i=1+3=>false. Now if we would simply increment i by one, we would again check if the value at i=2 equals that at i=3, which we already did. The next usefull comparison would be i=4 with i=5, which incedentally is the same as i+counter=1+3 from the last iteration. Does that make sense to you? \$\endgroup\$ – miscco Aug 31 '16 at 4:47
1
\$\begingroup\$
#include <vector>
#include <math.h>
//...
    std::sort(myvector.begin(), myvector.end());

Include what is necessary to compile the program. <math.h> isn't used by your function. <algorithm> is required for std::sort.


int max = 0;
std::vector<int> maxs;

Echoing @miscco here, the name doesn't represent what the variable contains.

int modal_frequency{};
std::vector<int> modes;

Your initial max is a violation of your second requirement.

edit - Misread the dataflow. However, the function still returns the wrong result. A sequence has no mode when all the numbers that appear in the data have the same frequency. -- end edit

my function should be able to handle multi-modality. It means, it should be able to return more than one mode when apropriate

Consider a sequence of distinct integers.

$$S = [1, 2, 3]$$

For mode(S), the mode is the empty-set (no mode).


if (maxs.size() > 0) maxs.clear();
    maxs.push_back(currentnum);

The use of an external buffer to store modal candidates is a violation of your first requirement. Consider a sequence such that the mode can be found at the end of the sequence and every other element in the sequence is distinct not a mode.

$$S = [1, 1, 2, 2, 3, 3, ..., n - 1, n - 1, n , n, n] $$

What happens with the capacity of the buffer as we approach \$n\$?

edit - This could potentially be a lot of appending and reallocating. If you actually pass that sequence into your function, you also discover a nice bug from exiting early. - edit


Know your <algorithm>s. Whenever you use a boolean/index as you scan a range,

bool alreadyin = false;
for (int j = 0; j < maxs.size(); j++)
{
    if (maxs[j] == currentnum)
    {
        alreadyin = true;
        break;
    }
}
if (alreadyin == false)
    maxs.push_back(currentnum);

You are typically doing one of the std::find variations.

if (std::find(maxs.cbegin(), maxs.cend(), currentnum) == maxs.cend()) {
   maxs.push_back(currentnum);
}

The same can be said if there is code scanning and comparing adjacent elements (see std::adjacent_find).

for (int i = 0; i < vectorsize - 1; i++) {
    int currentnum = myvector[i];    
    if (currentnum == myvector[i + 1]) {
        counter++;

Keep functions short and simple. Functions that are focused on a single logical operation are easier to understand, test, and reuse.

Instead of having a function "do-it-all", let's take a different approach where we break-up the code into abstractions that perform single logical operations. Some pseudocode:

function mode(sequence)
    sort sequence
    if sequence has no mode
        return an empty range
    calculate the modal frequency
    gather maximas with modal frequency
    return maxima range
end function

Calculate might use a function that flattens a range of equal elements into an element count via std::adjacent_find. For gather (a custom partition), we could use that count function with either std::rotate or std::swap) distinct modes with the modal frequency (in-place). Which you decide to use depends on your need for stability within the two partitioned sequences. Perhaps create both and name prefix one stable_.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your suggestions, I found most pretty useful indeed. However, I don't quite agree with the claims that I violated my two requirements. In the first case, I saved temporary modes in a vector because well, it's all about retrieving a vector of modes. In my condition 1 I was talking about algorithms for finding mode that duplicate the whole data. But sure, that's debatable. \$\endgroup\$ – user2019840 Aug 30 '16 at 5:10
  • \$\begingroup\$ Now in what regards my condition 2 and the use of max, there you got it wrong. If you notice, I don't use such variable to retrieve values, but rather as just a auxiliary to calculate "current" modes being evaluated and more importantly, to allow early exits. The results are all about the vector maxs, which of course do not violate my second condition \$\endgroup\$ – user2019840 Aug 30 '16 at 5:10
  • \$\begingroup\$ Corrected the review based on your feedback with edited annotations. Duplicating the whole data or half the data is still duplicating data (not all, but potentially about half). As I mentioned, an in-place solution is possible using a partitioning approach (gather). The second condition states that Mode() should return multimodal sets when apropriate. A sequence whose elements all share the same frequency has no mode. It is neither appropriate nor correct to return a multimodal sequence. \$\endgroup\$ – Snowhawk Aug 30 '16 at 8:31
  • 1
    \$\begingroup\$ Great reviews. You are correct, I was returning the passed vector as the result when the result should be 'no mode'. The main reason for that is that post-function execution it's easy to test if result is of the same size of original vector (i.e. there is no mode), while it's not that easy to convey "no mode" otherwise. But yes, that in itself would duplicate the data. Talking about your in-place suggestions, I quite like them. I will try and see how much each hurts performance (both certainly will, the question becomes how much for the classical trade-off between memory and speed). Thanks! \$\endgroup\$ – user2019840 Aug 31 '16 at 2:57
  • \$\begingroup\$ It is equally easy to check against modesize==0 than to check against modesize==myvectorsize \$\endgroup\$ – miscco Aug 31 '16 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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