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. w tedy kiedy 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. Ale czy to jest dobre podejście? Prawdopodobnie trafisz w wyszukiwarce na artykuł traktujący o wyszukiwaniu liniowym -albo sam je intuicyjnie 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 😉
Tyle wstępu, teraz trochę teorii. 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.
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.
A więc dobrze, 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 on jest zwany wartownikiem. Zwany jest tak ponieważ zabezpiecza nas przed sytuacją, gdy dany element nie istnieje w tablicy. Ale zapytasz jak to? 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 nie wiele, 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ę.
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.
| Wyszukiwanie liniowe | Powtórzenia | ||
| Krok | Operacja | Pesymistyczny | Uśredniony |
| 1 | $i=0 | 1 | 1 |
| 2 | Jeśli $i >= $n zwróć -1 | n + 1 | n/2 +1 |
| 3 | Jeśli $tab[$i] == $poszukiwany element zwróć i | n | n/2 |
| 4 | $i++ | n | n/2 |
| 5 | Wróć do kroku 2 | n | n/2 |
| Łącznie | 4n+2 | 2n+2 |
| Wyszukiwanie liniowe z wartownikiem | Powtórzenia | ||
| Krok | Operacja | Pesymistyczny | Uśredniony |
| 1 | Dodaj poszukiwany element na koniec zbioru | 1 | 1 |
| 2 | $i = 0 | 1 | 1 |
| 3 | Jeśli $tab[$i] == $poszukiwany element idź do kroku 6 | n+1 | n/2 +1 |
| 4 | $i++ | n | n/2 |
| 5 | Wróć do kroku 3 | n | n/2 |
| 6 | jeśli $i ma wartość ostatniego elementu zbioru, zwróć -1, w innym przypadku $i | 1 | 1 |
| Łącznie | 3n+4 | 3/2n+5 |
| N | Przypadek pesymistyczny | Przypadek uśredniony | ||
|---|---|---|---|---|
| Wyszukiwanie Liniowe | Wyszukiwanie Liniowe z wartownikiem | Wyszukiwanie liniowe | Wyszukiwanie liniowe z wartownikiem | |
| 4n+2 | 3n+4 | 2n+2 | 3/2n +5 | |
| 1 | 6 | 7 | 4 | 6.5 |
| 2 | 10 | 10 | 6 | 8 |
| 3 | 14 | 13 | 8 | 9.5 |
| 4 | 18 | 16 | 10 | 11 |
| 5 | 22 | 19 | 12 | 12.5 |
| 6 | 26 | 22 | 14 | 14 |
| 10 | 42 | 34 | 22 | 20 |
| 100 | 402 | 304 | 202 | 155 |
| 1000 | 4002 | 3004 | 2002 | 1505 |
| 10000 | 40002 | 30004 | 20002 | 15005 |
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.
A 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: https://pastebin.pl/view/5f8c5d12
Wyniki testu nie są zaskakujące:
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 w tedy 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. W tedy 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ą wyszukiwanie liniowe 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.
