Wprowadzenie

Szukanie danych przechowywanych w różnych strukturach danych jest kluczową częścią prawie każdej pojedynczej aplikacji.

Istnieje wiele różnych algorytmów dostępnych do wykorzystania podczas wyszukiwania, a każdy z nich ma różne implementacje i opiera się na różnych strukturach danych, aby wykonać zadanie.

Bycie w stanie wybrać konkretny algorytm dla danego zadania jest kluczową umiejętnością dla programistów i może oznaczać różnicę między szybką, niezawodną i stabilną aplikacją a aplikacją, która rozpada się od prostego żądania.

• Operatory członkowskie
• Szukanie liniowe
• Szukanie binarne
• Szukanie skokowe
• Szukanie Fibonacciego
• Szukanie wykładnicze
• Szukanie interpolacyjne

.

Operatory członkowskie

Algorytmy rozwijają się i stają się z czasem optymalizowane w wyniku ciągłej ewolucji i potrzeby znalezienia najbardziej efektywnych rozwiązań dla podstawowych problemów w różnych dziedzinach.

Jednym z najczęstszych problemów w dziedzinie informatyki jest przeszukiwanie kolekcji i określanie, czy dany obiekt jest w niej obecny, czy nie.

Prawie każdy język programowania posiada własną implementację podstawowego algorytmu wyszukiwania, zazwyczaj jako funkcję, która zwraca Boolean wartość True lub False, gdy w danym zbiorze elementów zostanie znaleziony element.

W Pythonie najprostszym sposobem wyszukiwania obiektu jest użycie operatorów przynależności – nazwanych tak, ponieważ pozwalają nam określić, czy dany obiekt jest członkiem kolekcji.

Operatory te mogą być używane z dowolną iterowalną strukturą danych w Pythonie, w tym z łańcuchami, listami i tuplami.

• in – Zwraca True, jeśli podany element jest częścią struktury.
• not in – Zwraca True, jeśli dany element nie jest częścią struktury.

>>> 'apple' in True>>> 't' in 'stackabuse'True>>> 'q' in 'stackabuse'False>>> 'q' not in 'stackabuse'True

Operatory członkostwa wystarczają, gdy wszystko, co musimy zrobić, to znaleźć, czy podłańcuch istnieje w danym łańcuchu, lub określić, czy dwa łańcuchy, listy lub tuple przecinają się pod względem obiektów, które przechowują.

W większości przypadków potrzebujemy pozycji elementu w sekwencji, oprócz określenia, czy istnieje, czy nie; operatory członkostwa nie spełniają tego wymagania.

Istnieje wiele algorytmów wyszukiwania, które nie zależą od wbudowanych operatorów i mogą być używane do wyszukiwania wartości szybciej i/lub bardziej wydajnie. Ponadto mogą one dostarczyć więcej informacji, takich jak pozycja elementu w kolekcji, a nie tylko określić jego istnienie.

Szukanie liniowe

Szukanie liniowe jest jednym z najprostszych algorytmów wyszukiwania i najłatwiejszym do zrozumienia. Możemy o nim myśleć jak o rozwiniętej wersji naszej własnej implementacji operatora in w Pythonie.

Algorytm polega na iterowaniu po tablicy i zwracaniu indeksu pierwszego wystąpienia elementu, gdy zostanie on znaleziony:

def LinearSearch(lys, element): for i in range (len(lys)): if lys == element: return i return -1

Jeśli więc użyjemy funkcji do obliczenia:

>>> print(LinearSearch(, 2))

Po wykonaniu kodu przywita nas:

1

Jest to indeks pierwszego wystąpienia elementu, którego szukamy – pamiętając, że indeksy w Pythonie są oparte na 0.

Złożoność czasowa wyszukiwania liniowego wynosi O(n), co oznacza, że czas wykonania wzrasta wraz z liczbą elementów na naszej liście wejściowej lys.

Wyszukiwanie liniowe nie jest często stosowane w praktyce, ponieważ taką samą wydajność można osiągnąć za pomocą wbudowanych metod lub istniejących operatorów, a nie jest ono tak szybkie lub wydajne jak inne algorytmy wyszukiwania.

