Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Szybkie dodawanie i wyszukiwanie elementów

Ostatnio zmodyfikowano 2012-01-09 22:26
Autor Wiadomość
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?
P-47734
DejaVu
» 2012-01-09 18:56:46
P-47735
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?
P-47737
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ę.
P-47739
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
P-47740
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 :)
P-47741
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ć
P-47742
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.
P-47745
« 1 » 2 3
  Strona 1 z 3 Następna strona