Szybkie dodawanie i wyszukiwanie elementów
Ostatnio zmodyfikowano 2012-01-09 22:26
Marys Temat założony przez niniejszego użytkownika |
Szybkie dodawanie i wyszukiwanie elementów » 2012-01-09 18:54:30 Witam,
poszukuje szybkiej metody dodawania elementów do listy oraz sprawdzania czy element na tej liście się znajduje. Początkowo korzystałem ze stosu. Rozwiązań jest wiele, ale które będzie najszybsze? |
|
DejaVu |
» 2012-01-09 18:56:46 |
|
Marys Temat założony przez niniejszego użytkownika |
» 2012-01-09 19:04:32 A skorzystanie po prostu z listy (list) lub jej odmiany deque? |
|
DejaVu |
» 2012-01-09 19:06:33 Porób sobie testy - ja Ci napisałem co będzie najszybsze do zadania, które chcesz zrealizować. Chcesz szukać kompromisu to go szukaj na własną rękę. |
|
ison |
» 2012-01-09 19:06:42 std::map dodawanie elementu w czasie log n szukanie czy istnieje element w czasie log n
chyba, że wolisz powrzucać elementy do vectora, posortować go i zapuścić bsearcha, albo powrzucać elementy do multiseta i zapuścić bsearcha, sam zdecyduj co Ci się najbardziej opłaca biorąc pod uwagę to ile razy wrzucasz, a ile razy szukasz elementu |
|
DejaVu |
» 2012-01-09 19:08:07 @up: wystarczyłby std::set, a poza tym jest to rozwiązanie dużo wolniejsze niż to co napisałem :) |
|
ison |
» 2012-01-09 19:10:51 @up: wystarczyłby std::set, a poza tym jest to rozwiązanie dużo wolniejsze niż to co napisałem :)
|
nie jest, to co jest szybsze zależy od tego ile razy ktoś chce dodawać element i go szukać w Twoim rozwiązaniu po każdym dodaniu elementu trzeba stracić n log n na posortowanie vectora, dla wrzucenia n elementów i zapytania się o jakiś element po każdym dodaniu elementu złożoność będzie okropna, imho najlepiej multiseta użyć |
|
DejaVu |
» 2012-01-09 19:14:55 @up: to co proponuję jest szybsze. Dodając 1 element na końcu nie uzyskujesz złożoności n*log(n) tylko złożoność niewiele większą niż liniowa. Po drugie: póki nie wyszukujesz to nie musisz sortować danych, więc dodawanie elementów można zrobić w czasie stałym O(1). Wyszukiwanie binarne na tablicy jest dużo szybsze niż wyszukiwanie na strukturze drzewiastej. Dodam jeszcze, że balansowanie drzewa to też mimo wszystko koszt. To, że złożoność jest teoretycznie log(n) nie oznacza wcale, że rozwiązanie będzie lepsze lub nawet porównywalne. |
|
« 1 » 2 3 |