ARCHIV

Perl (48) - Libovolně složité datové struktury

Ukážeme si příklady datových struktur, které lze použít k ukládání dat se složitými vzájemnými vztahy. Popíšeme také způsob prohlížení těchto struktur vhodný pro ladění.

18.12.2006 06:00 | Jiří Václavík | Články autora | přečteno 18881×

Dvojrozměrné struktury, kteréžto byly tématem minulého dílu, jsou mezistupněm k rozsáhlým datovým stromům. Ty poskytují způsob, kterým se lze poměrně snadno vypořádat se složitými vztahy mezi daty. Složité datové struktury mohou být vytvořeny například jako dlouhý propojený řetězec odkazů a až daleko na jeho konci jsou skalární hodnoty - tedy ta konkrétní data, kvůli kterým celá struktura existuje. Odkazy budou jsou v datové struktuře pouze proto, aby vytvořily v té změti dat nějaký systém.

Protože teorii již máme v podstatě kompletně zvládnutou, ukážeme si příklad. Vytvoříme si datovou strukturu, která bude reprezentovat atlas světa. To je velice názorný příklad. Právě atlas totiž obsahuje data setříděná postupně podle řady kritérií, tedy přesně to, na co chceme ukázat.

Nejprve se musíme rozhodnout, která data budeme uchovávat. Rozhodněme se pro informace o jednotlivých státech světa. Každý stát bude zařazen do nějaké části světa (Evropa, Asie apod.). Samotné informace budou obsahovat rozlohu, počet obyvatel, jméno hlavního města a seznam jmen dalších větších měst.

Vše budeme řešit pomocí anonymních dat. Budeme mít jedinou pojmenovanou proměnnou. Pomocí ní musíme být schopni vytisknout jakoukoliv informaci, obsaženou v naší datové struktuře.

Začneme tím, že vytvoříme hash nejvyšší úrovně. Jeho prvky budou tvořeny dvojicí hodnot - klíčem bude jméno části světa a prvkem odkaz na hash, ve kterém bude seznam států.

