V tej predstavitvi si bomo ogledali, kako delujejo slovarji, kako jih uporabljamo v programskih jezikih C# in Python, in kako so predstavljeni v računalniku.

Recimo, da imamo dan telefonski imenik. Kot podatke imamo dane naziv osebe in pa njegovo telefonsko številko. Te podatke moramo sedaj shraniti. Kako bi to storili, da bi do podatkov dostopali enostavno in hitro? Recimo, da si za rešitev tega problema izberemo slovarje. Pa si poglejmo, zakaj bi to v tem primeru bila najboljša rešitev.

Najprej si za lažjo predstavo oglejmo, kaj sploh slovarji so in kje jih uporabljamo.

Slovar je abstraktni podatkovni tip. Sestavljen je iz množice parov (ključ, vrednost) tako, da se vsak ključ v množici pojavi samo enkrat.

Osnovne operacije so:

• dodajanje parov (ključ, vrednost) v zbirko,
• odstranjevanje parov iz zbirke,
• sprememba ali zamenjava vrednosti v zbirki,
• iskanje vrednosti glede na ključ.

Kot bomo videli kasneje na konkretnih primerih, so možne tudi dodatne operacije.

Sedaj pa nazaj na naš primer telefonskega imenika. V slovar bi podatke shranili tako, da so ključi imena (skupaj s priimki), vrednosti, ki jim jih pripišemo, pa so njihove telefonske številke. Seveda moramo pri tem upoštevati, da morajo biti ključi enolično določeni in se ne smejo ponavljati, torej ne smemo imeti dveh oseb z istim imenom in priimkom.

Preden pa si pogledamo nekaj konkretnih problemov, najprej poglejmo, kako v Pythonu in C# izvedemo nekaj osnovnih ukazov nad slovarji.

Slovarje v Pythonu predstavlja razred dict .

Osnovne operacije so:

• prazen slovar naredimo z slovar = {}
• v slovar dodajamo z slovar[ključ] = vrednost
• iz slovarja brišemo z del slovar[ključ]
• vrednosti spreminjamo enako, kot v slovar dodajamo, le da je ključ že v slovarju, vrednost pa drugačna
• po slovarju iščemo z slovar[ključ] , ki vrne vrednost pri ključu

V filmčku na naslednji prosojnici si lahko ogledate nekaj več metod in operacij.

V C# so slovarji predstavljeni z razredom Hashtable.

Osnovne operacije so:

• slovar ustvarimo z Hashtable h = new Hashtable()
• za dodajanje h.Add(ključ, vrednost) ,
• za brisanje h.Remove(ključ) ,
• za prirejanje uporabljamo kar obliko h[ključ]=vrednost
• za iskanje s pomočjo ključa pa samo h[ključ] , ki vrne vrednost pri tem ključu

Če uporabimo using System.Collections , si lahko nekoliko olajšamo delo, saj nam pred vsak ukaz za slovar ni potrebno pisati System.Collections . Za primer, namesto, da pišemo System.Collections.Hashtable h , pišemo samo Hashtable h .

Nekaj primerov ostalih operacij, metod in lastnosti pa najdete na naslednji prosojnici.

