Optimalizované vyhledávání v poli - princip děr

Algoritmy Vyhledávání Optimalizované vyhledávání v poli - princip děr

Funguje na principu děr. Z daného slova se vypočítá hash - číslo indikující index v poli. Pokud je na dané pozici díra (null) zapíše se daná hodnota. Pokud je již obsazeno, jde na další pozici do té doby, dokud není volná.

Pokud ve slovníku hledám, vypočítám hash slova. Najdu si jej v poli a zkontroluji, zda odpovídá hledanému slovu. Pokud ano, vrátí ho. Pokud ne podívá se na další pozici. A hledá do té doby, než narazí na díru.

Toto optimalizuje rychlost vyhledávání.

Příkladné použití - třída Slovník.

Zdrojový kód je v jazyce Java

public class Dictionary
{
        // pole pro ukládání slovíček
        String[][] dictionary;
        // kapacita pole
        int capacity;

        /**
         * Konstruktor slovníku. Vytvoří slovník o dané kapacitě.
         * @param capacity Velikost slovníku - počet slov, které se do něj vejdou
         */
        public Dictionary(int capacity)
        {
                this.capacity = capacity;
                dictionary = new String[capacity][2];
        }

        /**
         * Vrátí hash daného slova. Sečte jednotlivá písmena (jejich ascii hodnoty) číslo je v rozmezí kapacity - hash mod kapacita.
         * @param word Slovo, jehož hash chceme získat
         * @return Celočíselný Hash daného slova
         */
        private int hash(String word)
        {
                int hash = 0;
                for (char letter : word.toCharArray())
                {
                        hash += (int)letter;
                }
                return hash % capacity;
        }

        /**
         * Přidá slovo do slovníku. Pokud tam již není a pokud je ve slovníku místo.
         * @param czech České slovo
         * @param english Anglický ekvivalent
         * @return Úspěch při ukládání
         */
        public boolean addWord(String czech, String english)
        {
                int position = hash(czech);

                while (dictionary[position][0] != null)
                {
                        if ((dictionary[position][0]).equals(czech)) return false;

                        position = ++position % capacity;
                }

                dictionary[position][0] = czech;
                dictionary[position][1] = english;

                return true;
        }

        /**
         * Najde ve slovníku pomocí hashe daný ekvivalent slova. Pokud tam není vrátí "Not found" - "Nenalezeno"
         * @param czech České slovo, které chceme přeložit
         * @return Anglický ekvivalent zadaného slova
         */
        public String translate(String czech)
        {
                int position = hash(czech);

                while (dictionary[position][0] != null)
                {
                        if (dictionary[position][0].equals(czech)) return dictionary[position][1];

                        position = ++position % capacity;
                }

                return "Nenalezeno";
        }
}

Ukázka použití výše uvedené třídy:

Zdrojový kód je v jazyce Java

Dictionary dic = new Dictionary(5);
System.out.println("úspěch při vložení: " + dic.addWord("pes", "dog"));
System.out.println("úspěch při vložení: " + dic.addWord("kočka", "cat"));
System.out.println("úspěch při vložení: " + dic.addWord("kůň", "horse"));

System.out.println(dic.translate("kočka"));
System.out.println(dic.translate("kůň"));
System.out.println(dic.translate("davos"));

Pozn. aby byla zachována rychlost vyhledávání, je třeba vždy mít pole o dostatečné velikosti. Tzn. s dostatečným počtem volných děr. Tedy z uvedené kapacity pole by se mělo zaplnit maximálně kolem 75%. Pokud se použije více, bude málo děr, tím pádem při vyhledávání prvku, který v poli není nebo koliduje (má stejný hash a proto byl posunut) se bude muset prohledat větší část pole (pokud bude plné, tak i celé pole) a algoritmus pak nebude mít smysl.


 

  Aktivity (1)

Článek pro vás napsal David Jančík [sczdavos]
Avatar
Autor je vášnivý programátor v .NET C# a PHP. Nezná slovo "nelze", nebojí se zkoušet nepoznané a pronikat do nových technologií.

Jak se ti líbí článek?
Ještě nikdo nehodnotil, buď první!


 


Miniatura
Předchozí článek
Hashovací tabulka
Miniatura
Všechny články v sekci
Vyhledávací algoritmy

 

 

Komentáře

Avatar
Kit
Redaktor
Avatar
Kit:

Je dobré, když při hledání díry krok není roven jedné, protože to vytváří shluky bez děr. Používají se jiné konstanty nebo posloupnosti. Velikost kroku se také dá spočítat druhou hashovací funkcí. Sníží to riziko kolizí.

Odpovědět 17.10.2012 9:37
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
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 1 zpráv z 1.