Explain please ...

[Hrach_Techie]

http://forum.armkb.com/showpost.php?...ostcount=50338

how's storing the result works here? it's not homework or any kind of assignment or so - just curious how it works ...

[CyberJoe]

Первая функция проверяет сколько ваз value повторяеться в массиве Array.
Вторая возвращает значение переменно из массива которая повторяеться чаще всех.

Вродеб.

[AvDav]

медленнее, но короче

#include <map>
#include <algorithm>

int get_max_freq_el(int *firstCell, int sz)
{
    using namespace std;
    map<int, int, greater<int> > counts;
    int n=sz<<1;
    for(int i=0; i<n; counts[count(firstCell, firstCell+n, firstCell[i])]=firstCell[i], ++i);
    return counts.begin()->second;
}

[nm]

Originally Posted by AvDav

медленнее, но короче

#include <map>
#include <algorithm>

int get_max_freq_el(int *firstCell, int sz)
{
    using namespace std;
    map<int, int, greater<int> > counts;
    int n=sz<<1;
    for(int i=0; i<n; counts[count(firstCell, firstCell+n, firstCell[i])]=firstCell[i], ++i);
    return counts.begin()->second;
}

замечу, что еще непонятнее и неправильнее (кстати )

[nm]

2Hrach - есть 3 варианта решения такой задачи -
1. сделать ассоциативный массив (int) -> (count) т.е. хранящий сколько раз данный инт встречается , после чего найти max от значений count, и соответствующий ему int
2. сделать как в твоем куске кода - один цикл идет по массиву, другой считает сколько раз встречается данный элемент в массиве - крайне нееффективный способ, т.к. O(N^2) операций. как пример приведу массив
[1,1,1,1,1,1,1,1,1,1,1,2,1] подумай, сколько раз функция appearance фудет высчитывать не нужное одно и то же значение для 1
3. если есть возможность копировать весь массив данных - то самый быстрый способ -- взять весь массив, отсортировать, далее в 1 проход определить последовательность каких чисел длиннее.

метод 1 - может быть крайне эффективным при том примере, который я привел - т.е. он будет хранить ровно 2 елемента, но при массиве типа [1,2,3,4,5,6,7,8,9,10,11,12,1] - он будет давать огромный overhead в использовании памяти - т.к. каждый элемент будет еще иметь с собой ссылки на другие элементы массива - т.е. эффективность будет от O(n) до O(log n) - если у тебя хватит памяти
метод 2 - квадратная зависимость от размера массива, т.е. для массива в 1000 элелемтов будет выполнено лимончик операций
метод 3 - дает постоянное (предсказуемое) использование памяти и количество операций O(n*log(n))

и ваще - можно почитать http://yenigul.net/tpop/handouts/C_Algorithms.htm просто для сравнения

мое личное предпочтение - number three - princessa Fion^W^W^W^W^W ну последний алгоритм

[AvDav]

Originally Posted by nm

замечу, что еще непонятнее и неправильнее (кстати )

почему неправильнее? считает количества вхождений для каждого элемента, если 2 или более максов даст последний макс, ну или так:

int get_max_freq_el(int* firstCell, int sz)
{
 using namespace std;
 hash_map<int, int> cc;
 int n=sz<<1;
 for(int i=0; i<n; ++cc[firstCell[i]], ++i);
 hash_map<int, int>::iterator i=cc.begin(), mit=i;
 while(i++!=cc.end()) if(mit->second < i->second) mit=i;
 return mit->first;
}

[CyberJoe]

Не, ну можно по короче, но не оптимальнее.
За корректность кода не отвечаю, нет компилятора, а так алгоритм, прост и короток. только вот работает с маленькими эллементами массива, т.е числа не должны сильно превышать какой то лимит.
Зато скорость большая даже если в массиве оооочень много эллементов.

int getmax(int * arr, int c){
int max = arr[0];
for (int i = 0; i < c; i++) if (max < arr[i]) max = arr[i];
return max;
}

int func(int * arr,int c){
int p = getmax(arr,c);
int *arr2; arr2 = new int[p];
for (int i = 0; i < c; i++) arr2[arr[i]]++;
p=getmax(arr2,p);
return p;
}

[nm]

Originally Posted by AvDav

почему неправильнее? считает количества вхождений для каждого элемента, если 2 или более максов даст последний макс, ну или так:

int get_max_freq_el(int* firstCell, int sz)
{
 using namespace std;
 hash_map<int, int> cc;
 int n=sz<<1;
 for(int i=0; i<n; ++cc[firstCell[i]], ++i);
 hash_map<int, int>::iterator i=cc.begin(), mit=i;
 while(i++!=cc.end()) if(mit->second < i->second) mit=i;
 return mit->first;
}

int n=sz<<1;

size*size rawno size*2 tol'ko w chastnom sluchae )))

[nm]

Originally Posted by CyberJoe

Не, ну можно по короче, но не оптимальнее.
............

ну, это то-же что я сказал - вариант 1 только с ограниченим что массив содержит элементы со значениями [0, p]

[AvDav]

Originally Posted by nm

int n=sz<<1;

size*size rawno size*2 tol'ko w chastnom sluchae )))

мне пора очки заказывать.

[Hrach_Techie]

спасибо большое люди!!!