Re: Finding most frequent element in std::vector?
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 million=
s
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::coun=
t
[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)
Steve