Hlavní navigace

Perličky (4)

Lukáš Zapletal 18. 10. 2002

Jsme tu opět s naším nepravidelným seriálem o programovacím jazyce Perl. Dnes se budeme nadále věnovat proměnným, zejména hashi. Nejprve si ale něco povíme o odkazech. Úplně na začátku si však něco přečtete o zajímavostech okolo šestky.

Novinky

Nejdříve se opět chvilku věnujme návrhu šestky. Díky tomu, že šestka bude mít vestavěné datové typy a jakousi „kontrolu při překladu“, rozšíří se tím pravděpodobně i kontexty: prázdný, pravdivostní, celočíselný, číselný, řetězcový, objektový a seznamový, přičemž seznamový bude mít jakési možné podkontexty, a to rozvinovací (flattening), nerozvinovací, líný a asociovaný. Díky tomu můžeme vytvořit funkci push takto: push($array, *@pushees);, což interpretu říká, že druhý parametr je rozvinovací seznam, takže funkce push bude přebírat dva nebo více parametrů.

V šestce bude možné nadefinovat proměnnou takto: my DoubleLinkedList $apples; což nebude znamenat, že se jedná o proměnnou typu dvojitě spojený seznam, ale o skalár, který hodláte takto používat a interpret při pokusu použít proměnnou jinak vypíše varování – tedy bude to jakýsi ASSERT.

Také tolik používané špičaté závorky již pro vstup ze souboru nebo standartního vstupu již nebudou potřeba. Stačí, aby měl kýžený objekt implementován iterátor (všechny třídy pro vstup/výstup tedy budou mít společného předka – iterátor) a programátor může jednoduše napsat: while ($stdin) { ... }. Objekt bude předávat dejme tomu řádek po řádku v řetězcovém nebo pomocí speciální proměnné $_ v logickém kontextu apod.

Toliko dnes o Perlu 6.0. Ještě než se ponoříme do zajímavé problematiky hashování, rád bych oznámil těm, kteří to ještě neví, že vyšel Perl 5.8. Blíže o něm a také o konferenci YAPC z Mnichova v příštím dílu.

Odkazy, zákazy a příkazy

Odkaz je obdoba ukazatele v C/C++. Představuje odkaz na objekt, skalár, pole, hash či typeglob. Výhoda použití odkazů je zřejmá. Odkaz je jen číslo, pokud tedy potřebujeme provádět manipulace či přesuny s nějakými většími objekty, je výhodnější použít odkaz, protože cílový prvek zůstavá na svém místě. V některých případech je použití odkazů zcela nutné.

Perl neumožňuje vytvářet vícerozměrná pole. Do polí však můžete uložit odkazy na jiná pole a tím si vlastně vícerozměrné pole simulovat. Dalším příkladem je předávání objektů (polí či hashů) do funkcí odkazem. U pole či hashe vlastně ani nemáte jinou možnost. Pokud byste se pokusili pole či hash předat přímo, Perl jej nejprve rozvine a poté zavolá. Jediná možnost je tedy použít odkaz. Protože se odkazy hojně používají, Perl má pro jejich vytváření speciální formy (tzv. konstrutory anonymních dat). Vše osvětlí následující ukázka (o funkcích v příštím dílu):

$skalar = "test";
@pole = ( 3, 4, 5 );

%hash = ( 1 => "11", 2 => "22" );

# vytvorime odkazy

$odkaz_skalar = \$skalar;
$odkaz_pole = \@pole;
$odkaz_hash = \%hash;

# pro vytvareni anonymnich dat

# ma Perl prislusne konstrukce
$odkaz_skalar = \do{ "test" };
$odkaz_pole = [ 3, 4, 5 ];

$odkaz_hash =  { 1 => "11", 2 => "22" };

# odkazy nyni obsahuji pouze informace

# o adrese a typu objektu
print "$odkaz_pole\n";
# nevypise pocet prvku ale neco jako
# ARRAY(0x1b054f4)

# musime totiz odkazy dereferencovat
# bud primo pomoci '$$' a '->'

print "$$odkaz_skalar\n";
print "$$odkaz_pole[0]\n";
print "$odkaz_hash->{1}\n";


# nebo prevest zpet na objekty
$skalar = ${ $odkaz_skalar };
@hash = @{ $odkaz_pole };
%hash = %{ $odkaz_hash };


