Sekvenční vyhledávání

Algoritmy Vyhledávání Sekvenční vyhledávání

Tento algoritmus představuje nejjednodušší a prakticky jediný způsob jak hledat v nesetříděné lineární datové struktuře (pole či seznamu). Jedná se o způsob, který nejspíš použil každý z nás, když se snažil něco rychle najít například v poli. Na závěr ukáži jak tento pomalý způsob alespoň trochu urychlit.

Když nemáme pole setříděné, stěží najdeme jiný způsob než jít a prvky postupně procházet (nejčastěji od začátku do konce) a porovnávat s hledanou hodnou. Této metodě se říká sekvenční vyhledávání (anglicky sequential search), někdy také lineární vyhledávání nebo naivní vyhledávání.

Časová složitost

Co se týče časové složitosti této metody, asi vás nepřekvapí, že není vůbec hezká. Pokaždé musí dojít minimálně k jednomu porovnání (v případě, že hned první prvek je ten, který hledáme) a maximálně dojde k n porovnání (n je počet prvků v naší struktuře), průměrný počet srovnání je poté kolem n/2. Časová složitost je tedy lineární. Nikdy nepřekročí ani dolní ani horní hranici (nikdy nebude rychlejší než 1 a nikdy nebude pomalejší než n), označíme ji tedy Θ(n), chcete-li O(n).

Implementace

K algoritmu budeme potřebovat lineární datovou strukturu (pole), hledaný prvek (x) a velikost datové struktury. Pojďme se tedy podívat na kód, který je napsaný v jazyce C# (v ostatních jazycích by byl velmi podobný).

/* v pripade, ze vas jazyk nedokaze urcit velikost pole, bude treba predat jeste parametr n typu int, ktery bude urcovat velikost pole */
public static int sekvencniVyhledavani(int[] pole, int x)
{
        for (int i = 0; i < pole.Length; i++)
        {
                if (pole[i] == x)
                        return i; // vraci index, pokud jsme hledany prvek nalezli
        }
        return -1; // pri neuspechu vracime -1
}

Kód asi není třeba příliš popisovat, je velice jednoduchý. Máme jeden cyklus a v něm jednu podmínku. Vrací se index nalezeného čísla (v případě úspěchu) nebo -1 (v případě neúspěchu). Algoritmus se dá samozřejmě upravit tak, aby vracel například pravdivostní hodnoty nebo to co zrovna potřebujeme.

Optimalizace

Na začátku jsem zmiňoval jisté vylepšení, které vám nyní ukáži. Když se podíváte na kód výše, zjistíte, že v podstatě dvakrát používáte operaci porovnání - ta první kontroluje, abychom nepřesáhli velikost pole a druhá zjišťuje, zdali se aktuální prvek rovná x. Nyní tedy zkusíme odstranit jednu podmínku jednoduchým trikem. Naše pole vytvoříme o jeden prvek větší a jako poslední prvek dáme hodnotu, kterou hledáme (občas se tato hodnota označuje jako zarážka). Pak tedy cyklus vždy nalezne hledaný prvek a bude jen zapotřebí zjistit, zda byl prvek nalezen ještě před zarážkou. Tomuto algoritmu se říká anglicky sequential search sentinel (česky by se to dalo přeložit jako sekvenční vyhledávání se zarážkou). Kód je tentokrát ještě jednodušší.

// opet muze byt potreba vlozit i velikost pole (n), pokud pracujete v jazyce, ktery ji neumi zjistit
public static int sekvencniVyhledavaniZarazka(int[] pole, int x)
{
        // vkladame hledany prvek na konec pole, pole musi byt o jeden prvek vetsi!
        pole[pole.Length - 1] = x;

        int i = 0;
        while (true)
        {
                if (pole[i] == x)
                        return i; // vraci index nalezeneho prvku
                i++;
        }
}

Rychlost tohoto algoritmu pocítíte, až budete vyhledávat ve velkém množství prvků (v rámci statisíců). Stále se však jedná o pomalé řešení (na poměry jiných vyhledávacích algoritmů).

Samozřejmě připomenu, že v místě volání funkce/metody bude třeba zjistit, kde jsme prvek našli, a to tím, že zjistíme jednoduchou podmínkou, jestli se vrácený index nerovná velikosti pole - 1.

Na závěr bych chtěl říci, že tento algoritmus se hodí jen na malé datové struktury a pro občasné používání. Vždy si tedy promyslete, jestli se vám nevyplatí pole nejdříve setřídit a poté použít například binární vyhledávání anebo použít jeden z vyhledávacích stromů.

P. S. Jak jste možná poznali, tento algoritmus je téměř nepoužitelný, když chceme do struktury vkládat nebo odebírat prvky (zvlášť u jazyků, které neumožňující rozšiřovat velikost pole), v těchto případech rozhodně využijte stromů.


 

  Aktivity (2)

Článek pro vás napsal Petr Valigura
Avatar
Autor se věnuje programování v různých (i funkcionálních) jazycích, nejčastěji však používá .NET a C#. Baví ho zajímavé algoritmy a věci kolem softwaru obecně.

Jak se ti líbí článek?
Celkem (3 hlasů) :
55555


 


Miniatura
Všechny články v sekci
Vyhledávací algoritmy
Miniatura
Následující článek
Binární vyhledávání

 

 

Komentáře

Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Díky za doplnění sbírky algoritmů, hezký článek na jednoduché téma, které tu chybělo :)

Odpovědět  +3 27. července 10:50
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Petr Valigura
Redaktor
Avatar
Odpovídá na David Čápka
Petr Valigura:

Jsem rád, že můžu znalosti ze školy předat takto dál :) ... už mám rozepsané B-stromy, takže sbírku algoritmů se budu snažit i nadále doplňovat :)

Odpovědět  +3 27. července 13:38
Občas je to tady dobrá klauniáda...
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 2 zpráv z 2.