ison |
» 2012-01-09 19:19:13 @up: to co proponuję jest szybsze.
|
jest ale tylko w niektórych przypadkach :) mówię, że zależy od tego ile razy i kiedy chcemy sprawdzać czy istnieje element for( int i = 0; i < n; ++i ) {
dodaj_element( random() );
sprawdz_czy_istnieje( random() );
}
przeanalizujmy 2 rozwiązania: rozwiązanie z vectorem: -dodanie elementu w czasie stałym -sprawdzenie czy istnieje na podstawie binsearcha wymaga posortowanego ciągu -> n log n końcowa złożoność (pętla for): n*n log n -> O(n^2 log n) rozwiązanie z mapą: -dodanie elementu w czasie log n -sprawdzenie czy istnieje w czasie log n końcowa złożoność (pętla for): n*log n -> O(n log n) widać różnicę :) |
|
DejaVu |
» 2012-01-09 19:22:12 Widzisz... Ty opierasz się na matematyce, a ja na doświadczeniu :) |
|
ison |
» 2012-01-09 19:24:34 ... czy twierdzisz, że rozwiązanie kwadratowe jest szybsze od rozwiązania n log n? Opieram się na własnym doświadczeniu, i takich testów robiłem już miliony i mogę z czystym sercem powiedzieć, że to co się bardziej opłaca zależy od tego kiedy i ile razy chcemy wyszukać element. Napisz przykładowy test w którym zaproponowane przeze mnie rozwiązanie Twoim zdaniem rozwiązanie będzie wolniejsze :)
|
OK, to o ile się zakładamy? :D oczywiście podkreślam, że teraz rozmawiamy o przypadku gdzie po każdym dodaniu elementu chcę wyszukać czy istnieje dany element -> żeby było jasne ;) w innym przypadku, gdzie chcemy wyszukać element po dodaniu n elementów, to nie przeczę temu, że rozwiązanie z vectorem będzie znacznie szybsze |
|
Marys Temat założony przez niniejszego użytkownika |
» 2012-01-09 19:31:10 To pomogę wam. Jest powtarzany taki cykl:
dodaj do list element
sprawdź czy element+1 występuje na liście
sprawdź czy element-1 występuje na liście
sprawdź czy element+x występuje na liście
sprawdź czy element-x występuje na liście
|
|
pekfos |
» 2012-01-09 19:32:38 Wszystko zależy gdzie to ma być użyte. Rozwiązania najlepszego pod każdym względem nie ma. :)
PS: ahh, ubiegł mnie. Częściej szukasz więc idź w stronę vectora. |
|
ison |
» 2012-01-09 19:53:29 Częściej szukasz więc idź w stronę vectora.
|
odwrotnie ;p jak częściej szuka to niech trzyma elementy w kontenerze gdzie będzie miał szybki dostęp do posortowanego ciągu, w przypadku vectora przed każdym sprawdzeniem czy istnieje element trzeba posortować cały vector co jest dosyć czasochłonne porównanie rozwiązania z vectorem i mapą (chociaż mapę można zastąpić multisetem ;p ale jak już miała być ta mapa to niech będzie mapa ;)) #include <map>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#define QUANTITY (10000)
int getRandom()
{
return rand() % 1000;
}
void f1()
{
std::vector < int > vec;
for( int i = 0; i < QUANTITY; ++i ) {
vec.push_back( getRandom() );
std::sort( vec.begin(), vec.end() );
bool exists = std::binary_search( vec.begin(), vec.end(), getRandom() );
}
}
void f2()
{
std::map < int, bool > m;
for( int i = 0; i < QUANTITY; ++i ) {
m.insert( std::pair < int, bool >( getRandom(), true ) );
std::map < int, bool >::iterator it = m.find( getRandom() );
bool exists =( it != m.end() );
}
}
int main()
{
srand( time( 0 ) );
clock_t start1 = clock();
f1();
printf( "vector: %d ms\n", int(( clock() - start1 ) * CLOCKS_PER_SEC / 1000 ) );
clock_t start2 = clock();
f2();
printf( "map: %d ms\n", int(( clock() - start2 ) * CLOCKS_PER_SEC / 1000 ) );
}
dla 1000 elementów: vector: 28 ms
map: 0 ms
10000: vector: 3473 ms
map: 3 ms
50000: vector: 78357 ms
map: 10 ms
lekka różnica jest :) |
|
pekfos |
» 2012-01-09 19:58:35 | odwrotnie ;p jak częściej szuka to niech trzyma elementy w kontenerze gdzie będzie miał szybki dostęp do posortowanego ciągu, w przypadku vectora przed każdym sprawdzeniem czy istnieje element trzeba posortować cały vector co jest dosyć czasochłonne |
Jak wie że nic nie było dodane, to może raz posortować i przeszukać binarnie :P Poza tym dostęp do elementów w vector jest w złożoności O(1) a w kontenerach o strukturze drzewa, O(n) :P |
|
ison |
» 2012-01-09 20:03:26 Jak wie że nic nie było dodane, to może raz posortować i przeszukać binarnie :P
|
dodaj do list element
sprawdź czy element+1 występuje na liście
sprawdź czy element-1 występuje na liście
sprawdź czy element+x występuje na liście
sprawdź czy element-x występuje na liście
|
... ;) Poza tym dostęp do elementów w vector jest w złożoności O(1) a w kontenerach o strukturze drzewa, O(n) :P
|
zgadza się, ale żeby zapuścić bsearcha vector musi być posortowany w czasie n log n za każdym razem a set nie, a jeśli autor tematu chce często dodawać i tuż po tym sprawdzać czy istnieje element to... zerknij na moje porównanie 2 rozwiązań wyżej :) |
|
| 1 « 2 » 3 |