Re: Finding most frequent element in std::vector?
On Mar 24, 11:47 pm, Steve555 <foursh...@btinternet.com> wrote:
On 24 Mar, 14:56, Michael Doubez <michael.dou...@free.fr> wrote:
On 24 mar, 15:12, Steve555 <foursh...@btinternet.com> wrote:
On 24 Mar, 12:19, Bart van Ingen Schenau <b...@ingen.ddns.info> wrote=
:
On Mar 24, 9:11 am, Steve555 <foursh...@btinternet.com> wrote:
Given a vector, I'm trying to find the most frequently occurring
element, and return it, along with a count of its frequency.
Although I've got a way of doing it below, this gets called milli=
ons
of times in an inner loop and I need to speed it up if possible.
I'm looping through each element of the vector, and using std::co=
unt
[snip]
Thanks for the many suggestions, using various ideas from each
(especially using freqArray) I've been able to reduce the time for 1
million runs from 1.91 seconds down to 0.69, so a huge improvement.
(I used the code directly in the end, rather than in a separate
function, but both times reflect this)
// assuming vec already exists
long *ptr, *freqArray = new long[201];
long maxElement, maxFreq;
for(long l=0;l<1000000;l++)
{
//clear the freqArray (using a ptr was quicker than []
ptr = freqArray;
for(long j=0; j<=200; j++) *ptr++ = 0;
maxFreq = 0;
for(long i=0; i<vec.size(); i++)
{
++freqArray[vec[i]];
if(freqArray[vec[i]] > maxFreq)
{
maxElement = vec[i];
maxFreq = freqArray[vec[i]];
}
}
}
P. Lepin: In this case, map worked out slower, probably the lookup
time.
I guess it is the locality and the dynamic allocation.
Michael: Sorry don't know what you mean by "quadratic" in this
context.
Quadratic means that the complexity is proportional to the square of
the number of elements.
It is as worse as it can get except for exponential or NP-complete
complexity.
And at 49 1/4, I'm a bit old for homework ;-)
Never too late.
[snip]
Out of shear curiosity could you try the following algorithm:
long FindMostFrequentInVector(vector<long> *inVec, long *maxElement)
{
vector<long>::iterator it = inVec->begin();
vector<long>::iterator end = inVec->end();
// sort inVec - best would be for it to be already sorted
std::sort(it,end);
long maxCount = 0;
// assert( !inVec->empty() );
long count = 1;
long element = *it;
while( ++it != end )
{
if( *it == element )
{ // count current element
++count;
}
else
{ // new element value
if( count > maxCount )
{
maxCount = count;
*maxElement = element;
}
element = *it;
count = 1;
}
}
return maxCount;
}
--
Michael
Thanks Michael. Running your algorithm (explicitly rather than in a
separate function) gave a time of .51 (compared to original .69 for 1
million loops). I've found (on my system at least) that iterators
carry some overhead compared to simple array indexing. Hence, using an
array buffer to keep track of the counts instead, along with memset()
to quickly clear it, brought the time down to .22.
What's also quite interesting about all the different methods
suggested is the amount of variation from run to run. The ones where I
use iterators or stl algorithms are very consistent (if a little
slower), whereas the best solution (using a freqArray and memset() )
can vary by as much as 60 ms (~25%). That said, it's a bit of an
artificial situation, loading a program, setting timers, looping a
million times and exiting... maybe there's some system crap causing
the variability. Anyway, not a problem, just a curiosity.
(I'm compiling in Xcode on OSX 10.6.2 on a 2.8ghz Intel Mac, timimg
done in microseconds, rounded)
First, you are in one of the rare situations where std::vector is
legitimately significantly slower than built-in arrays.
vector<int> x(10);
will initialize all of its 10 elements to 0. A built-in array
int x[10];
will not. This is usually not a concern, but in your case it might be.
Zero initializing all the bins of the bin sort might be quite costly.
Second, if you're using microsoft visual studios compiler, consider
turning off checked iterators. In release mode, VS includes some extra
run time checking in its STL iterators.
http://msdn.microsoft.com/en-us/library/aa985965%28VS.80%29.aspx
Otherwise, with a halfway decent optimizing compiler with its
optimizations turned on, there should be no noticeable difference
between built-in arrays and std::vectors.
I would suggest a basic bin sort, or some variation:
- Create a built-in array of bins for the bin sort. (Do not initialize
it. We're trying to save this cost.)
- For each element in the input vector, zero the corresponding bin.
- Loop over the input vector, keeping track of the "best thus far"
value and "number of times seen" for the "best thus far" value. For
each element, increment the corresponding bin, and then update if
necessary the "best thus far" counters.
This has 2 loops of 10 iterations each which is almost certainly
faster than the algorithm with a loop of 200 iterations. However,
std::memset may be significantly faster than a loop of 200 iterations,
so it might be faster to memset all 200 bins to 0 instead of looping
an additional time up front to zero out the 1-10 "will be used" bins.
We traverse the input vector in increasing address order, which caches
tend to like. However, we are hitting the bins in a random order,
which isn't too cache friendly, though I would guess that it's still
faster than our alternatives. Possible alternatives: You might be able
to use a hash table for the bins, though I suspect the extra overhead
of "hashing" would outweigh any benefits, and there's always those
pesky problems of getting a good hash function and the potential
really slow worst case. You might try having a map of pairs of (value,
frequency), or more specifically a sorted array of pair<int, int>. I
suspect that the caching effects with the small input size would
easily favor the sorted built-in array over "Big O"-superior std::map.
A linear search on the sorted array might even outperform a binary
search on the sorted array due to its small size. Hell, it might even
be faster to not sort at all and just do a linear lookup in the bins
for each of the 10 elements of the input vector.
Note specifically that many of the alternatives presented fly in the
face of conventional Big O analysis. However, you specifically said
that your algorithm has these fixed \small\ values, and Big O only
applies when the size is "large enough". Note however that this is not
an excuse to code yourself into a corner if at all possible, so if and
when the range of values becomes "any float", or the input size
becomes "several million", you are not screwed.
As always, the basic "guideline" of optimization is to first write
code "sanely", then measure to find the slow spots, then optimize /
hack the slow spots, measuring all alternatives. I've listed a lot of
alternatives, and I really don't know which would perform the best.
I'd guess that it depends a lot on the hardware and distribution of
input values.