Foto s laskavým svolením:jimray
V předchozím úvodním článku awk jsme viděli, že awk může být účinným nástrojem pro vše od malých jednolinkových až po zajímavé aplikace. Určitě máme k dispozici složitější jazyky, pokud to situace vyžaduje; perl a python přicházejí na mysl. Aplikace vyžadující síťovou podporu, přístup k databázi, uživatelská rozhraní, binární data nebo rozsáhlejší podporu a složitost knihoven je nejlepší přenechat jiným jazykům s lepší podporou v těchto oblastech.
Nicméně awk je vynikající jazyk pro testování algoritmů a aplikací s určitou složitostí , zejména tam, kde lze problém rozdělit na kousky, které mohou proudit jako součást potrubí. Je to ideální nástroj pro rozšíření funkcí programování shellu, protože je všudypřítomný; nalezený v nějaké formě na téměř všech systémech Unix/Linux/BSD. Mnoho problémů souvisejících s textem, řádky protokolu nebo tabulkami symbolů je snadno vyřešeno nebo alespoň prototypováno pomocí awk spolu s dalšími nástroji, které se nacházejí na systémech Unix/Linux.
Zatímco awk se dobře hodí k provozu na vstupu po řádku, zpracovává a poté odesílá nějaký výstup pro každý řádek, může být také použit v tradičnějších aplikacích dávkového stylu, kde čte všechny vstupy, zpracovává a poté odesílá zpracovaný výstup dále.
Ještě další řešení sudoku – YASPS pro Awk
Aplikace, kterou jsem se rozhodl použít jako příklad, je „další luštitel sudoku“. Hned na začátku se musím přiznat, že jsem nikdy sám neseděl, abych vyřešil jednu z těchto hádanek, ale načrtl jsem to během několika dní, když jsem dojížděl ve vlaku a sledoval, jak na nich ostatní lidé pracují. Myslím, že to byla mnohem větší zábava, než vlastně dělat nějaké hádanky..
Stáhněte si program YASPS pro Awk:solve.awk
Vstupní formát, který jsem zvolil, je ten, který lze snadno analyzovat v awk a je poměrně tradiční v prostředí Unixu. Prázdné řádky a řádky začínající znakem hash (#) jsou ignorovány, což usnadňuje vkládání komentářů. Mezi sloupci lze kvůli čitelnosti použít mezery navíc. Příklad je znázorněn na následujícím obrázku:
------------------------------------------------------------------------------- # I forget where I got this.. # this is one of the hardest ones I've found for this algorithm, although # after transposing the matrix it can be solved in a fraction of the time 2 0 0 6 7 0 0 0 0 0 0 6 0 0 0 2 0 1 4 0 0 0 0 0 8 0 0 5 0 0 0 0 9 3 0 0 0 3 0 0 0 0 0 5 0 0 0 2 8 0 0 0 0 7 0 0 1 0 0 0 0 0 4 7 0 8 0 0 0 6 0 0 0 0 0 0 5 3 0 0 8 -------------------------------------------------------------------------------
V tomto programu není téměř žádná kontrola chyb, ale bylo by snadné jej přidat před nebo jako součást obalového skriptu. Nechám to jako cvičení pro čtenáře.
Tento program používá velmi jednoduchý hloubkový rekurzivní algoritmus zpětného sledování s průběžnou eliminací neplatných záznamů. Awk nemusí mít výrazovou sílu pro reprezentaci složitých dat, kterou má perl nebo jiné jazyky, ale s opatrností lze použít mnoho problémů a sad dat střední velikosti. Tento algoritmus nemusí být nejlepší, ale rozhodně je dostatečně rychlý pro většinu problémů a snadno se implementuje.
V případě jakéhokoli problému efektivní reprezentace dat značně zjednodušuje úkol navrhování programu. Znázornil jsem úplný stav skládačky v matici zvané „master“. To se stěží používá pro mnoho, kromě vedení záznamů o tom, co je kde, a pro provádění konečného výstupu.
Hlavními proměnnými tahouna jsou tři další pole. Z rekurzivní metody pokusu a omylu, kterou jsme zvolili, intuitivně víme, že budeme muset poměrně často kontrolovat platnost zkušebních čísel. Abychom tento proces urychlili, udržujeme asociativní pole pro ukládání aktuálního stavu pro řádky, sloupce a každou oblast (která, i když to není technicky správné, budeme nazývat „kvadrant“). Toto jsou pole R, C a Q. (Všimněte si, že awk rozlišuje velká a malá písmena.)
Někdy to pomůže, když se pokusíte vyřadit běžné výpočty z vnořených smyček for nebo rekurzivních volání funkcí na předvýpočetní hodnoty, které se často používají. Zkoušel jsem to s maticí „regmap“, která by ukládala číslo kvadrantu dané hodnotami řádků a sloupců, ale zjistil jsem, že úspora času v tomto případě je nejednoznačná. Nechal jsem to komentovat, ale váš počet najetých kilometrů se může lišit a technika je často velmi užitečná.
Rekurzivní algoritmy jsou často nejlépe navrženy, a proto jsou popsány shora dolů. Nejvyšší funkce v tomto programu se nazývá „search()“ a je volána ze vzoru „END“ po načtení problémových dat do polí.
Na vysoké úrovni začíná search() s dodanými parametry řádku a sloupce a hledá další prázdné místo ke kontrole. Pokud žádné nejsou, problém byl vyřešen a vrátí se s řešením. Pokud je prázdné místo (reprezentované nulou), otestuje dostupná čísla (pomocí funkce inuse() pro čísla, která se v daném řádku, sloupci nebo kvadrantu nepoužívají) vložením čísla do polí pomocí mark() a voláním sama rekurzivně. Pokud funkce rekurzivního vyhledávání() vrátí nulu, znamená to, že selhala, takže je znovu zavolána funkce mark(), která zruší označení zkušebního čísla. Poté se opakuje, dokud nejsou vyčerpány možnosti nebo dokud volání search() nevrátí úspěch.
Krása mnoha rekurzivních algoritmů spočívá v inherentní eleganci a jednoduchosti řešení. I když se někdy nejedná o nejrychlejší algoritmy, často jsou „dostatečně rychlé“ a snáze se navrhují. Tento program řeší většinu hádanek za méně než několik sekund. Jedna věc, kterou jsem si všiml při zkoušení tohoto programu na různých hádankách, je, že pokud řešení problému trvalo delší dobu (v desítkách sekund), pouhá transpozice matice by často poskytla stejné řešení ve zlomku sekundy. U dnešních vícejádrových CPU to naznačuje jednu možnost, jak to urychlit:Napište obalový skript, který spustí několik instancí programu s různými transpozicemi matice. Příklad je uveden s předchozí hádankou uvedenou výše a transponovanou verzí na následujícím obrázku, kde byl transponovaný problém vyřešen čtyřikrát rychleji.
------------------------------------------------------------------------------- marion:~/sudoku$ time awk -f solve.awk THE-HARDEST-SO-FAR.dat # Searches=134214 2 8 3 6 7 1 9 4 5 9 7 6 5 4 8 2 3 1 4 1 5 3 9 2 8 7 6 5 6 7 4 1 9 3 8 2 8 3 4 2 6 7 1 5 9 1 9 2 8 3 5 4 6 7 3 2 1 7 8 6 5 9 4 7 5 8 9 2 4 6 1 3 6 4 9 1 5 3 7 2 8 real 0m10.009s user 0m9.889s sys 0m0.024s marion:~/sudoku$ time awk -f solve.awk /tmp/transposed.dat # Searches=32253 8 3 4 7 9 2 6 1 5 2 1 9 6 5 8 7 3 4 7 6 5 4 1 3 8 2 9 3 4 6 5 7 9 2 8 1 5 2 8 3 6 1 9 4 7 1 9 7 8 2 4 3 5 6 9 8 1 2 4 7 5 6 3 4 5 2 9 3 6 1 7 8 6 7 3 1 8 5 4 9 2 real 0m2.487s user 0m2.456s sys 0m0.008s -------------------------------------------------------------------------------
Když je požadováno něco ještě rychlejšího, lze toho často dosáhnout překladem algoritmu do jiného jazyka s přímější reprezentací datových sad. Jednou jsem provedl překlad tohoto programu do C se zajímavým zvratem v indexování dat. Tato verze pravděpodobně pracuje o několik řádů rychleji, především kvůli způsobu, jakým jsou data reprezentována. Pravděpodobně později vydáme další článek „Ještě další řešení sudoku pomocí C“.
Věřím, že awk si zaslouží místo v sadě nástrojů každého. Jeho jednoduchost ve srovnání s jinými jazyky je možná vnímána jako slabina, ale já to vidím jako jednu z jeho silných stránek. Jazyk se lze naučit za odpoledne a používat jej bez použití referenčních knih pro řešení mnoha každodenních problémů. Používám jej pravidelně přímo z příkazového řádku, až po implementaci věcí, jako jsou kompilátory pro DSL (Domain Specific Languages).
Doporučené knihy Awk
- Programovací jazyk AWK od Alfreda V. Aho, Briana W. Kernighana a Petera J. Weinbergera. Původní kniha od autorů jazyka má několik vynikajících příkladů středně složitých programů a je stále mou oblíbenou knihou o awk. Vydalo Addison-Wesley, 1988. ISBN 020107981X.
- Další perly programování:Zpovědi kodéra od Jona Bentleyho, AT&T Bell Labs, Murray Hill, NJ. Další knihu o použití awk jako prototypového nástroje pro algoritmy lze nalézt v More Pearls. Výborné čtení. Rok vydání:1988. ISBN:0201118890