Foto mit freundlicher Genehmigung:Kol Tregaskes
Im ersten Artikel dieser Serie haben wir gesehen, wie awk für mehr als nur die Textverarbeitung eingesetzt (oder gespielt) werden kann. Das einfache Skript demonstrierte die Verwendung von assoziativen Arrays, Rekursion und wie wir mehr Arrays (mehr als zur Darstellung der Daten erforderlich) verwenden könnten, um die Verarbeitung zu beschleunigen. Am Ende blieben einige Teaser-Ideen übrig, wenn Sie nach etwas Schnellerem suchen.
Wann würden Sie etwas Schnelleres brauchen? Ein Leser wies darauf hin, dass das Lösen der Rätsel einfach ist. Was wäre, wenn Sie ein System zum Generieren von Rätseln entwerfen würden? Eines der Werkzeuge, die Sie benötigen, ist ein Programm, das sicherstellt, dass es nur eine Lösung für ein Rätsel gibt. (Ein anderer Leser, Milos, schlug leichte Modifikationen vor, um alle Lösungen zu finden.) Oder was wäre, wenn wir die Größe der Rätsel auf 16×16 oder 25×25 erhöhen wollten?
Das Übersetzen des Skripts in eine schnell kompilierte Sprache könnte hilfreich sein, und in diesem Artikel untersuchen wir einen der Hauptvorteile von awk, nämlich die einfache Übersetzung nach C, falls erforderlich.
Erste Schnittübersetzung
In unserem ersten Versuch, das Programm zu übersetzen, werden wir Ausschnitte des Codes nebeneinander zeigen, um die geringfügigen erforderlichen Unterschiede zu demonstrieren. Wir werden die drei Hauptfunktionen untersuchen, die am meisten betroffen sind; inuse(), mark() und die rekursive search()-Funktion. Der Code ist so eng, dass eine Kopie des awk-Programms zum Starten der Bearbeitung für die Konvertierung nach C verwendet wurde.
Zuerst, um einige der Definitionen aus dem Weg zu räumen. Wir werden auch die Vorkompilierung der Region verwenden, da wir nach mehr Geschwindigkeit suchen. Der erste Unterschied, der behandelt werden muss, besteht darin, dass die awk-Array-Indizes eins relativ waren und C-Array-Indizes standardmäßig null relativ sind. Für unsere Zwecke und um die Dinge einfach zu halten, werden wir weiterhin die einen relativen Index verwenden und Arrays mit zusätzlichen Elementen zuweisen.
#define SUBORDER 3
#define ORDER (SUBORDER * SUBORDER)
#define MARK 1
#define UNMARK 0
int count = 0;
unsigned int regmap[ORDER+1] [ORDER+1];
unsigned int master[ORDER+1] [ORDER+1];
unsigned int C[ORDER+1][ORDER+1];
unsigned int R[ORDER+1][ORDER+1];
unsigned int Q[ORDER+1][ORDER+1];
#define fregmap(r,c) (regmap[r][c])
/* precompile region map for faster lookup
*/
int initregmap()
{
int i,j;
for (i = 0; i < ORDER ; i++)
for (j = 0; j < ORDER ; j++)
regmap[i+1][j+1] = i/SUBORDER*SUBORDER + j/SUBORDER +1 ;
} Der Awk-zu-C-Vergleich
Nun zu den drei Hauptfunktionen, um die Ähnlichkeiten und geringfügigen Unterschiede zu erkennen. Die ursprünglichen awk-Versionen der Funktionen werden als Kommentare hinterlassen. Hier sind einige der Unterschiede:
- C erfordert Deklarationen von Funktions-, Parameter- und Variablentypen
- awk benötigt kein Semikolon als Trennzeichen für Anweisungen, wenn es nur eine Anweisung pro Zeile gibt
- awk „fälscht“ mehrdimensionale Arrays, indem es assoziative Arrays verwendet und die Indizes mit dem SUBSEP-Zeichen trennt, das durch ein Komma repräsentiert wird
- In awk werden lokale Variablendeklarationen einfach mit den Parametern für die Funktion eingefügt, normalerweise mit zusätzlichen Leerzeichen, um sie zur besseren Lesbarkeit zu trennen
- Kommentartrennzeichen sind unterschiedlich
- Funktionen werden anders deklariert
- C verwendet null relative Indizes für Arrays
Trotzdem sieht man eine direkte Eins-zu-Eins-Entsprechung und die Übersetzung von awk nach C ist in diesem Beispiel fast trivial.
inline int inuse(r,c,try) // function inuse(r,c,try) {
int r,c,try; //
{ //
int q = fregmap(r,c); // q = fregmap(r,c)
//
return (R[r][try] || C[c][try] || Q[q][try]); // return (C[c,try] || R[r,try] || Q[q,try])
} // }
inline void mark(r,c,try, flag) // function mark(r,c,try, flag, q) {
int r,c,try, flag; //
{ //
int q = fregmap(r,c); // q = fregmap(r,c)
//
Q[q][try] = flag; // Q[q,try] = flag
R[r][try] = flag; // R[r,try] = flag
C[c][try] = flag; // C[c,try] = flag
master[r][c] = flag ? try : 0 ; // master[r,c] = flag ? try : 0
} // }
int search(r,c) // function search(r,c, q,i,a,try) {
int r,c; //
{ //
int q,i,a,try; //
count++ ; // count++
//
while (master[r][c]) { // while (master[r,c]) {
if (++c > ORDER) { // if (++c > ORDER) {
c = 1 ; // c = 1
if (++r > ORDER) { // if (++r > ORDER) {
/* then we're done filling */ // # then we're done filling!
return 1 ; // return 1
} // }
} // }
} // }
//
for (try=1; try <= ORDER; try++) { // for (try=1; try <= ORDER; try++) {
if (! inuse(r,c,try)) { // if (! inuse(r,c,try)) {
mark(r,c,try, MARK) ; // mark(r,c,try, 1)
if (search(r,c)) return 1 ; // if (search(r,c)) return 1
/* else zero returned -- unwind, unmark */ // # else zero returned -- unwind
mark(r,c,try, UNMARK) ; // mark(r,c,try, 0) # unmark
} // }
} // }
//
return 0; // return 0
} // }
Bitmaps
Einer der Schlüssel zur Geschwindigkeit, auf den im vorherigen Artikel angespielt wurde, war die Verwendung von Bitmaps für die R-, C- und Q-Arrays. Da jedes dieser Arrays nur zum Testen auf Elementzugehörigkeit verwendet wird oder nicht, handelt es sich streng genommen um eine binäre Funktion, die durch ein einzelnes Bit anstelle eines Int dargestellt werden könnte. Dadurch konnten wir im Vergleich zu anderen Suchmethoden in sehr wenigen Maschinenzyklen testen, ob ein Eintrag gültig war oder nicht (eine der am stärksten betroffenen Funktionen).
Hier sind ein paar Codeschnipsel, die zeigen, wie es unserem ursprünglichen awk-Prototyp ähnelt. Die obligatorischen Deklarationen haben sich gegenüber der ursprünglichen C-Version oben geringfügig geändert; Wir haben eine Dimension für die C-, R- und Q-Arrays verloren und werden die Ints als Bit-Arrays verwenden.
----------------------------------------------------------------------------- #define SUBORDER 3 #define ORDER (SUBORDER * SUBORDER) unsigned int regmap[ORDER+1] [ORDER+1]; unsigned int master[ORDER+1] [ORDER+1]; unsigned int C[ORDER+1]; unsigned int R[ORDER+1]; unsigned int Q[ORDER+1]; -----------------------------------------------------------------------------
Die Funktionen mark() und inuse() werden viele Male aufgerufen und hier brauchen wir die schnellen direkten Lookups. Die mark()-Funktion ist etwas komplexer als die awk- und die originale C-Version, weil wir etwas herumspielen müssen. Die inuse()-Funktion ist jedoch sehr einfach.
-----------------------------------------------------------------------------
void mark(r,c,try, flag)
int r,c,try, flag;
{
unsigned bitmap = (1 << try) ;
int q = fregmap(r,c);
if (flag) {
Q[q] |= bitmap ;
R[r] |= bitmap ;
C[c] |= bitmap ;
}
else {
Q[q] &= ~bitmap ;
R[r] &= ~bitmap ;
C[c] &= ~bitmap ;
}
master[r][c] = flag ? try : 0 ;
}
int inuse(r,c,try)
int r,c,try;
{
int q = fregmap(r,c);
unsigned bitmap = 1 << try;
return ((R[r] | C[c] | Q[q]) & bitmap) ;
}
----------------------------------------------------------------------------- Die search()-Funktion bleibt gegenüber der awk-Version praktisch unverändert und ist identisch mit unserer ursprünglichen C-Version oben. Wir haben Information Hiding verwendet, um die Tatsache zu verbergen, dass die anderen Funktionen Bitmaps für die Suche verwenden.
Unterm Strich
Die Timing-Ergebnisse sind interessant. Beide C-Versionen sind für tausend Iterationen ausgelegt, da eine einzelne Iteration zu klein war, um zuverlässig zu messen. Auf unserem System erhalten wir für eine Beispieldatei im Durchschnitt folgende Ergebnisse:
- Ursprüngliches awk-Skript – echt:10,9 s, Benutzer:10,2 s
- Erste C-Version – 1000 Iterationen, real:21,2 s, Benutzer:19,7 s
- Zweite C-Version mit Bitmaps – 1000 Iterationen, real:16,4 s, Benutzer:15,1 s
Die ursprüngliche awk-Version ( solve.awk ) ist ungefähr 500x langsamer als die erste C-Version und vielleicht 675x langsamer als die Bitmap-Version (unter Verwendung der Benutzerzeiten).
Das awk-Skript war sicherlich für die meisten Zwecke schnell genug, und dies wird in realen Skripten oft der Fall sein. Wenn mehr Geschwindigkeit benötigt wird, kann awk immer noch als effektives Prototyping-Tool verwendet werden. Die Ähnlichkeit zu C in gewisser Weise macht es ziemlich einfach, in diese Sprache zu übersetzen, wenn die Notwendigkeit entsteht, was ein weiterer großer Vorteil für awk gegenüber den Alternativen ist. Sie können jedoch nicht immer davon ausgehen, dass es in C so viel besser sein wird. Dies war ein ziemlich CPU-intensives erfundenes Beispiel. Eine andere Sache ist die Textverarbeitung, wo awk wirklich glänzt.
Bei sorgfältiger Verwendung kann uns awk manchmal mit seiner Geschwindigkeit überraschen. Zum Beispiel ist die „etablierte Weisheit“, dass, wenn Sie etwas mit grep oder sed tun können, es schneller als awk sein wird. Nicht unbedingt wahr. Ein sed-Skript zum Analysieren von Protokollen wurde kürzlich durch eine in awk geschriebene Version ersetzt, die etwa 40-mal schneller und weitaus flexibler war. Dies macht einen großen Unterschied, wenn Protokolldateien im Wert von mehreren zehn oder hundert Gigabyte analysiert werden. Wenn Interesse besteht, wird es in einen zukünftigen Artikel aufgenommen.