Wyszukiwanie liniowe jest dobrym rozwiązaniem, gdy musimy znaleźć pierwsze wystąpienie elementu w nieposortowanej kolekcji, ponieważ w przeciwieństwie do większości innych algorytmów wyszukiwania nie wymaga sortowania kolekcji przed rozpoczęciem wyszukiwania.

Wyszukiwanie binarne

Wyszukiwanie binarne stosuje metodę dziel i zwyciężaj. Jest ono szybsze niż wyszukiwanie liniowe, ale wymaga posortowania tablicy przed wykonaniem algorytmu.

Zakładając, że szukamy wartości val w posortowanej tablicy, algorytm porównuje val z wartością środkowego elementu tablicy, który nazwiemy mid.

• Jeśli mid jest elementem, którego szukamy (najlepszy przypadek), zwracamy jego indeks.
• Jeśli nie, określamy, po której stronie mid val jest bardziej prawdopodobne, w oparciu o to, czy val jest mniejsze lub większe niż mid, i odrzucamy drugą stronę tablicy.
• Następnie rekurencyjnie lub iteracyjnie wykonujemy te same kroki, wybierając nową wartość dla mid, porównując ją z val i odrzucając połowę możliwych dopasowań w każdej iteracji algorytmu.

Algorytm wyszukiwania binarnego można napisać albo rekurencyjnie, albo iteracyjnie. Rekursja jest generalnie wolniejsza w Pythonie, ponieważ wymaga alokacji nowych ramek stosu.

Ponieważ dobry algorytm wyszukiwania powinien być tak szybki i dokładny, jak to tylko możliwe, rozważmy iteracyjną implementację wyszukiwania binarnego:

Jeśli użyjemy funkcji do obliczenia:

>>> BinarySearch(, 20)

Dostaniemy wynik:

1

Który jest indeksem wartości, której szukamy.

Akcja, którą algorytm wykonuje następnie w każdej iteracji, jest jedną z kilku możliwości:

• Przywrócenie indeksu bieżącego elementu
• Przeszukanie lewej połowy tablicy
• Przeszukanie prawej połowy tablicy

Możemy wybrać tylko jedną możliwość na iterację, a nasza pula możliwych dopasowań zostaje podzielona przez dwa w każdej iteracji. To sprawia, że złożoność czasowa wyszukiwania binarnego jest O(log n).

Jedną z wad wyszukiwania binarnego jest to, że jeśli istnieje wiele wystąpień elementu w tablicy, nie zwraca ono indeksu pierwszego elementu, ale raczej indeks elementu najbliższego środka:

>>> print(BinarySearch(, 4))

Wykonanie tego fragmentu kodu da w wyniku indeks środkowego elementu:

1

Dla porównania wykonanie wyszukiwania liniowego na tej samej tablicy zwróciłoby:

0

Który jest indeksem pierwszego elementu. Nie można jednak kategorycznie stwierdzić, że wyszukiwanie binarne nie działa, jeśli tablica zawiera ten sam element dwa razy – może działać tak samo jak wyszukiwanie liniowe i zwracać pierwsze wystąpienie elementu w niektórych przypadkach.

Jeśli wykonamy wyszukiwanie binarne na tablicy na przykład i szukamy 4, otrzymamy 3 jako wynik.

Wyszukiwanie binarne jest dość powszechnie stosowane w praktyce, ponieważ jest wydajne i szybkie w porównaniu do wyszukiwania liniowego. Ma ono jednak pewne wady, takie jak zależność od operatora //. Istnieje wiele innych algorytmów wyszukiwania divide and conquer, które pochodzą z wyszukiwania binarnego, zbadajmy kilka z nich następnie.

Szukanie skokowe

Szukanie skokowe jest podobne do wyszukiwania binarnego w tym, że działa na posortowanej tablicy i wykorzystuje podobne podejście divide and conquer do przeszukiwania go.

Można go sklasyfikować jako ulepszenie algorytmu wyszukiwania liniowego, ponieważ zależy on od wyszukiwania liniowego, aby wykonać rzeczywiste porównanie podczas wyszukiwania wartości.

