Autor Wątek: Algorytm przeszukiwania  (Przeczytany 1506 razy)

Offline Ed

  • Użytkownik

# Grudzień 24, 2006, 12:21:07
Witam !

Jestem ciekaw jaki algorytm szukania polecacie ? Jaki wybrać do swojej gry/silnika ? Proszę o jakieś nazwy i jeśli to możliwe jakiś link do arta lub sampla.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Grudzień 24, 2006, 12:49:46
Może coś więcej? Czego szukasz? W jakim zbiorze? Jakie cechy mają te dane? To tak jakbyś pytał - jakiego algorytmu sortowania używamy? Wybór algorytmu zależy od danych i ich układu. Co do samego szukania po posortowanej tablicy to pewnie połówkowe będzie najczęściej spotykanym.

Offline Ed

  • Użytkownik

# Grudzień 24, 2006, 13:49:27
Chodzi mi o przeszukiwanie tablic bądź wektorów STL bo z tego korztam najczęściej.

Offline mINA87

  • Użytkownik

# Grudzień 24, 2006, 14:02:12
Czego szukasz? Max? Min? Konkretnego elementu? Jak sa ulozone elementy w tablicy? Dowolnie? Posortowane?

Offline Ed

  • Użytkownik

# Grudzień 24, 2006, 14:05:08
no zależy raz potrzebuje min , raz max, a raz konkretnego elementu. Nieposortowe.

Offline vashpan

  • Użytkownik
    • Strona

# Grudzień 24, 2006, 14:34:08
Hmm jak dla mnie warto korzystac z STL, rozwiazanie najbardziej przenosne chyba, no i w miare szybkie...

#include <algorithm>

//ta druga wersja funkcji to wtedy gdy korzystamy z innego porownania niz operator <
iterator max_element( iterator start, iterator end );
iterator max_element( iterator start, iterator end, BinPred p );

iterator min_element( iterator start, iterator end );
iterator min_element( iterator start, iterator end, BinPred p );

//do szukania:
iterator find( iterator start, iterator end, const TYPE& val );


Offline Xion

  • Moderator
    • xion.log

# Grudzień 24, 2006, 14:48:07
Do szukania jest jeszcze find_if(), poszukujący pierwszego elementu spełniającego dany predykat logiczny.

Czy są one szybkie? To rzecz względna, w nieposortowanych danych będą one wykonywały się liniowo względem ich ilości. Jeżeli operacja szukania dowolnego elementu jest przeprowadzana często, to warto rozważyć zbiór (set). Jeżeli zaś często interesuje nas element max/min, to odpowiednia jest kolejka priorytetowa (priority_queue).

Offline Smetana

  • Użytkownik

# Grudzień 24, 2006, 14:58:04
Cytuj
no zależy raz potrzebuje min , raz max, a raz konkretnego elementu. Nieposortowe.
Jak są nieposortowane i są zwykłym wektorem to możesz sam szybko napisać proste funkcje o złożoności n. Jak ci zależny na czymś szybszym to musisz pomyśleć o jakiejś strukturze danych, np. kopiec.

edit: Od kopca lepsze by było dla max i min takie drzewko BST, albo lepiej AVL.
« Ostatnia zmiana: Grudzień 24, 2006, 15:03:29 wysłana przez Smetana »