# zjistit, zda se jedna o odkaz, muzeme
# jednoduse, funkce ref() vraci nepravdu,
# pokud to tak neni, a v opacnem pripade
# vraci retezec (SCALAR, ARRAY, HASH
# CODE, REF, GLOB nebo LVALUE), coz
# se samozrejme vyhodnoti na pravdu
if ( ref($odkaz_skalar) ) {
    if ( ref($odkaz_skalar) eq "SCALAR") {
        print "Je to skalar!\n";
    }
}


# Perl pri volani funkci pole a hash
# rozvine, nasledujici funkce by mela
# vypsat pocet prvku v poli
sub delka1 {
    @p = shift;
    return scalar(@p);
}


print delka1(@pole) . "\n";
# vypise '1' a ne '3', volani bychom
# cekali asi takto:
# > delka1( (1,2,3) );
# jenze skutecnst je trochu jina:

# > delka1( 1,2,3 );

# spravne reseni tohoto problemu
# jak jinak nez pomoci odkazu
sub delka2 {
    $rp = shift;
    return scalar( @{ $rp } );
}


print delka2(\@pole) . "\n";

Hash je tvůj kamarád

Snad každý programovací jazyk má v sobě zakomponovanou podporu pro tuto základní strukturu. Jak víme, pole má tu vlastnost, že pro výběr prvku je složitost algoritmu konstantní O(n) = c, ovšem přidávání či mazání z pole již tuto složitost nemá. O poli jsme se již bavili v předchozím dílu Perliček, nyní se zaměříme na hash. Nejprve ve zkratce, co je to vlastně hash.

Hash (neboli adresovatelná tabulka) je rozšířením pole. V poli přistupujete v konstantním čase k hledanému prvku pomocí indexu (čísla), kdežto u hashe můžete přistupovat pomocí nějakého obecného objektu (nejčasteji je to řetězec). Na ten se aplikuje tzv. hashovací funkce, jejíž výsledkem je odkaz na místo, kde se nachází kýžený prvek. Co je je však důležité, je to, že díky tomu, že hashovací funkce je jednoduchý algoritmus, který se provede jen jednou, je složitost vyhledávání v hashi řádově konstantní. Jaj je pěkně popsáno v [APP], Perl provádí při hashování zhruba toto:

char* key = "Testovací řetězec";
unsigned int hash = 0;

char *s = key;
int i = strlen(key);
while (i--)
    hash = hash * 33 + *s++;
// proměnná hash nyní obsahuje index
// pro nalezení prvku. perl však alokuje
// pro prvky jen určitou část paměti,

// proto nyní zajitíme, abychom se
// "vešli" do alokované části indexové
// množiny (která má velikost 2 na n)
index = hash & max_index;

int prvek = data[index];

Hashovací funkce musí vygenerovat na stejný vstup stejný index a dobrá hashovací funkce by měla pokrýt celou cílovou (indexovou) množinu. Může se také stát, že dva různé vstupy (řetězce) generují stejný index, címž vznikají kolize a Perl je řeší pomocí separátního řetězení. Zkrátka a dobře je nutno vědět, že kolize jsou v Perlu ošetřeny.

Indexová množina je při vytvoření hashe nastavena na 8 záznamů (toto se u vaší ditribuce může lišit). S přibývajícími daty Perl počítá prvky, z čehož jednoduše odvodí i faktor naplnění. Pokud překročí určitý práh, indexová množina se rozšíří na nejbližší mocninu 2 (tzn. 16, 32, 64…). Zkrátka a dobře je nutné si uvědomit, že pokud máte volnou paměť, můžete do hashe v Perlu vesele ukládat dál a dál.

Proč jsem se zde tak rozepsal? Hash je užitečný pomocník a je dobré ho poznat „zevnitř“. Ne nadarmo někteří programátoři tvrdí, že úplně nahrazuje značně komplikované vyhledávací stromy. Ovšem problematika řešení kolizí není zase tak zcela triviální a hash neumožňuje záskat některé informace (maximum, minimum atd.), což vyhledávací stromy umí. Nyní se ale vrhněme na hash v samotném Perlu. Použití je snadné a intuitivní:

# vytvorit hash jiz umime
%vek = ('Milan' => 19, 'Vilem' => 17, 'Jarda' => undef);


# vlozime prvek (pozor, nyni nepouzijeme %)
$vek{'Jarda'} = 22;

# nemusime u retezcu psat uvozovky
$vek{Lukas} = 23;

# smazeme Vilema

