Nasza strona używa cookies. Korzystając ze strony, wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki. Rozumiem

Wyszukiwanie liniowe w PHP - co do tego mają wartownicy?

Poznaj najprostszy i najpopularniejszy sposób wyszukiwania w PHP, czyli algorytm wyszukiwania liniowego.
Wyszukiwanie liniowe w PHP - co do tego mają wartownicy?

W życiu każdego programisty przychodzi taki etap, że standardowe metody wyszukujące dostępne w PHP nie pozwalają w łatwy sposób osiągnąć zamierzonego celu. Dzieje się tak np. wtedy, gy musimy przeszukać tablicę obiektów po określonym kluczu lub kluczach. Przykładowo listę klientów po numerze PESEL lub bazę aut po marce i modelu. Sięgamy wtedy szybko do wyszukiwarki, bierzemy pierwszą metodę przeszukującą i jesteśmy zadowoleni.

Czy to dobre podejście? Prawdopodobnie trafisz w wyszukiwarce na artykuł traktujący o wyszukiwaniu liniowym albo samodzielnie intuicyjnie je zaimplementujesz. Ekstra! Jest to jeden z najpopularniejszych i najprostszych algorytmów wyszukiwania, więc i ja postaram się go omówić, ale trochę inaczej niż w innych dostępnych źródłach – tak po mojemu 😉


Jak działa wyszukiwanie liniowe

Załóżmy, że mamy poniższą tablicę cyfr:

[2,7,4,3,2,1,7]


Potrzebujemy sprawdzić, czy w naszej tablicy znajdziemy cyfrę 5. Nasz algorytm nie robi nic innego niż przechodzi kolejno po każdym elemencie tablicy i sprawdza, czy jest to poszukiwany element. Jeżeli to on - zwraca nam jego pozycję. Jeżeli pętla nie odnajdzie naszego elementu, zwraca nam FALSE, null lub -1 – zależnie od implementacji.

enter image description here

Przykładowa implementacja wyszukiwania liniowego

Jak zapewne zauważyłeś, użyta została pętla for zamiast foreach. Zaletą użycia pętli for jest możliwość rozpoczęcia przeszukiwania od dowolnego indeksu - co może być użyte do znalezienia wszystkich pasujących wartości w zbiorze.

Mamy nasze wyszukiwanie liniowe. Czy jesteśmy w stanie przyśpieszyć w prosty sposób ten algorytm? Oczywiście! Wystarczy na koniec tablicy dodać poszukiwany element - to właśnie on jest tytułowym wartownikiem. Zwany jest tak ponieważ zabezpiecza nas przed sytuacją, gdy dany element nie istnieje w tablicy.


Gdzie tu optymalizacja?

Klucz tkwi w tym, że teraz w każdym obiegu pętli nie sprawdzamy czy jesteśmy jeszcze w zakresie zbioru, a w zamian po znalezieniu elementu, sprawdzamy tylko raz jego pozycję - czy jest to pozycja wartownika. Jeśli tak, element nie istnieje w tablicy - w innym przypadku - to nasz poszukiwany element. Pozornie oszczędzamy niewiele, bo tylko jedno porównanie w pętli mniej - zależnie od przypadku, możemy zaoszczędzić dość sporo lub mało stracić - ale o tym za chwilę.

Wyszukiwanie liniowe z wartownikiem - blokowy

Wyszukiwanie liniowe z wartownikiem

No dobrze, to ile właściwie oszczędzamy na wartowniku? Przeanalizujmy ilość operacji dla wariantu pesymistycznego - poszukiwany element znajduje się na ostatnim miejscu zbioru, oraz przypadek uśredniony - element statystycznie znajduje się w środku zbioru.

Jak widzisz, ilość porównań jest zależna od wielkości przeszukiwanego zbioru. Im większy zbiór, tym większe korzyści otrzymujemy, lecz przy relatywnie małych zbiorach spowalniamy działanie naszego algorytmu.

Teraz spójrzmy na realne czasy wykonania. Test przebiegł następująco: Generujemy dane wejściowe. Tablica o wielkości n w zakresie 1-10000 elementów. Wypełniamy ją liczbami pseudolosowymi liczbami całkowitymi w zakresie 1 - 10n. Następnie z tego zakresu losujemy poszukiwaną wartość.

Uruchamiamy kolejno funkcje z tym samym zestawem danych: wyszukiwanie liniowe oraz wyszukiwanie z wartownikiem. Dla każdego mierzymy czas. Procedurę powtarzamy 1000 razy, a na koniec obliczamy średnie czasy wykonania każdej z metod.

Kod odpowiedzialny za przeprowadzenie testu jest dostępny tutaj.

Wyniki testu nie są zaskakujące: 

enter image description here

Zdaję sobie sprawę, że podczas tego testu miało miejsce zbyt wiele czynników mogących zaburzyć końcowy wynik, ale tendencja ukazana w teście jest jak najbardziej prawidłowa i zgodna z oczekiwaniami.


Podsumowanie

Powyższe algorytmy bez problemu możemy użyć w przypadku, gdy chcemy znaleźć wszystkie elementy w zbiorze, a nie tylko pierwszy, jak w podanych przykładach. Należy wtedy do metody dodać argument mówiący o indeksie, od którego należy zacząć przeszukiwanie. Początkowo powinien mieć wartość 0, a następnie ostatni znaleziony element +1. Wtedy zaczynamy przeszukiwać od podanego miejsca w zbiorze.

Pamiętaj - znajomość algorytmów to jedno, a wiedza który wybrać w danej sytuacji, to drugie. A więc kiedy rozważać wybór algorytmów liniowych?

Wyszukiwania liniowego najczęściej używamy, gdy nie mamy żadnych wstępnych informacji o zbiorze lub wiemy, że zbiór nie jest posortowany. W takich sytuacjach musimy niestety przeszukać wszystkie elementy tablicy.

Sugerując się tabelką, wyszukiwania liniowego użyłbym w sytuacji, gdy wiem, że ilość elementów zbioru nie jest większa od sześciu w innym wypadku, gdy jest większa lub nie znam/nie potrafię oszacować wielkości zbioru zaryzykowałbym i użyłbym wersji z wartownikiem.



Artykuł oryginalnie opublikowany na stronie phpdev.tech.

Rozpocznij dyskusję

Lubisz dzielić się wiedzą i chcesz zostać autorem?

Podziel się wiedzą z 160 tysiącami naszych czytelników

Dowiedz się więcej