Foto per gentile concessione di:jimray
Abbiamo visto in un precedente articolo introduttivo di awk che awk può essere uno strumento efficace per qualsiasi cosa, dalle piccole battute fino ad alcune applicazioni interessanti. Ci sono certamente linguaggi più complessi a nostra disposizione se la situazione lo richiede; mi vengono in mente perl e python. Le applicazioni che richiedono supporto di rete, accesso a database, interfacce utente, dati binari o supporto e complessità di librerie più estese è meglio lasciare ad altre lingue con un supporto migliore in queste aree.
Tuttavia, awk è un'eccellente linguaggio per testare algoritmi e applicazioni con una certa complessità , in particolare quando il problema può essere suddiviso in blocchi che possono essere trasmessi in streaming come parte di un tubo. È uno strumento ideale per aumentare le funzionalità della programmazione della shell poiché è onnipresente; si trova in qualche forma su quasi tutti i sistemi Unix/Linux/BSD. Molti problemi relativi al testo, alle linee di registro o alle tabelle dei simboli vengono risolti facilmente o almeno prototipati con awk insieme agli altri strumenti presenti sui sistemi Unix/Linux.
Sebbene awk si presti bene a operare sull'input di una riga alla volta, elaborando e quindi inviando dell'output per ciascuna riga, può anche essere utilizzato in un'applicazione più tradizionale in stile batch in cui legge tutto l'input, elabora e quindi invia il output elaborato in poi.
Ancora un altro risolutore di puzzle di Sudoku:YASPS per Awk
L'applicazione che ho scelto di utilizzare come esempio è "l'ennesimo risolutore di puzzle di sudoku". Devo confessare all'inizio che non mi sono mai seduto per risolvere uno di questi enigmi da solo, ma l'ho abbozzato in pochi giorni mentre mi spostavo su un treno e osservavo altre persone che ci lavoravano. Penso che sia stato molto più divertente che fare uno qualsiasi dei puzzle..
Scarica il programma YASPS per Awk:solve.awk
Il formato di input che ho scelto è facile da analizzare in awk ed è abbastanza tradizionale nell'ambiente Unix. Le righe vuote e quelle che iniziano con un carattere hash (#) vengono ignorate semplificando l'inserimento di commenti. È possibile utilizzare spazi aggiuntivi tra le colonne per la leggibilità. Un esempio è mostrato nella figura seguente:
------------------------------------------------------------------------------- # 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 -------------------------------------------------------------------------------
Non c'è quasi nessun controllo degli errori in questo programma, ma sarebbe facile aggiungerlo prima o come parte di uno script wrapper. Lo lascerò come esercizio per il lettore.
Questo programma utilizza un algoritmo di backtracking ricorsivo in profondità molto semplice con eliminazione anticipata e continua di voci non valide. Awk potrebbe non avere il potere espressivo per rappresentare dati complessi che hanno Perl o altri linguaggi, ma con cura è possibile utilizzare molti problemi e set di dati di dimensioni moderate. Questo algoritmo potrebbe non essere il migliore in circolazione, ma è sicuramente abbastanza veloce per la maggior parte dei problemi ed è facile da implementare.
Con qualsiasi problema, rappresentare i dati in modo efficace rende molto più semplice il compito di progettare un programma. Ho rappresentato lo stato completo del puzzle in una matrice chiamata “master”. Questo è usato a malapena per molto, tranne per tenere un registro di cosa è dove e per fare l'output finale.
Le principali variabili del cavallo di battaglia sono altre tre matrici. Intuitivamente sappiamo dal metodo ricorsivo per tentativi ed errori che abbiamo scelto che dovremo controllare la validità dei numeri di prova abbastanza spesso. Per accelerare tale processo, manteniamo array associativi per memorizzare lo stato corrente per righe, colonne e ciascuna regione (che, sebbene non tecnicamente corretta, chiameremo "quadrante"). Questi sono gli array R, C e Q. (Nota che awk fa distinzione tra maiuscole e minuscole.)
A volte aiuta quando si tenta di scomporre calcoli comuni da cicli for nidificati o chiamate di funzioni ricorsive per pre-calcolare valori che vengono utilizzati spesso. L'avevo provato con la matrice "regmap" che avrebbe memorizzato un numero di quadrante dati i valori di riga e colonna, ma in questo caso ho trovato ambigui il risparmio di tempo. L'ho lasciato commentato, ma il tuo chilometraggio può variare e la tecnica è spesso molto utile.
Gli algoritmi ricorsivi sono spesso progettati al meglio e quindi descritti in modo top-down. La funzione principale in questo programma si chiama "search()" e viene chiamata dal pattern "END" dopo che i dati del problema sono stati letti negli array.
Ad alto livello, search() inizia con i parametri di riga e colonna forniti e cerca lo spazio vuoto successivo da controllare. Se non ce ne sono, il problema è stato risolto e si ripresenta con la soluzione. Se c'è uno spazio vuoto (rappresentato da zero), verifica i numeri disponibili (con la funzione inuse(), per i numeri non in uso in quella riga, colonna o quadrante) inserendo un numero negli array usando mark() e chiamando stesso in modo ricorsivo. Se la funzione ricorsiva search() restituisce uno zero significa che ha fallito, quindi la funzione mark() viene nuovamente chiamata per deselezionare il numero di prova. Quindi esegue il ciclo finché le possibilità non sono esaurite o la chiamata search() restituisce successo.
La bellezza di molti algoritmi ricorsivi è l'eleganza intrinseca e la semplicità delle soluzioni. Sebbene a volte non siano gli algoritmi più veloci, spesso sono "abbastanza veloci" e più facili da progettare. Questo programma risolve la maggior parte dei puzzle in meno di pochi secondi. Una cosa che ho notato mentre provavo questo programma su diversi enigmi è che se un problema richiedeva un periodo di tempo più lungo per essere risolto (in decine di secondi), la semplice trasposizione della matrice spesso darebbe la stessa soluzione in una frazione di secondo. Con le CPU multi-core di oggi, questo suggerisce una possibilità per velocizzarlo:scrivere uno script wrapper che avvii diverse istanze del programma con diverse trasposizioni della matrice. Viene mostrato un esempio con il puzzle precedente mostrato sopra e la versione trasposta nella figura seguente in cui il problema trasposto è stato risolto quattro volte più velocemente.
------------------------------------------------------------------------------- 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 -------------------------------------------------------------------------------
Quando è necessario qualcosa di ancora più veloce, spesso può essere ottenuto traducendo l'algoritmo in un altro linguaggio con una rappresentazione più diretta dei set di dati. Ho fatto una traduzione di questo programma in C una volta con una svolta interessante sull'indicizzazione dei dati. Questa versione probabilmente esegue alcuni ordini di grandezza più velocemente, in gran parte a causa del modo in cui i dati sono rappresentati. Probabilmente rilasceremo "Yet Another Sudoku Puzzle Solver Using C" come un altro articolo più avanti.
Credo che awk meriti un posto nella cassetta degli attrezzi di tutti. La sua semplicità rispetto ad altre lingue è forse vista come una debolezza, ma io la vedo come uno dei suoi punti di forza. La lingua può essere appresa in un pomeriggio e utilizzata senza ricorrere a libri di riferimento per risolvere molti problemi quotidiani. Lo uso regolarmente direttamente dalla riga di comando, fino all'implementazione di cose come i compilatori per DSL (Domain Specific Languages).
Libri Awk consigliati
- Il linguaggio di programmazione AWK di Alfred V. Aho, Brian W. Kernighan e Peter J. Weinberger. Il libro originale degli autori della lingua ha degli ottimi esempi di programmi moderatamente complessi ed è ancora il mio libro preferito su awk. Pubblicato da Addison-Wesley, 1988. ISBN 020107981X.
- Altre perle di programmazione:Confessioni di un programmatore di Jon Bentley, AT&T Bell Labs, Murray Hill, NJ. Un altro libro sull'utilizzo di awk come strumento di prototipazione per algoritmi può essere trovato in More Pearls. Ottima lettura. Anno di pubblicazione:1988. ISBN:0201118890