Dając posortowaną tablicę, zamiast przeszukiwać elementy tablicy przyrostowo, przeszukujemy ją skokowo. Tak więc w naszej liście wejściowej lys, jeśli mamy rozmiar skoku skoku, nasz algorytm rozważy elementy w kolejności lys, lys, lys, lys i tak dalej.

Przy każdym skoku przechowujemy poprzednią wartość, na którą patrzyliśmy i jej indeks. Gdy znajdziemy zbiór wartości, w którym lys<element<lys, wykonujemy wyszukiwanie liniowe z lys jako lewym najbardziej oddalonym elementem i lys jako prawym najbardziej oddalonym elementem w naszym zbiorze wyszukiwania:

Ponieważ jest to złożony algorytm, rozważmy obliczanie krok po kroku wyszukiwania skokowego z tymi danymi wejściowymi:

>>> print(JumpSearch(, 5))

• Szukanie skokowe najpierw określiłoby rozmiar skoku przez obliczenie math.sqrt(len(lys)). Ponieważ mamy 9 elementów, rozmiar skoku wyniósłby √9 = 3.
• Następnie obliczamy wartość zmiennej right, która jest minimalną długością tablicy minus 1 lub wartością left+jump, która w naszym przypadku wyniosłaby 0+3= 3. Ponieważ 3 jest mniejsze od 8 używamy 3 jako wartości right.
• Teraz sprawdzamy, czy nasz szukany element, 5, znajduje się pomiędzy lys a lys. Ponieważ 5 nie znajduje się między 1 a 4, przechodzimy dalej.
• Następnie ponownie wykonujemy obliczenia i sprawdzamy, czy nasz element szukany znajduje się między lys a lys, gdzie 6 to 3+skok. Ponieważ 5 jest pomiędzy 4 i 7, wykonujemy wyszukiwanie liniowe na elementach pomiędzy lys i lys i zwracamy indeks naszego elementu jako:

4

Złożoność czasowa wyszukiwania skokowego wynosi O(√n), gdzie √n jest rozmiarem skoku, a n jest długością listy, umieszczając wyszukiwanie skokowe pomiędzy algorytmami wyszukiwania liniowego i wyszukiwania binarnego pod względem wydajności.

Jedną z najważniejszych zalet wyszukiwania skokowego w porównaniu z wyszukiwaniem binarnym jest to, że nie polega ono na operatorze podziału (/).

W większości procesorów użycie operatora dzielenia jest kosztowne w porównaniu z innymi podstawowymi operacjami arytmetycznymi (dodawanie, odejmowanie i mnożenie), ponieważ implementacja algorytmu dzielenia jest iteracyjna.

Koszt sam w sobie jest bardzo mały, ale gdy liczba elementów do przeszukania jest bardzo duża, a liczba operacji dzielenia, które musimy wykonać wzrasta, koszt ten może narastać. Dlatego wyszukiwanie skokowe jest lepsze od wyszukiwania binarnego, gdy mamy do czynienia z dużą liczbą elementów w systemie, w którym nawet niewielki wzrost szybkości ma znaczenie.

Aby uczynić wyszukiwanie skokowe szybszym, moglibyśmy użyć wyszukiwania binarnego lub innego wewnętrznego wyszukiwania skokowego do przeszukiwania bloków, zamiast polegać na znacznie wolniejszym wyszukiwaniu liniowym.

Wyszukiwanie Fibonacciego

Wyszukiwanie Fibonacciego jest kolejnym algorytmem dziel i zwyciężaj, który wykazuje podobieństwa zarówno do wyszukiwania binarnego, jak i skokowego. Jego nazwa pochodzi od tego, że używa liczb Fibonacciego do obliczania rozmiaru bloku lub zakresu wyszukiwania w każdym kroku.

Liczby Fibonacciego zaczynają się od zera i działają według wzoru 0, 1, 1, 2, 3, 5, 8, 13, 21… gdzie każdy element jest sumą dwóch liczb, które go bezpośrednio poprzedzają.

