Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 30.07.2005, 09:30   #1
★★★★★★★★★★★★★
 
Hrach_Techie's Avatar
 
Join Date: 08 2004
Location: London, UK
Age: 38
Posts: 16,531
Downloads: 8
Uploads: 0
Reputation: 482 | 6
Question Explain please ...

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 ...
Reply With Quote
Old 30.07.2005, 20:58   #2
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Default

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

Вродеб.
Reply With Quote
Old 31.07.2005, 10:03   #3
Untouchable misanthrope
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Pure thoughts
Age: 36
Posts: 3,408
Downloads: 22
Uploads: 0
Reputation: 222 | 3
Default

медленнее, но короче
Code:
#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;
}
Reply With Quote
Old 31.07.2005, 10:17   #4
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally Posted by AvDav
медленнее, но короче
Code:
#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;
}

замечу, что еще непонятнее и неправильнее (кстати )
Reply With Quote
Old 31.07.2005, 10:30   #5
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

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 ну последний алгоритм
Reply With Quote
Old 31.07.2005, 12:15   #6
Untouchable misanthrope
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Pure thoughts
Age: 36
Posts: 3,408
Downloads: 22
Uploads: 0
Reputation: 222 | 3
Default

Quote:
Originally Posted by nm
замечу, что еще непонятнее и неправильнее (кстати )
почему неправильнее? считает количества вхождений для каждого элемента, если 2 или более максов даст последний макс, ну или так:
Code:
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;
}
Reply With Quote
Old 31.07.2005, 12:31   #7
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Default

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

Code:
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;
}
Reply With Quote
Old 31.07.2005, 13:28   #8
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally Posted by AvDav
почему неправильнее? считает количества вхождений для каждого элемента, если 2 или более максов даст последний макс, ну или так:
Code:
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 )))
Reply With Quote
Old 31.07.2005, 13:31   #9
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally Posted by CyberJoe
Не, ну можно по короче, но не оптимальнее.
............
ну, это то-же что я сказал - вариант 1 только с ограниченим что массив содержит элементы со значениями [0, p]
Reply With Quote
Old 31.07.2005, 13:37   #10
Untouchable misanthrope
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Pure thoughts
Age: 36
Posts: 3,408
Downloads: 22
Uploads: 0
Reputation: 222 | 3
Default

Quote:
Originally Posted by nm
int n=sz<<1;

size*size rawno size*2 tol'ko w chastnom sluchae )))
мне пора очки заказывать.
Reply With Quote
Old 02.08.2005, 06:58   #11
★★★★★★★★★★★★★
 
Hrach_Techie's Avatar
 
Join Date: 08 2004
Location: London, UK
Age: 38
Posts: 16,531
Downloads: 8
Uploads: 0
Reputation: 482 | 6
Default

спасибо большое люди!!!
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 17:40.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.