Tukaj je predstavljena koda v C#, s katero naredimo slovar, nato pa na njem izvedemo nekaj najpogostejših operacij. Koda je razdeljena na tri dele, vendar se ti deli navzujejo eden na drugega. Pod vsakim delom kode je prikazan rezultat, ki ga program izpiše na konzolo.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace hashtable
{
    class Program
    {
        /// <summary>
        /// metoda naredi nov slovar z elementi a 0, b 0 , c 0
        /// </summary>
        /// <returns></returns>
        static Hashtable NovSlovar()
        {
            //najprej naredimo nov slovar
            Hashtable h = new Hashtable();
            //potem pa mu dodamo elemente
            //prvi način je, da v oklepajih podamo ključ in mu pripredimo vrednost
            h['a'] = 0;
            //drugi način pa je z metodo Add
            h.Add('b', 0);
            h.Add('c', 0);
            //na koncu vrnemo slovar
            return h;
        }
        static void Main(string[] args)
        {
            //naredimo nov slovar s pomočjo metode NovSlovar
            Hashtable hashtable = NovSlovar();
            //in ga izpišemo po parih ključ, vrednost
            Console.WriteLine("Slovar:");
            foreach (DictionaryEntry entry in hashtable)
            {
                Console.WriteLine(entry.Key + " " + entry.Value);
            }
            Console.WriteLine("");

            //v slovar poskusimo dodati element z že obstoječim ključem
            Console.WriteLine("V slovar dodamo element s ključem 'c' in vrednostjo 1.");
            try
            {
                //program vrže izjemo
                hashtable.Add('c', 1);
            }
            catch
            {
                //ujamemo izjemo
                Console.WriteLine("Če želimo v slovar dodati element z že obstoječim ključem, nam program vrže izjemo.");
            }
            Console.WriteLine("");

            //elementu v seznamu spremenimo vrednost
            Console.WriteLine("Slovarju pri ključu 'a' spremenimo vrednost v 1.");
            //to naredimo tako, da v oklepajih podamo ključ in mu priredimo novo vrednost
            hashtable['a'] = 1;
            //še enkrat izpišemo slovar
            Console.WriteLine("Slovar:");
            foreach (DictionaryEntry entry in hashtable)
            {
                Console.WriteLine(entry.Key + " " + entry.Value);
            }
            Console.WriteLine("");

izpis na konzoli za ta del kode

             //z lastnostjo Count preštejemo elemente v slovarju
            int dol = hashtable.Count;
            Console.WriteLine("Vseh elementov v slovarju je : " + dol.ToString());
            Console.WriteLine("");

            //lastnost Keys in Values nam vrneta tabelo ključev in tabelo vrednosti
            ICollection kl = hashtable.Keys;
            ICollection vr = hashtable.Values;
            //te nato izpišemo
            Console.WriteLine("Vsi ključi:");
            foreach (char kljuc in kl)
            {
                Console.WriteLine(kljuc.ToString() + " ");
            }
            Console.WriteLine("Vse vrednosti:");
            foreach (int vrednost in vr)
            {
                Console.WriteLine(vrednost + " ");
            }
            Console.WriteLine("");

            //z metodami Cointains, CointainsKey in CointainsValue preverimo, če so dane vrednosti v slovarju, ključ v slovarju ali pa vrednost v slovarju
            Console.WriteLine("Preverimo če slovar vsebuje 'a' : " + hashtable.Contains('a'));
            Console.WriteLine("Preverimo če slovar vsebuje ključ 'a' : " +hashtable.ContainsKey('a'));
            Console.WriteLine("Preverimo če slovar vsebuje vrednost 'a' : " +hashtable.ContainsValue('a'));
            Console.WriteLine("");

izpis na konzoli za ta del kode

            //z metodami Cointains, CointainsKey in CointainsValue preverimo, če so dane vrednosti v slovarju, ključ v slovarju ali pa vrednost v slovarju
            Console.WriteLine("Preverimo če slovar vsebuje 'a' : " + hashtable.Contains('a'));
            Console.WriteLine("Preverimo če slovar vsebuje ključ 'a' : " +hashtable.ContainsKey('a'));
            Console.WriteLine("Preverimo če slovar vsebuje vrednost 'a' : " +hashtable.ContainsValue('a'));
            Console.WriteLine("");

            //z metodo remove odstranimo element iz slovarja, metodi podamo ključ
            hashtable.Remove('a');
            Console.WriteLine("Iz slovarja izbrišemo element s ključem 'a'.");
            //izpišemo slovar
            Console.WriteLine("Slovar:");
            foreach (DictionaryEntry entry in hashtable)
            {
                Console.WriteLine(entry.Key + " " + entry.Value);
            }
            Console.WriteLine("");

            //z metodo Clear izbrišemo vse elemente v slovarju
            Console.WriteLine("Slovarju izbrišemo vse elemente.");
            hashtable.Clear();
            //slovar izpišemo
            Console.WriteLine("Slovar:");
            foreach (DictionaryEntry entry in hashtable)
            {
                Console.WriteLine(entry.Key + " " + entry.Value);
            }

            Console.ReadKey();
        }
    }
}

izpis na konzoli za ta del kode

Tabela ukazov za C# in Python, ki na slovarjih izvedejo podobne operacije:

tabela ukazov za C# in Python

Slovarji so v programiranju zelo uporabna podatkovna struktura in so za določene primere veliko bolj uporabni kot seznami.

Problem:

Denimo da imamo dan niz "Kako delujejo slovarji.". Zanima nas kolikokrat v tem nizu ,nastopa posamezen znak. Želimo dobiti izpis v obliki:

k 2
a 2
...

Pa si najprej poglejmo kako bi ta problem rešili s pomočjo seznamov:

• V Pythonu vrednosti hranimo v seznamu dvojic (znak, št. ponovitev). Dvojico v seznam dodamo, če dvojice s tem znakom v njem še ni. Če pa dvojica s tem znakom že obstaja, povečamo število ponovitev za 1.
• Podobno naredimo tudi v C#, le da pare shranjujemo v seznamu nizov "znak št.ponovitev". Tukaj imamo še dodatne težave s tem, da moramo iz niza vzeti število ponovitev, ga pretvoriti iz niza v število, ga povečati za 1 in nato shraniti nazaj v niz, na koncu pa še nazaj v seznam.
• Alternativna rešitev s seznami bi bila tudi ta, da bi ključe hranili v eni tabeli vrednosti pa v drugi. Ker pa ta rešitev ni zanesljiva, saj se ob dodajanju novih elementov v tabele lahko indeksi zamešajo, zato sem raje uporabila zgoraj opisani rešitvi.

Na naslednjih prosojnicah si lahko ogledate konkretne programe, ki rešijo problem s seznamom. Problem je najprej rešen v Pythonu, potem pa še v C#.

def prestejZnakeSez(niz):
    '''v metodi preštejemo število posameznih znakov v nizu,
    podatke pa v dvojicah znak, števec hranimo v seznamu'''
    #naredimo seznam
    sez = []
    #se sprehodimo po elementih v nizu
    for el in niz:
        #spremenljivka, ki pove, če je znak že v seznamu
        vSez = False
        #potem pa gremo še z indeksi po dolžini seznama
        for i in range(len(sez)):
            #shranimo dvojico
            k,v = sez[i]
            #preverimo, če je znak že v seznamu
            if k == el:
                #če je števec povečamo, in dvojico shranimo nazaj
                sez[i] = (k, v+1)
                #znak je že v seznamu
                vSez = True
                break
        #če pa znaka še ni v seznamu
        if not vSez:
            #mu dodamo novo dvojico znak, števec
            sez.append((el, 1))
    #vrnemo seznam
    return sez

s1 = prestejZnakeSez('Riba reže raci rep.')
for a,b in s1:
    print(str(a) + ' ' + str(b))

rezultat metode za dani niz

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace znaki
{
    class Program
    {
        /// <summary>
        /// za dan niz ustvarimo slovar, v katerem shranimo kolikorat se je posamezni
        /// znak pojavil v nizu
        /// </summary>
        /// <param name="niz"></param>
        /// <returns></returns>
public static List<string> znakiSez(string niz)
        {
            //naredimo nov seznam, ki bo vseboval nize
            List<string> sez = new List<string>();

            //najprej se sprehodimo po znakih v nizu
            foreach (char el in niz)
            {
                //nastavimo spremenljivko, ki bo povedala, če je znak že v seznamu
                bool vSez = false;
                //nato pa se z indeksi sprehodimo še čez seznam
                for (int i = 0; i < sez.Count && !vSez; i++)
                {
                    //niz razdelimo glede na vejico
                    string[] z = sez[i].Split(',');
                    //če je znak enak elementu je ta že v seznamu
                    if (z[0] == el.ToString())
                    {
                        //potem spremenimo niz tako, da števec, ki je drugi element v seznamu, povečamo za 1
                        sez[i] = z[0] + "," + (int.Parse(z[1]) + 1);
                        //in element je že v seznamu
                        vSez = true;
                        break;
                    }
                }
                //če pa ga v seznamu še ni, ga dodamo
                if (!vSez)
                {
                    //niz je sestavljen iz znaka, vejice in števca
                    sez.Add(el + ",1");
                }

            }
            //na koncu seznam vrnemo
            return sez;
        }
        static void Main(string[] args)
        {

            //za nek niz pokličemo metodo, ki prešteje znake v nizu
            string niz = "uizzrre6rd7678909hivgcrs44d7";

            //naredimo seznam in pokličemo metodo
            List<string> sez = znakiSez(niz);
            //nato pa seznam izpišemo na konzolo
            Console.WriteLine("Znak v nizu : kolikokrat nastopa:");
            foreach (string entry in sez)
            {
                string[] r = entry.Split(',');
                Console.WriteLine(r[0] + ' ' + r[1]);
            }
            Console.ReadKey();
        }
    }
}

Sedaj pa si poglejmo, kakšna je ideja za program, če se rešitve lotimo s slovarji.

• V obeh jezikih naredimo podobno. Naredimo slovar, potem pa se z zanko sprehodimo po znakih v nizu. Za vsak znak preverimo, če je že v slovarju. Če je, njegovo vrednost povečamo za eno, če pa ga v slovarju še ni, ga dodamo v slovar kot ključ ki mu pripada vrednost 1. Na koncu vrnemo slovar.

Kot vidimo, imamo tukaj veliko manj dela s shranjevanjem podatkov. Tako je rešitev boljša in hitrejša, če podatke shranimo v slovar.