Algorytm działa z trzema liczbami Fibonacciego naraz. Nazwijmy te trzy liczby fibM, fibM_minus_1 i fibM_minus_2, gdzie fibM_minus_1 i fibM_minus_2 są dwiema liczbami bezpośrednio przed fibM w sekwencji:

fibM = fibM_minus_1 + fibM_minus_2

Inicjalizujemy wartości na 0,1 i 1 lub pierwsze trzy liczby w sekwencji Fibonacciego, aby uniknąć otrzymania błędu indeksu w przypadku, gdy nasza tablica wyszukiwania lys zawiera bardzo małą liczbę elementów.

Następnie wybieramy najmniejszą liczbę ciągu Fibonacciego, która jest większa lub równa liczbie elementów w naszej tablicy wyszukiwania lys, jako wartość fibM, a dwie liczby Fibonacciego bezpośrednio przed nią jako wartości fibM_minus_1 i fibM_minus_2. Gdy w tablicy pozostały elementy, a wartość fibM jest większa od jeden, to:

• Porównujemy val z wartością bloku w zakresie do fibM_minus_2 i zwracamy indeks elementu, jeśli pasuje.
• Jeśli wartość jest większa niż element, na który aktualnie patrzymy, przesuwamy wartości fibM, fibM_minus_1 i fibM_minus_2 o dwa kroki w dół w sekwencji Fibonacciego i resetujemy indeks do indeksu elementu.
• Jeśli wartość jest mniejsza niż element, na który aktualnie patrzymy, przesuwamy wartości fibM, fibM_minus_1 i fibM_minus_2 o jeden krok w dół w sekwencji Fibonacciego.

Przyjrzyjrzyjmy się implementacji tego algorytmu w języku Python:

Jeśli użyjemy funkcji FibonacciSearch do obliczenia:

>>> print(FibonacciSearch(, 6))

Przyjrzyjrzyjmy się procesowi tego wyszukiwania krok po kroku:

• Wyznaczenie najmniejszej liczby Fibonacciego większej lub równej długości listy jako fibM; w tym przypadku najmniejszą liczbą Fibonacciego spełniającą nasze wymagania jest 13.
• Wartości te zostałyby przypisane jako:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• Następnie sprawdzamy element lys, gdzie 4 jest minimum z -1+5 . Ponieważ wartość lys wynosi 5, a więc jest mniejsza od szukanej wartości, przesuwamy liczby Fibonacciego o jeden krok w dół w ciągu, dzięki czemu wartości:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• Następnie sprawdzamy element lys, gdzie 7 jest minimum z 4+3. Ponieważ wartość lys wynosi 8, czyli jest większa od szukanej przez nas wartości, przesuwamy liczby Fibonacciego o dwa kroki w dół w sekwencji.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• Teraz sprawdzamy element lys, gdzie 5 jest minimum liczby 4+1 . Wartość lys to 6, czyli wartość, której szukamy!

Wynik, zgodnie z oczekiwaniami to:

5

Złożoność czasowa wyszukiwania Fibonacciego to O(log n); taka sama jak wyszukiwania binarnego. Oznacza to, że algorytm jest szybszy zarówno od wyszukiwania liniowego, jak i skokowego w większości przypadków.

Wyszukiwanie Fibonacciego może być użyte, gdy mamy bardzo dużą liczbę elementów do przeszukania i chcemy zmniejszyć nieefektywność związaną z użyciem algorytmu, który opiera się na operatorze podziału.

Dodatkową zaletą stosowania wyszukiwania Fibonacciego jest to, że może ono obsługiwać tablice wejściowe, które są zbyt duże, aby zmieścić je w pamięci podręcznej procesora lub w pamięci RAM, ponieważ przeszukuje elementy w coraz większych krokach, a nie w stałym rozmiarze.

Wyszukiwanie wykładnicze

Wyszukiwanie wykładnicze to kolejny algorytm wyszukiwania, który można zaimplementować w Pythonie w dość prosty sposób, w porównaniu z wyszukiwaniem skokowym i wyszukiwaniem Fibonacciego, które są nieco bardziej złożone. Jest on również znany pod nazwami: wyszukiwanie galopujące, wyszukiwanie podwajające i wyszukiwanie Struzika.

