Wyszukiwanie liniowe - 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. 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.

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.

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ę.

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.

Wyszukiwanie liniowe Powtórzenia
Krok Operacja PesymistycznyUś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 PesymistycznyUś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: 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 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.


Autor: Artur

artur@lisart.pl