Seznami pa so boljša rešitev takrat, ko imamo za ključe zaporedje števil, in se nam ni potrebno posebej ukvarjati s ključi, ampak v seznam vnašamo samo vrednosti. Ključe v tem primeru predstavljajo indeksi.

Na naslednjih prosojnicah si lahko ogledate še rešitev problema s slovarji, najprej v Pythonu, potem pa še v C#.

def prestejZnake(niz):
    '''v metodi preštejemo število posameznih znakov v nizu,
    ter podatke shranimo v slovar'''
    #prazen slovar
    znak = {}
    #z zanko se sprehodimo po elementih niza
    for el in niz:
        #če je element že v slovarju vrednost povečamo za 1
        if el in znak:
            znak[el] += 1
        #če pa elementa še ni v slovarju ga dodamo in mu vrednost nastavimo na 1
        else:
            znak[el] = 1
    #vrnemo slovar
    return znak

s2 = prestejZnake('Riba reže raci rep.')
for c,d in s2.items():
    print(str(c) + ' ' + str(d))

rezultat metode za dani niz

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace znaki
{
    class Program
    {
        /// <summary>
        /// za dan niz ustvarimo slovar, v katerem shranimo kolikorat se je posamezni
        /// znak pojavil v nizu
        /// </summary>
        /// <param name="niz"></param>
        /// <returns></returns>
        public static Hashtable znaki(string niz)
        {
            //naredimo nov slovar
            Hashtable z = new Hashtable();
            //sprehodimo se po nizu
            foreach (char el in niz)
            {
                //če znaka še ni v slovarju, ga dodamo in pripišemo vrednost 1
                if (!z.ContainsKey(el))
                {
                    z[el] = 1;
                }
                //če pa je znak že v slovarju
                else
                {
                    //si najprej zapolnimo njegovo vrednost
                    int vr = (int)z[el];
                    //jo povečamo za 1
                    vr++;
                    //in shranimo nazaj k pripadajočem ključu
                    z[el] = vr;
                }
            }
            //vrnemo slovar
            return z;
        }

        static void Main(string[] args)
        {
            //za nek niz pokličemo metodo, ki prešteje znake v nizu
            string niz = "uizzrre6rd7678909hivgcrs44d7";
            Hashtable zn = znaki(niz);
            //slovar, ki ga dobimo izpišemo na konzolo
            Console.WriteLine("Znak v nizu : kolikokrat nastopa:");
            foreach (DictionaryEntry entry in zn)
            {
                Console.WriteLine(entry.Key + " " + entry.Value);
            }
            Console.ReadKey();
        }
    }
}

Slovarje lahko hranimo na več načinov. Recimo kot iskalno dvojiško drevo, verižni seznam ali najpogosteje, z razpršeno tabelo.

V razpršeni tabeli podatke hranimo tako, da za vsak ključ s pomočjo posebne funkcije izračunamo indeks. Pod ta indeks, v tabelo v ozadju, shranimo vrednost.

Časovna zahtevnost:

V povprečju razpršena tabela porabi časa za shranjevanje vrednosti, za iskanje vrednosti, za vstavljanje v tabelo z vrednostmi in za brisanje iz tabele z vrednostmi, pri čemer je velikost tabele, pa število shranjenih vrednosti. Zaradi hitrega iskanja je v računalništvu razpršena tabela velikokrat uporabljena za shranjevanje podatkov.

Za primerjavo si poglejmo koliko za te operacije porabimo v uravnoteženem iskalnem dvojiškem drevesu. Za iskanje, vstavljanje in brisanje vrednosti porabimo .

Problemi se pojavijo, ko za več ključev funkcija izračuna enake indekse. Ker v tabeli pod tem indeksom že hranimo vrednost, ne moremo vanjo shraniti nove vrednosti, saj bi staro izgubili. Zato poznamo različne algoritme za rešitev takih težav.

Dva primera takih algoritmov si lahko ogledate na naslednjih dveh prosojnicah.

S tem algoritmom poskušamo za dan ključ poiskati prvi nezasedeni indeks v tabeli. Ko ta indeks najdemo, vanj shranimo vrednost. V taki tabeli nato nov indkes iščemo s pomočjo spodnje enačbe:

novIndeks = (začetnaVrednost + dolžina) % dolžinaTabele

Pri tem je novIndeks iskani indeks, zacVrednost je prvotni izračunan indeks, dolžina je dana dolžina intervala, dolžinaTabele pa dolžina tabele v katero shranjujemo vrednosti.