Wyszukiwanie wykładnicze zależy od wyszukiwania binarnego, aby wykonać ostateczne porównanie wartości. Algorytm działa poprzez:

• Określenie zakresu, w którym prawdopodobnie znajduje się szukany przez nas element
• Użycie wyszukiwania binarnego dla zakresu w celu znalezienia dokładnego indeksu elementu

Implikacja algorytmu wyszukiwania wykładniczego w języku Python to:

Jeśli użyjemy funkcji do znalezienia wartości:

>>> print(ExponentialSearch(,3))

Algorytm działa poprzez:

• Sprawdzenie, czy pierwszy element na liście pasuje do wartości, której szukamy – ponieważ lys to 1, a my szukamy 3, ustawiamy indeks na 1 i przechodzimy dalej.
• Przejście przez wszystkie elementy listy i w momencie, gdy element na pozycji index’th jest mniejszy lub równy naszej wartości, wykładniczo zwiększamy wartość index w wielokrotnościach dwójki:
  • index = 1, lys jest 2, co jest mniejsze niż 3, więc indeks jest mnożony przez 2 i ustawiany na 2.
  • index = 2, lys jest 3, co jest równe 3, więc indeks jest mnożony przez 2 i ustawiany na 4.
  • index = 4, lys wynosi 5, co jest większe niż 3; pętla jest przerywana w tym momencie.
• Wykonuje następnie wyszukiwanie binarne, krojąc listę; arr. W Pythonie oznacza to, że lista podrzędna będzie zawierała wszystkie elementy aż do 4. elementu, więc tak naprawdę wywołujemy:

>>> BinarySearch(, 3)

, co zwróciłoby:

2

, co jest indeksem elementu, którego szukamy zarówno na oryginalnej liście, jak i na liście pokrojonej, którą przekazujemy do algorytmu wyszukiwania binarnego.

Ekspresowe wyszukiwanie przebiega w czasie O(log i), gdzie i jest indeksem szukanego elementu. W najgorszym przypadku złożoność czasowa wynosi O(log n), gdy szukanym elementem jest ostatni element (n to długość tablicy).

Wyszukiwanie wykładnicze działa lepiej niż binarne, gdy szukany element znajduje się bliżej początku tablicy. W praktyce używamy wyszukiwania wykładniczego, ponieważ jest to jeden z najbardziej wydajnych algorytmów wyszukiwania dla tablic nieograniczonych lub nieskończonych.

Wyszukiwanie interpolacyjne

Wyszukiwanie interpolacyjne jest kolejnym algorytmem dziel i zwyciężaj, podobnym do wyszukiwania binarnego. W przeciwieństwie do wyszukiwania binarnego, nie zawsze rozpoczyna wyszukiwanie od środka. Wyszukiwanie interpolacyjne oblicza prawdopodobną pozycję szukanego elementu według wzoru:

index = low + )*(high-low) / (lys-lys)]

Gdzie zmiennymi są:

• lys – nasza tablica wejściowa
• val – szukany element
• index – prawdopodobny indeks szukanego elementu. Jest on obliczany jako wartość wyższa, gdy val jest bliższy wartością elementowi na końcu tablicy (lys), a niższa, gdy val jest bliższy wartością elementowi na początku tablicy (lys)
• low – indeks początkowy tablicy
• high – indeks ostatni tablicy

Algorytm wyszukuje obliczając wartość index:

• Jeśli znaleziono dopasowanie (gdy lys == val), zwracany jest indeks
• Jeśli wartość val jest mniejsza niż lys, wartość dla indeksu jest ponownie obliczana z wykorzystaniem wzoru dla lewej podtablicy
• Jeśli wartość val jest większa niż lys, wartość dla indeksu jest ponownie obliczana przy użyciu formuły dla prawej podrzędnej tablicy

Przejdźmy dalej i zaimplementujmy wyszukiwanie interpolacyjne przy użyciu Pythona:

Jeśli użyjemy funkcji do obliczania:

>>> print(InterpolationSearch(, 6))

