Prev: Questions compiled over the last 5 years
Next: template problem
From: Gerhard Wolf on 10 Jun 2008 17:03
Hi,

i need a function hat returns the most common value of a vector.
{1,1,1,1,2,2,2,3,4,4,4,4,4,4,4,5,5} => 4
{1,2,2,3,4,5,5,6,7} => 2 the first maximum
I need it for different datatypes int,double... so a template class would be
the best but i don't know how to start? Are there any free statistical
templates available in the internet?
From: Daniel T. on 10 Jun 2008 21:22
Gerhard Wolf <quisquiliae(a)gmx.de> wrote:

> i need a function hat returns the most common value of a vector.
> {1,1,1,1,2,2,2,3,4,4,4,4,4,4,4,5,5} => 4
> {1,2,2,3,4,5,5,6,7} => 2 the first maximum
> I need it for different datatypes int,double... so a template class would be
> the best but i don't know how to start? Are there any free statistical
> templates available in the internet?

The first solution I came up with will work with arrays, vectors, deques
or lists, holding any type that is copyable and less-than comparable:

template < typename T >
struct populate_map
{
map< T, int >& m;
populate_map(map< T, int >& m):m(m) { }
void operator()(const T& t) {
m[t] += 1;
}
};

template < typename T >
struct find_greatest_count
{
T t;
int count;
void operator()(const typename map< T, int >::value_type& v) {
if (v.second > count) {
count = v.second;
t = v.first;
}
}
};

template < typename It >
typename iterator_traits<It>::value_type
find_most_prevalent(It begin, It end)
{
typedef typename iterator_traits<It>::value_type T;
map<typename iterator_traits<It>::value_type, int> m;
for_each(begin, end, populate_map<T>(m));
return for_each(m.begin(), m.end(), find_greatest_count<T>()).t;
}

// test code
int main()
{
int arr[] = {1,1,1,1,2,2,2,3,4,4,4,4,4,4,4,5,5};
assert(find_most_prevalent(arr, arr + 17) == 4);
int arr2[] = {1,2,2,3,4,5,5,6,7};
assert(find_most_prevalent(arr2, arr2 + 9) == 2);
cout << "OK\n";
}


Second solution. This one is likely faster but it modifies the container
being examined. It works with the same container types but the type
contained must be equality comparable instead of less-than comparable...

template < typename It >
typename iterator_traits<It>::value_type
find_most_prevalent(It begin, It end)
{
typedef typename iterator_traits<It>::value_type T;
T result;
int count = 0;
while (begin != end) {
T value = *begin;
It newEnd = remove(begin, end, value);
int newCount = distance(newEnd, end);
if (newCount > count) {
result = value;
count = newCount;
}
end = newEnd;
}
return result;
}

Any others?
From: Eric Pruneau on 10 Jun 2008 22:33

"Daniel T." <daniel_t(a)earthlink.net> a �crit dans le message de news:
daniel_t-3D76D1.21224510062008(a)earthlink.vsrv-sjc.supernews.net...
> Gerhard Wolf <quisquiliae(a)gmx.de> wrote:
>
>> i need a function hat returns the most common value of a vector.
>> {1,1,1,1,2,2,2,3,4,4,4,4,4,4,4,5,5} => 4
>> {1,2,2,3,4,5,5,6,7} => 2 the first maximum
>> I need it for different datatypes int,double... so a template class would
>> be
>> the best but i don't know how to start? Are there any free statistical
>> templates available in the internet?
>
> The first solution I came up with will work with arrays, vectors, deques
> or lists, holding any type that is copyable and less-than comparable:
>
> template < typename T >
> struct populate_map
> {
> map< T, int >& m;
> populate_map(map< T, int >& m):m(m) { }
> void operator()(const T& t) {
> m[t] += 1;
> }
> };
>
> template < typename T >
> struct find_greatest_count
> {
> T t;
> int count;
> void operator()(const typename map< T, int >::value_type& v) {
> if (v.second > count) {
> count = v.second;
> t = v.first;
> }
> }
> };
>
> template < typename It >
> typename iterator_traits<It>::value_type
> find_most_prevalent(It begin, It end)
> {
> typedef typename iterator_traits<It>::value_type T;
> map<typename iterator_traits<It>::value_type, int> m;
> for_each(begin, end, populate_map<T>(m));
> return for_each(m.begin(), m.end(), find_greatest_count<T>()).t;
> }
>
> // test code
> int main()
> {
> int arr[] = {1,1,1,1,2,2,2,3,4,4,4,4,4,4,4,5,5};
> assert(find_most_prevalent(arr, arr + 17) == 4);
> int arr2[] = {1,2,2,3,4,5,5,6,7};
> assert(find_most_prevalent(arr2, arr2 + 9) == 2);
> cout << "OK\n";
> }
>
>
> Second solution. This one is likely faster but it modifies the container
> being examined. It works with the same container types but the type
> contained must be equality comparable instead of less-than comparable...
>
> template < typename It >
> typename iterator_traits<It>::value_type
> find_most_prevalent(It begin, It end)
> {
> typedef typename iterator_traits<It>::value_type T;
> T result;
> int count = 0;
> while (begin != end) {
> T value = *begin;
> It newEnd = remove(begin, end, value);
> int newCount = distance(newEnd, end);
> if (newCount > count) {
> result = value;
> count = newCount;
> }
> end = newEnd;
> }
> return result;
> }
>
> Any others?

What about

int main(void)
{
int A[10] = {1,1,1,2,3,4,4,6,7,7};
int* beg = A;
int* end = A+10;

size_t NbMax = 0;
int ElemMost = *beg;
while(beg != end)
{
int CurElem = *beg;
size_t Nb = 0;
while(*beg == CurElem && beg != end)
{
++beg;
++Nb;
}
if(Nb > NbMax)
{
NbMax = Nb;
ElemMost = CurElem;
}
}
return 0;
}

It doesn't invalidate the element of your array and the complexity is O(n)
(best and worst case).The array must be sorted, but if it is not the case
you can always apply a quick sort and the the complexity jump to O(n log(n))
+ O(n).

The complexity with the remove solution is O( n(n+1)/2) which is quadratic
for the worst case, but the best case is linear. the remove solution also
mess with your elements.

Transforming the alogorithm into a template is left as an exercise!!!

-------------

Eric Pruneau


 | 
Pages: 1
Prev: Questions compiled over the last 5 years
Next: template problem