Pa si poglejmo kako to poteka na spodnji sliki. Najprej vzamemo osebo John Smith in zanj s hash funkcijo izračunamo indeks 152. Ker pod tem indeksom še ni shranjene vrednosti, jo zapolnimo z našo. Sedaj vzamemo osebo Lisa Smith in naredimo enako. Tudi tukaj je indeks 001 prazen. Postopek poteka enako še za osebo Sam Doe. Sedaj pa vzamemo osebo Sandra Dee za katero pa ponovno naračunamo indeks 152. Ker smo pod ta indeks že prej shranili vrednost osebe John Smith, moramo sedaj poiskati nov prazen indeks. Tega izračunamo po zgoraj razloženi enačbi. Novi izračunani indeks je sedaj 153 in je prazen, zato lahko vanj shranimo vrednost. Pri naslednji osebi Ted Baker ponovno izračunamo indeks, ki je že zaseden in sicer indeks 153v katerega smo v prejšnjem koraku shranili vrednost za osebo Sandra Dee. Tudi tukaj nov indeks računamo po zgornji enačbi in pravi je že naslednji 154.

primer shranjevanja vrednosti za linearno poskušanje

Vir slike: Razpršene tabele

Problem z linearnim poskušanjem je ta, da če je hash funkcija slaba, torej za več različnih ključev izračuna enak indeks. V takem primeru moramo nato izračunati veliko novih indeksov. Pravi problem pa se pojavi, ko iščemo tako vrednost, saj po formuli še vedno naračunamo prvotni indeks, nato pa nove indekse računamo toliko časa, dokler ne pridemo do prave vrednosti.

V tem algoritmu v tabelo, če več ključev kaže na isti indeks,shranimo verižni seznam. V ta verižni seznam shranimo po vrsti vrednosti, ki pripadajo ključem z istim indeksom. Tako se tudi rešimo težav glede večanja tabele.

Vrednosti tukaj pa dobimo tako, da najprej izračunamo indeks pod katerim je shranjena vrednost v tabeli in se nato sprehodimo po verižnem seznamu, dokler ne najdemo pravega ključa, ob katerem je shranjena iskana vrednost.

Pa še tukaj poglejmo kako shranjujemo vrednosti na spodnji sliki. Primer je enak prejšnjemu. Najprej izračunamo indeks za osebo John Smith. Ta indeks je 152, ker pod tem indeksom še ni nič shranjeno, vanj shranimo vozel z vrednostjo, ki kaže na None. Enako naredimo še za osebi Lisa Smith in Sam Doe, saj tudi njuna dva indeksa še nista zasedena. Zopet pa se zaplete pri osebi Sandra Dee, saj hash funkcija tudi pri njej naračuna indeks 152. Tudi za to osebo naredimo vozel s pripadajočo vrednostjo, ki kaže na None. Spremenimo pa kam kaže zadnji vozel shranjen pod tem indeksom. To je v tem primeru vozel za osebo John Smith in ta sedaj kaže na novo narejeni vozel. Tako dobimo verižni seznam shranjen pod danim indeksom. Za osebo Ted Baker pa naračunamo indeks 153, ki pa je v tem primeru prazen, zato tudi tukaj v tabelo pod ta indeks shranimo vozel z vrednostjo, ki kaže na None.

primer shranjevanja vrednosti pri veriženju

Vir slike: Razpršene tabele

Tudi tukaj se pojavi problem pri slabi hash funkciji, ki za veliko ključev naračuna enak indeks, saj so tako verižni seznami lahko zelo dolgi. Tako pri iskanju določene vrednosti lahko porabimo veliko časa, saj moramo pregledati cel verižni seznam.

Razpršene tabele uporabljamo predvsem zaradi hitrega iskanja vrednosti. Poglejmo pa si še nekaj drugih uporab:

• Ena uporaba je recimo kodiranje in dekodiranje. Če imamo recimo za znake dane različne kode, in hočemo te shraniti tako, da jih bomo najlažje uporabili. Naredimo torej slovar, ki ima za ključe znake, za vrednosti pa njihove kode. Hkrati pa lahko naredimo tudi slovar za dekodiranje, pri tem da so sedaj kode ključi, vrednosti pa znaki. Ta zapis je primeren, saj do kod dostopamo hitro in brez večjih problemov.
• Uporaba, ki smo jo že prikazali je telefonski imenik, v slovarje pa lahko shranimo tudi recimo poštne številke, kjer so te ključi, vrednost pa je kraj, ki spada k tej poštni številki.
• Ena izmed možnosti bi bila tudi hranitev dejanskega slovarja, kjer bi bili ključi besede, vrednosti pa razlage za posamezne besede.

• Python slovarji

• C# slovarji

• Razpršene tabele