Naszymi wartościami początkowymi byłyby:

• val = 6,
• low = 0,
• high = 7,
• lys = 1,
• lys = 8,
• index = 0 + = 5

Ponieważ lys wynosi 6, czyli wartość, której szukamy, przerywamy wykonywanie i zwracamy wynik:

5

Jeśli mamy dużą liczbę elementów, a naszego indeksu nie da się obliczyć w jednej iteracji, to po dostosowaniu wartości high i low w naszym wzorze wciąż na nowo obliczamy wartości indeksu.

Złożoność czasowa wyszukiwania interpolacji wynosi O(log log n), gdy wartości są równomiernie rozłożone. Jeśli wartości nie są równomiernie rozłożone, złożoność czasowa w najgorszym przypadku wynosi O(n), tak samo jak wyszukiwanie liniowe.

Wyszukiwanie interpolacyjne działa najlepiej na równomiernie rozłożonych, posortowanych tablicach. Podczas gdy wyszukiwanie binarne zaczyna się w środku i zawsze dzieli się na dwa, wyszukiwanie interpolacyjne oblicza prawdopodobną pozycję elementu i sprawdza indeks, co zwiększa prawdopodobieństwo znalezienia elementu w mniejszej liczbie iteracji.

Dlaczego warto używać Pythona do wyszukiwania?

Python jest bardzo czytelny i wydajny w porównaniu ze starszymi językami programowania, takimi jak Java, Fortran, C, C++ itp. Jedną z kluczowych zalet używania Pythona do implementacji algorytmów wyszukiwania jest to, że nie musisz się martwić o rzutowanie lub jawne wpisywanie.

W Pythonie większość algorytmów wyszukiwania, które omawialiśmy, będzie działać równie dobrze, jeśli szukamy Stringa. Należy pamiętać, że musimy wprowadzić zmiany w kodzie dla algorytmów, które używają elementu wyszukującego do obliczeń numerycznych, takich jak algorytm wyszukiwania interpolacyjnego.

Python jest również dobrym miejscem do rozpoczęcia pracy, jeśli chcesz porównać wydajność różnych algorytmów wyszukiwania dla swojego zbioru danych; budowanie prototypu w Pythonie jest łatwiejsze i szybsze, ponieważ możesz zrobić więcej za pomocą mniejszej liczby wierszy kodu.

Aby porównać wydajność zaimplementowanych przez nas algorytmów wyszukiwania względem zbioru danych, możemy skorzystać z biblioteki time w Pythonie:

import timestart = time.time()# call the function hereend = time.time()print(start-end)

Wnioski

Istnieje wiele możliwych sposobów wyszukiwania elementu wewnątrz kolekcji. W tym artykule podjęliśmy próbę omówienia kilku algorytmów wyszukiwania i ich implementacji w Pythonie.

Wybór algorytmu opiera się na danych, które musisz przeszukać; twojej tablicy wejściowej, którą we wszystkich naszych implementacjach nazwaliśmy lys.

• Jeśli chcesz przeszukać nieposortowaną tablicę lub znaleźć pierwsze wystąpienie szukanej zmiennej, najlepszą opcją jest wyszukiwanie liniowe.
• Jeśli chcesz przeszukać posortowaną tablicę, istnieje wiele opcji, z których najprostszą i najszybszą metodą jest wyszukiwanie binarne.
• Jeśli masz posortowaną tablicę, którą chcesz przeszukać bez użycia operatora podziału, możesz użyć wyszukiwania skokowego lub wyszukiwania Fibonacciego.
• Jeśli wiesz, że element, którego szukasz, prawdopodobnie będzie bliżej początku tablicy, możesz użyć wyszukiwania wykładniczego.
• Jeśli twoja posortowana tablica jest również równomiernie rozłożona, najszybszym i najbardziej wydajnym algorytmem wyszukiwania byłoby wyszukiwanie interpolacyjne.

Jeśli nie jesteś pewien, którego algorytmu użyć z posortowaną tablicą, po prostu wypróbuj każdy z nich wraz z biblioteką czasową Pythona i wybierz ten, który działa najlepiej z twoim zbiorem danych.