ARCHIV

Perl (111) - Pokročilá práce se seznamy

Seznámíme se s několika zajímavými funkcemi, které jsou k dispozici v externích modulech. Zejména se zaměříme na efektivnější práci při operování se seznamem jako celkem, složitější cyklení a na permutování.

7.6.2010 00:00 | Jiří Václavík | Články autora | přečteno 12700×

Když jsme se v minulosti zabývali seznamy, nevyčerpali jsme plně všechny nástroje, které jsou nám k dispozici. Tento díl se to pokusí napravit. Vedle standardních funkcí ze základní distribuce Perlu budeme používat ještě navíc modul Algorithm::Loops. Ten tedy stáhneme z archivu CPAN a nainstalujeme.

Skalární operace provedená na pole po složkách

Ačkoliv jsme velkou část často používaných funkcí ze základní distribuce Perlu představili v začátku toho seriálu, stále jsme se neseznámili s veledůležitou funkcí map. Ta dokáže vzít pole, na každý jeho prvek aplikovat nějakou funkci a vytvořit tak pole nové.

Typickou úlohou pro map je konverze všech prvků seznamu řetězců z malých písmen na velké. Žádná běžná funkce, která by toto řešila neexistuje. Avšak máme zde funkci uc, která je schopna provést změnu velikosti písmen ve skalárním kontextu. Pomocí map ji provedeme po složkách.

@male=qw(abc def ghi);
print @velke = map(uc, @male);

Na operaci lze samozřejmě použít i funkci napsanou uživatelem. Příkladem nechť je následující kód, kde funkce map pro každý prvek $_ z pole @cisla vrátí výraz, který vznikne aplikací uvedené funkce na proměnnou $_ (tedy prvek pole @cisla). Do pole @dvojnasobky tedy v našem případě uložíme hodnoty 2, 4, 6, 8, 10, 12, 14, 16, 18, 20.

@cisla=1..10;
sub zdvojnasob {2*$_};
@dvojnasobky=map(zdvojnasob, @cisla);

Jako první argument funkce map lze zadat i samotný výraz z definice funkce zdvojnasob. Následující kód tak docílí téhož, aniž bychom definovali nový podprogram.

@cisla=1..10;
@dvojnasobky=map(2*$_, @cisla);

Poznamenejme, že v tomto výrazu nemusí $_ vůbec figurovat. Pro vytvoření pole pravdivých hodnot o stejné délce jako původní bychom tedy mohli použít i jeden z následujících příkazů.

print map(1, @puvodni);
print map(defined, @puvodni);

Chceme-li zvolit jinou datovou strukturu, do které se mají data ukládat, můžeme udělat jednoduchý trik a nevracet jen skalární hodnotu. Máme-li nějakou množinu klíčů, ke kterým nalezneme hodnoty, budeme je pravděpodobně chtít nějak rozumně uložit - tedy do hashe. V prvním argumentu funkce map tedy pro každý klíč nalezneme hodnotu pomocí nějaké funkce a vrátíme jak tento klíč, tak i záskanou hodnotu. Návod dává tento příkaz.

%hash = map{$_ => najdi_hodnotu($_)} @klice;

Poznamenejme, že varianta map používající složené závorky může občas dělat problémy. To proto, že složené závorky mohou indikovat blok i anonymní hash. To, jak se vyhnout problémům je obsáhleji diskutováno v dokumentaci.

map však není schopen řešit úplně všechno tak, jak bychom možná na první pohled očekávali. Chceme-li aplikovat na seznam operace tr/// nebo s///, pak je vhodné použít funkci Filter. Funkce map by zde fungovala jinak - zapsala by do nového pole vždy pravdivou nebo nepravdivou hodnotu podle toho, zda došlo k nahrazení. Tak se děje proto, že se fakticky vrací hodnota výrazu ($neco =~ tr///), nikoliv hodnota $neco.

Funkce Filter je k dispozici v modulu Algorithm::Loops. Je proto třeba tento modul zavést. Filter se používá podobně jako map. Nikoliv však stejně. Například vyžaduje použití složených závorek.

Příkladem je nahrazení všech slov kurs slovem kurz v prvcích pole @texty.

use Algorithm::Loops qw(Filter);
@zmenene = Filter{s/kurs/kurz/} @texty;

Jiným příkladem je modifikace čtění ze vstupu tak, aby byly ignorovány bílá místa na konci řádků.

