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
