Foto mit freundlicher Genehmigung:Jimray
Wir haben in einem früheren awk-Einführungsartikel gesehen, dass awk ein effektives Werkzeug für alles sein kann, von kleinen Einzeilern bis hin zu einigen interessanten Anwendungen. Sicherlich stehen uns komplexere Sprachen zur Verfügung, wenn es die Situation erfordert; Perl und Python kommen mir in den Sinn. Anwendungen, die Netzwerkunterstützung, Datenbankzugriff, Benutzerschnittstellen, binäre Daten oder umfassendere Bibliotheksunterstützung und -komplexität erfordern, sollten am besten anderen Sprachen mit besserer Unterstützung in diesen Bereichen überlassen werden.
Nichtsdestotrotz ist awk hervorragend Sprache zum Testen von Algorithmen und Anwendungen mit einiger Komplexität , insbesondere wenn das Problem in Stücke zerlegt werden kann, die als Teil einer Pipe gestreamt werden können. Es ist ein ideales Werkzeug, um die Funktionen der Shell-Programmierung zu erweitern, da es allgegenwärtig ist; in irgendeiner Form auf fast allen Unix/Linux/BSD-Systemen zu finden. Viele Probleme, die mit Text, Protokollzeilen oder Symboltabellen zu tun haben, werden mit awk zusammen mit den anderen Werkzeugen, die auf Unix/Linux-Systemen zu finden sind, bequem gelöst oder zumindest prototypisiert.
Während awk sich gut dafür eignet, die Eingabe zeilenweise zu bearbeiten, zu verarbeiten und dann etwas Ausgabe für jede Zeile zu senden, kann es auch in einer traditionelleren Anwendung im Batch-Stil verwendet werden, in der es die gesamte Eingabe liest, verarbeitet und dann sendet verarbeitete Ausgabe weiter.
Noch ein Sudoku-Puzzle-Löser – YASPS für Awk
Die Anwendung, die ich als Beispiel gewählt habe, ist „Noch ein weiterer Sudoku-Puzzle-Löser“. Ich muss gleich zu Beginn gestehen, dass ich mich noch nie hingesetzt habe, um eines dieser Rätsel selbst zu lösen, sondern es in ein paar Tagen skizziert habe, während ich in einem Zug pendelte und anderen Leuten dabei zusah, wie sie daran arbeiteten. Ich denke, es hat viel mehr Spaß gemacht, als eines der Rätsel zu lösen..
YASPS-Programm für Awk herunterladen:solve.awk
Das von mir gewählte Eingabeformat ist in awk einfach zu parsen und in der Unix-Umgebung ziemlich traditionell. Leere Zeilen und solche, die mit einem Rautezeichen (#) beginnen, werden ignoriert, was das Einfügen von Kommentaren erleichtert. Zur besseren Lesbarkeit können zwischen den Spalten zusätzliche Leerzeichen verwendet werden. Ein Beispiel ist in der folgenden Abbildung dargestellt:
------------------------------------------------------------------------------- # 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 -------------------------------------------------------------------------------
Es gibt fast keine Fehlerprüfung in diesem Programm, aber es wäre einfach, es vor oder als Teil eines Wrapper-Skripts hinzuzufügen. Ich überlasse das dem Leser als Übung.
Dieses Programm verwendet einen sehr einfachen rekursiven Backtracking-Algorithmus, der zunächst der Tiefe folgt und ungültige Einträge im Voraus und fortlaufend eliminiert. Awk hat möglicherweise nicht die Ausdruckskraft, um komplexe Daten darzustellen, die Perl oder andere Sprachen haben, aber mit Vorsicht können viele Probleme und Datensätze mittlerer Größe verwendet werden. Dieser Algorithmus ist vielleicht nicht der beste, aber er ist sicherlich schnell genug für die meisten Probleme und einfach zu implementieren.
Bei jedem Problem macht die effektive Darstellung der Daten die Aufgabe, ein Programm zu entwerfen, viel einfacher. Ich habe den vollständigen Zustand des Puzzles in einer Matrix namens „Master“ dargestellt. Dies wird kaum für viel verwendet, außer um aufzuzeichnen, was wo ist und um die endgültige Ausgabe zu machen.
Die wichtigsten Arbeitstiervariablen sind drei weitere Arrays. Intuitiv wissen wir von der rekursiven Trial-and-Error-Methode, die wir gewählt haben, dass wir die Gültigkeit von Versuchsnummern ziemlich oft überprüfen müssen. Um diesen Prozess zu beschleunigen, pflegen wir assoziative Arrays zum Speichern des aktuellen Zustands für die Zeilen, Spalten und jede Region (die wir, obwohl sie technisch nicht korrekt ist, einen „Quadranten“ nennen). Dies sind die Arrays R, C und Q. (Beachten Sie, dass bei awk zwischen Groß- und Kleinschreibung unterschieden wird.)
Manchmal hilft es, wenn Sie versuchen, allgemeine Berechnungen aus verschachtelten for-Schleifen oder rekursiven Funktionsaufrufen herauszufiltern, um häufig verwendete Werte vorzuberechnen. Ich hatte dies mit der „regmap“-Matrix versucht, die eine Quadrantennummer bei gegebenen Zeilen- und Spaltenwerten speichern würde, aber ich fand die Zeitersparnis in diesem Fall mehrdeutig. Ich habe es auskommentiert gelassen, aber Ihre Laufleistung kann variieren und die Technik ist oft sehr nützlich.
Rekursive Algorithmen werden oft am besten entworfen und daher von oben nach unten beschrieben. Die oberste Funktion in diesem Programm heißt „search()“ und wird vom „END“-Muster aufgerufen, nachdem die Problemdaten in die Arrays eingelesen wurden.
Auf hoher Ebene beginnt search() mit den bereitgestellten Zeilen- und Spaltenparametern und sucht nach dem nächsten zu prüfenden leeren Bereich. Wenn keine vorhanden sind, wurde das Problem gelöst und es kehrt mit der Lösung zurück. Wenn es ein leeres Feld gibt (dargestellt durch Null), testet es verfügbare Zahlen (mit der Funktion inuse() auf Zahlen, die in dieser Zeile, Spalte oder diesem Quadranten nicht verwendet werden), indem es eine Zahl in die Arrays einfügt, indem es mark() verwendet und aufruft selbst rekursiv. Wenn die rekursive search()-Funktion eine Null zurückgibt, bedeutet dies, dass sie fehlgeschlagen ist, sodass die mark()-Funktion erneut aufgerufen wird, um die Markierung der Versuchsnummer aufzuheben. Es wiederholt sich dann, bis die Möglichkeiten erschöpft sind oder der Aufruf von search() Erfolg zurückgibt.
Das Schöne an vielen rekursiven Algorithmen ist die inhärente Eleganz und Einfachheit der Lösungen. Obwohl sie manchmal nicht die schnellsten Algorithmen sind, sind sie oft „schnell genug“ und einfacher zu entwerfen. Dieses Programm löst die meisten Rätsel in weniger als ein paar Sekunden. Eine Sache, die mir beim Ausprobieren dieses Programms bei verschiedenen Rätseln aufgefallen ist, ist, dass, wenn ein Problem länger dauerte, um es zu lösen (in zehn Sekunden), das einfache Transponieren der Matrix oft die gleiche Lösung in einem Bruchteil einer Sekunde ergab. Bei heutigen Mehrkern-CPUs bietet sich eine Möglichkeit zur Beschleunigung an:Schreiben Sie ein Wrapper-Skript, das mehrere Instanzen des Programms mit unterschiedlichen Transpositionen der Matrix startet. Ein Beispiel wird mit dem oben gezeigten vorherigen Rätsel und der transponierten Version in der folgenden Abbildung gezeigt, wo das transponierte Problem viermal schneller gelöst wurde.
------------------------------------------------------------------------------- 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 -------------------------------------------------------------------------------
Wenn etwas noch schnelleres erforderlich ist, kann dies oft erreicht werden, indem der Algorithmus in eine andere Sprache mit einer direkteren Darstellung der Datensätze übersetzt wird. Ich habe dieses Programm einmal in C übersetzt, mit einer interessanten Wendung bei der Datenindizierung. Diese Version wird wahrscheinlich einige Größenordnungen schneller ausgeführt, hauptsächlich aufgrund der Art und Weise, wie die Daten dargestellt werden. Wahrscheinlich werden wir „Noch ein weiterer Sudoku-Rätsellöser mit C“ später als einen weiteren Artikel veröffentlichen.
Ich glaube, dass awk einen Platz in jedermanns Toolkit verdient. Seine Einfachheit im Vergleich zu anderen Sprachen wird vielleicht als Schwäche angesehen, aber ich sehe es als eine seiner Stärken. Die Sprache kann an einem Nachmittag erlernt und ohne Rückgriff auf Nachschlagewerke zur Lösung vieler alltäglicher Probleme verwendet werden. Ich verwende es regelmäßig direkt von der Befehlszeile aus, bis hin zur Implementierung von Dingen wie Compilern für DSLs (Domain Specific Languages).
Empfohlene Awk-Bücher
- Die Programmiersprache AWK von Alfred V. Aho, Brian W. Kernighan und Peter J. Weinberger. Das Originalbuch der Autoren der Sprache enthält einige hervorragende Beispiele für mäßig komplexe Programme und ist immer noch mein Lieblingsbuch über awk. Herausgegeben von Addison-Wesley, 1988. ISBN 020107981X.
- Mehr Programming Pearls:Confessions of a Coder von Jon Bentley, AT&T Bell Labs, Murray Hill, NJ. Ein weiteres Buch zur Verwendung von awk als Prototyping-Tool für Algorithmen finden Sie in More Pearls. Hervorragende Lektüre. Erscheinungsjahr:1988. ISBN:0201118890