Vb.76: Sortierprogramme

[Thomas Berger]

Bernhard Eversberg wrote:

> 
> Sortierprogramme
> ----------------

Zu GSORT einige Anmerkungen (und auch zum Sortieren von 
Allegro-Dateien unter UNIX):

I. Unter MS-DOS (8+3-Dateinamen!) ist die Dateigroesse von
GNU-Sort auf etwa 26MB beschraenkt: Dann naehert sich die
Anzahl der Temporaerdateien der kritischen Grenze von 1000,
wonach sie sich selber aufzufressen beginnen. (Kannibalismus
unter GNUs?)


II. Das GNU-Sortierprogramm (GSORT) kennt ja auch die 
Möglichkeit, nur nach bestimmten "Feldern" zu sortieren, 
und - was besonders interessant ist, aus vorsortierten 
Dateien von allen Datensätzen mit uebereinstimmenden Feldern 
nur jeweils einen auszugeben. Ich denke hierbei an Exporte 
aus Datenbanken, die durch Nachladen von Stammsaetzen 
moeglicherweise ziemlich viele Dubletten enthalten.

Das Allegro-Kategoriendezeichen 0 laesst sich dem 
GNU-Sortierprogramm aber nicht in der Kommandozeile mitteilen 
(wenigstens von mir nicht) und ausserdem stoert es auch dann, 
wenn man andere Zeichen als Feldtrennung definiert: Es wirkt 
wohl (C-Style!) stets als Zeichenkettenende. Die SUN-Variante 
des Sortierprogramms (heisst ebenfalls sort) reagiert sogar noch 
allergischer auf Zeichen 0.

Gluecklicherweise hat das Programm tr (TRansformieren) diese
Probleme nicht. Wenn Sie also eine Pipe (Befehlsverkettung) 
mit
tr \000 \013<infile | ... 
einleiten, so werden die Zeichen 0 in Zeichen 11 (dezimal)
umgewandelt, welche in Allegro-Datensaetzen nicht vorkommen
(sollten) und die Sortierung (Feldendezeichen moeglichst niedrig!)
nicht weiter stoeren.

So umgewandelte Datensaetze muessten sich mit jedem Sortierprogramm
(außer MS-DOS-SORT natuerlich) verarbeiten lassen, insbesondere
der Schalter -t ^K von GNU-Sort läßt sich jetzt einsetzen, aber
auch etwa das Programm awk, um einzelne Kategorien zu extrahieren.

Ist alles fertig, laesst sich die Angelegenheit mit 
... | tr \013 \000>outfile
wieder in Allegro-Daten zurueckverwandeln.

Folgende MS-DOS Stapeldatei sortiert und bereinigt Dubletten
anhand von uebereinstimmenden ersten drei Kategorien:

tr \000 \013 <%1 | gsort -s -t ^K +0 -3>%temp%\sort.tmp
gsort -t ^K -m -u +0 -3 %temp%\sort.tmp | tr \013 \000>%2
del %temp%\sort.tmp

(dabei ist ^K _ein_ Zeichen, CUT u. PASTE funktioniert hiermit
also nicht...)

> Beide Programme sind nach unseren Tests gleich schnell. Mag sein, dass
> ein Unterschied bei groesseren Dateien auftritt, aber so etwa bis
> 500K merkt man nichts.

Da möchte ich aber für die GNU-Programme eine Lanze brechen:
Ich habe nachgemessen und unter fuer Sortierungen optimalen
Bedingungen (drei Plattten benutzt) und auch unter weniger
optimalen Bedingungen festgestellt, dass (allerdings bei grossen
Dateien, vor ein paar Monaten habe ich es aber auch einmal mit
mittelgrossen probiert) GSORT etwa 1,6 mal schneller ist als 
ASORT (60000 Titelsaetze in 473 gegen 742 Sekunden).

Selbst die obige .BAT-Datei (bei meinen Tests wurden etwa 70%
der Datensaetze eliminiert) ist trotz der zusaetzlichen tr- und
gsort-Aufrufe noch etwa 1,2 mal schneller als ASORT, wobei ein
nachtraegliches Eliminieren der Dubletten meiner Schaetzung nach
mindestens zweimal langsamer als der gesamte Sortierlauf waere.

Auf einer RAMDISK habe ich 1000 Titel (ca. 460kB) mit GSORT
in 4,4 Sekunden, mit ASORT in 7,2 sortiert, hier ist der
Geschwindigkeitsvorteil von GSORT sogar noch ein Quentchen
groesser.

Zugegebenermassen habe ich einen langsamen Prozessor und eine
schnelle Platte. Andersherum betrachtet: Wer keine Unterschiede
misst, dessen Platte bremst vermutlich den Prozessor aus...

Viele Gruesse
Thomas Berger