%svet = (
    "evropa" => { ... },
    "asie" => { ... },
    "jizni amerika" => { ... },
    "severni amerika" => { ... },
    "australie" => { ... },
    "antarktida" => { ... },
    "afrika" => { ... }

Jak už bylo řečeno, v každém z těchto anonymních hashů bude seznam států.

%svet = (
    "evropa" => {
        "albanie" => { ... },
        "andorra" => { ... },
        "belgie" => { ... },
        "belorusko" => { ... },
        "bosna" => { ... },
        ...
    },
    ...
);

Každá hodnota prvku je opět odkazem na hash. Tento hash už bude obsahovat konkrétní informace.

%svet = (
    "evropa" => {
          ...
        "ceska republika" => {
            "rozloha" => 79_000,
            "lidi" => 10_250_000,
            "hlavni mesto" => "Praha",
            "dalsi mesta" => [ ... ]
        },
        ...
    },
    ...
);

Vnoření ale půjde ještě hlouběji. Do prvku s klíčem "dalsi mesta" přiřadíme odkaz na seznam měst.

%svet = (
    "evropa" => {
        "ceska republika" => {
            "rozloha" => 79_000,
            "lidi" => 10_250_000,
            "hlavni mesto" => "Praha",
            "dalsi mesta" => [
                "Brno",
                "Ostrava",
                "Ceske Budejovice",
                "Plzen"
            ]
        },
        ...
    },
    ...
);

A tak můžeme pokračovat dále. Ke všemu bychom stále přistupovali pomocí jediné proměnné. Otázka je, jak moc by byl další postup vhodný. Struktura by teoreticky mohla obsahovat například ještě informace o jednotlivých městech apod. Avšak je třeba se s tímto umět ve vhodnou chvíli zastavit a zamyslet se, zda by nebylo lepší řešit problém nějak jinak. Leckdo by namítl, že ani námi demonstrovanou strukturu by přes hash neřešil. V mnoha případech bude například než struktura vhodnější databáze, které si podrobně rozebereme někdy v budoucnu.

Teď již ale zabíháme někam úplně jinam. Smysl předchozího odstavce měl být ten, že rozsáhlou datovou strukturu je dobré použít, pokud je to "rozumné". To znamená, že s dobře navrženou datovou strukturou by se mělo nechat pohodlně pracovat a měla by obsahovat opravdu jen ty informace, pro které je určena. Do jisté míry také záleží na zkušenostech a vkusu programátora.

Tak čí onak, metoda vytváření struktury by měla být z výše uvedeného již jasná. Nyní se krátce podívejme, jak se s takovou strukturou pracuje.

Kontinenty jsou klíči proměnné %svet. Použijeme funkci keys k jejich vytisknutí.

Půjdeme o úroveň dále a vytiskneme seznam evropských států. Na tento seznam ukazuje proměnná $svet{"evropa"}.

Teď zkusíme nějaký konkrétní údaj.

S těmito údaji lze operovat stejně jako s jakoukoliv jinou skalární hodnotou. Poměr počtu lidí České repuliky k její rozloze získáme takto.

Dále vypíšeme seznam měst České republiky. Nesmíme zapomenout, že Praha jako hlavní město je ve zvláštním prvku. Dále musíme myslet na to, že když tiskneme ostatní města, jde o seznam, a tudíž musíme použít jako předponu zavináč.

print "Mesta Ceske republiky: ", $svet{"evropa"}{"ceska republika"}{"hlavni mesto"},
@{$svet{"evropa"}{"ceska republika"}{"dalsi mesta"}};

Teď uděláme podobnou věc, ale vytiskneme hned všechna evropská města, která máme zaznamenaná. Použijeme cyklus foreach a v každé jeho iteraci přiřadíme do promněnné $_ jeden odkaz na hash obsahující informace o konkrétním evropském státě. Tento odkaz v tělě cyklu dereferencujeme. Všimněme si, jak je odkaz dereferencován. Je totiž větví celé struktury %svet. Název státu nás nezajímá, proto můžeme použít pro vytvoření pole předávaného cyklu funkci values.

print "Seznam evropskych mest: ";
foreach (values %{$svet{"evropa"}}){
    print $_->{"hlavni mesto"};  #tiskne hlavní město
    print @{$_->{"dalsi mesta"}};#tiskne další města
}

Poslední příklad vylepšíme a budeme tisknout i název státu, ve kterém města leží. V předchozím příkladu nás název státu nezajímal. Teď už ale ano. Protože název státu uložen jako klíč hashe, musíme změnit pole předávané cyklu foreach. values vyměníme za keys. Teď už $_ nebude přímo odkazem na hash s informacemi o konkrétním státě, ale pouze řetězec obsahující název státu. Musíme proto dereferencovat už od nejvyšší úrovně proměnné %svet.

print "Seznam evropskych mest podle statu: ";
foreach (keys %{$svet{"evropa"}}){
    print "$_: ";                               #tiskne název státu
    print $svet{"evropa"}{$_}{"hlavni mesto"};  #tiskne hlavní město
    print @{$svet{"evropa"}{$_}{"dalsi mesta"}};#tiskne další města
    print "\n";
}

Nejen získávat je třeba informace. Je nutné občas aktualizovat - přidávat, mazat nebo editovat. Občas vypukne válka a nějaké státy zanikají a jiné vznikají. Přidáme si tedy nový stát.

$svet{"evropa"}{"novy stat"} = {
    "rozloha" => 10_000,
    "lidi" => 1_000_000,
    "hlavni mesto" => "mesto X",
    "dalsi mesta" => [
        "mesto A",
        "mesto B"
    ]
};

Funkcí delete můžeme prvky datových struktur naopak mazat.

Moduly pro manipulaci s datovými strukturami

Nyní si představíme moduly Storable a Data::Dumper.

Tisk datových struktur

Modul Data::Dumper se používá k formátovanému tisku datových struktur. Obsahuje funkci Dumper, která přijímá jako parametr odkaz na datovou strukturu a tu zformátovanou tiskne na výstup.

use Data::Dumper;
print Dumper $odkaz;

V případě datové struktury podobné té, kterou jsme si dnes napsali, se vytiskne toto.

  $ perl dumper.pl
  $VAR1 = {
          'evropa' => {
                        'ceska republika' => {
                                               'lidi' => 10250000,
                                               'dalsi mesta' => [
                                                                  'Brno',
                                                                  'Ostrava',
                                                                  'Ceske Budejovice',
                                                                  'Plzen'
                                                                ],
                                               'rozloha' => 79000,
                                               'hlavni mesto' => 'Praha'
                                             },
                        ...
                      },
          'asie' => {}
          ...
        };
  $

Zapamatujme si, že je nutné, abychom opravdu předali odkaz. Svět na tom sice nestojí, ale je dobré to mít na paměti, když nám Dumper nevypíše to, co chceme. Může to svádět psát pouze

Takhle se vytiskne něco trochu jiného. Dumper ve skutečnosti přijímá seznam odkazů, takže by se vytiskly struktury pro každý klíč i hodnotu. Dumper musí být volána takto.

Perzistence datových struktur

Modul Storable zajišťuje perzistenci. Používá se k ukládání datových struktur do souborů a zpětně i k jejich načítání.

K uložení se používá funkce store. Umožňuje uložit do souboru jednu datovou strukturu. (Pokud jich chceme uložit více, můžeme předávat odkaz na pole odkazů na datové struktury.)

use Storable;
store(\%odkaz, "soubor");

store ukládá data do souboru v binární podobě.

Pro načtení ze souboru slouží funkce retrieve. Znovuvytvoří strukturu a vrátí na ní odkaz.

use Storable;
$r_svet = retrieve("soubor");

Storable nabízí ještě funkce dclone, která klonuje (nikoliv vytváří odkaz na ni!) datovou strukturu. Přesnou kopii tak můžeme získat tímto způsobem.

use Storable;
$r_kopie_svet = Storable::dclone(\%svet);

Následujícím trikem danou strukturu hned i pojmenujeme.

%kopie_svet = %{ Storable::dclone(\%svet) };

To bylo stručné, avšak pro běžné účely dostačující seznámení s moduly Storable a Data::Dumper. Zájemci naleznou podrobnější informace v dokumentaci.

Pseudohashe

Na závěr uveďme, opět spíše pro zajímavost, něco o pseudohashích. Pseudohash je speciální datová struktura, se kterou lze pracovat jako s odkazem na pole i jako odkazem na hash. V Perlu je zavedena pouze experimentálně.

Pseudohash je pole, jehož první prvek musí být odkaz na hash. V něm jsou řetězce, které dávají do vztahu indexy pole s klíči hashe.

$pseudohash = [{"a" => 1, "b" => 2, "c" => 3}, "1. hodnota", "2. hodnota", "3. hodnota"];

Nyní lze k hodnotám přistupovat jako k hodnotám hashe nebo hodnotám pole. Tyto zápisy vytisknou stejnou hodnotu.

print $pseudohash->{"c"};
print $pseudohash->[3];

Více o pseudohashích na perlref(1).

Verze pro tisk