delete($vek{Vilem});

# pozor! toto nevede ke smazani Milana,
# pouze to nastavi hodnotu na undef
# (pamet je tedy stale zabrana)
$vek{Milan} = undef;

# pruchody hashi
while(($klic, $hodnota) = each(%hash)) {
    print "$klic = $hodnota\n";
}


# nebo druha moznost
foreach $klic (keys %hash) {
    print "$klic = $hash{$klic}\n";
}


# co takhle projit hash setrideny podle klicu?
foreach $klic (sort keys %hash) {
    print "$klic = $hash{$klic}\n";
}


print scalar(%vek);

Rád bych se pozastavil u posledního příkazu. Pokud bychom se snažili vytisknout hash, provede se vytištění všech dvojic klíč/hodnota těsně za sebou v nespecifikovaném pořadí, což je nám obvykle na dvě věci. Co je ale užitečné, je převést hash do skalárního kontextu a pak tuto hodnotu vytisknout. Tato hodnota totiž nyní obsahuje faktor naplnění, v tomto případě přibližně „4/8“, což nám říká, že byla alokována paměť pro 8 záznamů a 4 jsou využity. Tohoto však můžete také využít obráceně, hodláte-li do hashe vložit větší počet záznamů a vyhnout se tak neustálému rozšiřování:

# hodlam naplnit zhruba 1000 zaznamu
%vek = 1000;

# Perl si tedy hash 'roztahnul' na 1024
# a vy muzete vesele plnit

Nutno podotknout, že hash má Perl implementován skvěle a takovouto věc budete dělat zcela výjimečně nebo spíše vůbec. Práh pro rozšiřování totiž funguje bezchybně, rychlost vyhledávání v hashi je skvělá a kolizemi se nemusíte zabývat. Co více si přát?

Na závěr povídání o hashi bych se rád zmínil o funkci tie (resp. untie). Ta totiž umožňuje k hashi navázat modul, který musí implementovat jednoduché rozhraní. Od té chvíle již hash neobhospodařuje Perl, ale daná třída. Můžete potom vytvořit modul pro vyhledávání třeba v databázi, který lze navázat na hash. S jakou lehkostí lze pak ukládat do takto „připojené“ databáze, ani netřeba zdůrazňovat. A nemusíte se omezit na databáze. Co takhle ukládat nastavení aplikace do textového souboru? Nebo vyhledávat ve slovníku cizích slov? A rovnou přes internet! Jen do toho!

Použitá literatura:
[PLD] Kolektiv autorů: Perl documentation, distribuce Perlu
[PRP] L. Wall, T. Christiansen, J. Orwant: Programming Perl, 3rd edition, O`Reilly, ISBN 0–596–00027–8
[APP] S. Srinivasan: Advanced Perl Programming, O`Reilly, ISBN 1–56592–220–4
[PSA] D. N. Blank-Edelman: Perl for System Administration, O`Reilly, ISBN 1–56592–609–9
[PCB] T. Christiansen, N. Torkington: Perl Cookbook, O`Reilly, ISBN 1–56592–243–3

Našli jste v článku chybu?

18. 10. 2002 10:43

Lukas Zapletal (neregistrovaný)

Na stránce ttp://www.perl.com/pub/a/2002/10/01/hashes.html vyšel o hashování v Perlu vynikajicí článek. Doporučuji všem, kteří by chtěli vědět víc.

Podnikatel.cz: Přivýdělek u Airbnb nebo Uberu? Čekejte kontrolu

Přivýdělek u Airbnb nebo Uberu? Čekejte kontrolu

Vitalia.cz: Žloutenka v Brně: Nakaženo bylo 400 lidí

Žloutenka v Brně: Nakaženo bylo 400 lidí

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: Dárky v podnikání. Jak je uplatnit v daních?

Dárky v podnikání. Jak je uplatnit v daních?

Vitalia.cz: Jak koupit Mikuláše a nenaletět

Jak koupit Mikuláše a nenaletět

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

Vitalia.cz: Chtějí si léčit kvasinky. Lék je jen v Německu

Chtějí si léčit kvasinky. Lék je jen v Německu

DigiZone.cz: Flix TV má set-top box s HEVC

Flix TV má set-top box s HEVC

Vitalia.cz: 9 největších mýtů o mase

9 největších mýtů o mase

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Lupa.cz: Avast po spojení s AVG propustí 700 lidí

Avast po spojení s AVG propustí 700 lidí