Wpis będzie bardzo krótki, ponieważ algorytm wyszukiwania liniowego nie należy do zbyt skomplikowanych. Jego celem jest odnalezienie konkretnej wartość w kolekcji. Argument podany podczas wywołania funkcji (opartej zwykle na typach generycznych) będzie porównywany kolejno z każdym obiektem w kolekcji do momentu wyczerpania puli lub odnalezienia szukanej wartości. Jako wynik zwracany jest numer indeksu w kolekcji lub wartość null / nil w przypadku, gdy wartość nie zostanie odnaleziona.
Wyszukiwanie liniowe nie jest specjalnie wydajnym algorytmem (o czym będzie na końcu) i lepszą alternatywą w większości przypadków jest wyszukiwanie binarne. Pomimo tego wyszukiwanie liniowe stanowi bardzo dobre wprowadzenie w świat algorytmów.
Z racji tego, że od jakiegoś czasu grzebię trochę w Kotlinie, od tego wpisu przykłady algorytmów prezentować będę także w tym języku (obok Swifta). Do testowania kodu mam utworzony osobnym projekt w Android Studio, w którym umieszczam wszystkie swoje przykłady. Jeżeli chodzi o Swift’a, to najlepiej skorzystać z Playground.
Tak prezentuje się implementacja w poszczególnych językach:
Kotlin:
|
1 2 3 4 5 6 7 8 |
fun <T:Comparable<T>> linearSearch(collection: List<T>, searchValue: T): Int? { for ((index, value) in collection.withIndex()) { if (value == searchValue) return index } return null } |
Swift:
|
1 2 3 4 5 6 7 8 |
func linearSearch<T: Equatable>(collection: [T], searchValue: T) -> Int? { for (index, value) in collection.enumerated() where value == searchValue { return index } return nil } |
Sprawdźmy algorytm w praktyce. Załóżmy, że mamy kolekcję składającą się z obiektów typu String:
|
1 |
["Maciek", "Krzysztof", "Damian", "Erwin"] |
Chcemy sprawdzić, czy w kolekcji znajduje się imię „Darek”. Teraz widać gołym okiem, że nie znajdziemy dopasowania, ale wyobraźcie sobie, że nie macie podglądu i nie możecie sprawdzić co dokładnie i na jakiej pozycji znajduje się w kolekcji 🤓:
Kotlin:
|
1 2 3 4 5 |
val names = arrayListOf("Maciek", "Krzysztof", "Damian", "Erwin") var index = linearSearch(names, "Darek") println(index) // w konsoli wyświetli null |
Swift:
|
1 2 3 4 5 |
let names = ["Maciek", "Krzysztof", "Damian", "Erwin"] let index = linearSearch(collection: names, searchValue: "Darek") print(index) // w konsoli wyświetli nil |
W naszej kolekcji nie znajdziemy „Darka”, więc funkcja zwróci nam null / nil.
Sprawdźmy jednak jaki będzie wynik jeżeli będziemy chcieli odnaleźć imię „Erwin”:
Kotlin:
|
1 2 3 |
var index = linearSearch(names, "Erwin") println(index) // w konsoli wyświetli 3 |
Swift:
|
1 2 3 4 5 |
let index = linearSearch(collection: names, searchValue: "Erwin") if let index = index { print(index) // w konsoli wyświetli 3 } |
Tym razem udało się odnaleźć pasujący element i funkcja zwróciła nam wartość 3, czyli numer indeksu pod którym ukrywa się poszukiwany obiekt 🧐.
Wydajność
Na samy początku wspomniałem, że wyszukiwanie liniowe nie stanowi najbardziej optymalnego rozwiązania. A to dlatego, że w najgorszym wypadku musimy przeszukać całą kolekcję, aby odnaleźć właściwy obiekt lub dowiedzieć się, że w kolekcji go nie ma. Oczywiście może zdarzyć się tak, że poszukiwany obiekt będzie znajdował się na samy początku kolekcji, ale na to bym za bardzo nie liczył 😅.
Z powyższego wynika, że w najgorszym wypadku koszt wyszukiwana liniowego wynosi O(n), co oznacza, że będzie się on zwiększał proporcjonalnie do wzrostu liczby elementów w kolekcji. W najlepszym wypadku koszt będzie wynosił O(1), czyli będzie stały.
Słowo na drogę
I to by było na tyle. W następnym wpisie skupię się na algorytmie Rabin-Karp, który pozwala na przeszukiwanie obiektów typu String w poszukiwaniu określonego wzorca. Do następnego 😎.