use Algorithm::Loops qw(Filter);
@radky = Filter {s/\n+$//} <VSTUP>;

Analogie map pro celá pole

Funkce MapCar aplikuje danou funkci po složkách na pole polí. Používá se například na práci s maticemi. MapCar příjimá jako parametr anonymní podprogram a seznam odkazů na pole. Tento podprogram je aplikován na pole, která vzniknou seskupením prvních, druhých atd. prvků v předaných seznamech.

print MapCar sub{"@_\n"}, [1, 2, 3], [4, 5, 6], [7, 8];

Tento příklad vytiskne na výstup následující matici.

1 4 7
2 5 8
3 6

Existují další varianty příkazu MapCar. Pro bližší informace nahlédněte do dokumentace. Zde pro představu z dalšího uvedeme jen jeden příklad. Transponovanou matici získáme následujícím příkazem.

$transpozice = MapCarU {[@_]} @$matice;

Vnořené cykly

Co když potřebujeme vytvořit kód, který bude vypadat nějak takto?

for $i (...){
  ...
  for $j (...){
    ...
    for $k (...){
      ...
      for $l (...){
        ...
      }
    }
  }
}

Funkce NestedLoops řeší problém libovolně hlubokého vnoření cyklů do sebe. Uvedenou situaci tak lze vyřešit poměrně elegantně.

NestedLoops přijímá tři parametry. Není ale třeba uvádět všechny. Prvním parametrem je odkaz na pole, které obsahuje pro každý cyklus jeden prvek (od vnějšího cyklu po vnitřní). Zde je určeno, přes které hodnoty budeme iterovat. Druhým parametrem je odkaz na hash přepínačů, pomocí kterých se nastavují pokročilejší vlastnosti. Na závěr se udává odkaz na podprogram, který se má provést.

Podívejme se na příklad, kde máme dva cykly. Vnější jde od 1 do 2 a vnitřní od 3 do 4. Budeme uvnitř nich tisknout aktuální hodnotu počítadel obou těchto cyklů.

NestedLoops(
  [([1..2], [3..4])],
  sub {print "@_\n"}
);

V hashi uvedeném ve druhém parametru můžeme použít zápis OnlyWhen => &test. Takto bude podprogram vykonán pouze tehdy, jsou-li splněny příslušné podmínky (test vrátí pravdivou hodnotu). Podívejme se na toto volání.

NestedLoops(
  [([1..2]) x 3],
  {OnlyWhen => \&test},
  \&udelej_neco
);

Bude mít stejný efekt, jako bychom napsali tento kód.

for $i (1..2){
  udelej_neco($i) if test($i);
  for $j (1..2){
    udelej_neco($i, $j) if test($i, $j);
    for $k (1..2){
      udelej_neco($i, $j, $k) if test($i, $j, $k);
    }
  }
}

Permutace

V modulu Algorithm::Loops je též k dispozici několik funkcí pro práci s permutacemi. Permutace pole je obecně nějaké přeuspořádání prvků v poli. Pokud se hodnoty v poli opakují, pak algoritmus, který nalezne všechny možné permutace není vůbec triviální. Pomocí funkcí NextPermute a NextPermuteNum lze toto všechno zařídit velmi pohodlně.

Funkce NextPermute (resp. NextPermuteNum pro čísla - rozdíl je v tom, že se shodnost prvků seznamů vyhodnocuje pomocí operátoru == nebo eq) se obvykle používá v podmínce cyklu. Stará se o to, abychom v každé iteraci dostali novou permutaci našeho seznamu. Jakmile projdeme všechny permutace, cyklus skončí, neboť NextPermute vrátí nepravdivou hodnotu.

Chceme nyní vypsat všechny permutace prvků 2, 3, 3, 1. Podívejme se na následující příklad.

use Algorithm::Loops qw(NextPermuteNum);
@seznam = (2, 3, 3, 1);
do{
  print @seznam,"\n";
}while(NextPermuteNum(@seznam))

Výstupem jsou následující řádky.

2331
3123
3132
3213
3231
3312
3321

Na první pohled vidíme, že něco není správně, protože dokonce žádný z řádků nezačína jedničkou. To je proto, že funkce NextPermuteNum požaduje vzestupně setříděný seznam. To může být zdrojem chyb. Příklad totiž musíme upravit.

use Algorithm::Loops qw(NextPermuteNum);
@seznam = sort {$a<=>$b} (2, 3, 3, 1);
do{
  print @seznam,"\n";
}while(NextPermuteNum(@seznam))

Jestliže se některá hodnota vyskytuje v seznamu vícekrát, pak teoreticky můžeme dostat stejnou permutaci vícekrát. Funkce NextPermuteNum ji ale vrátí vždy jen jednou. Můžeme se o tom přesvědčit v následujícím příkladu.

@seznam = (1, 1, 1, 1);
do{
  print @seznam,"\n";
}while(NextPermuteNum(@seznam))

Seznam má 4 prvky a tedy máme 4!=4*3*2*1=24 permutací. Avšak jakákoliv permutace aplikovaná na náš seznam dá výsledek 1111. Proto tento kód produkuje jen jediný řádek.

Existuje též modul Algorithm::Permute, který umí o něco více a řeší problematiku permutací pomocí objektového rozhraní.

Verze pro tisk