===================================================================== SimpleSort V1.0 ===================================================================== (C) 1993/94 Helmut Neumann *DAS* Sortierprogramm für den Amiga 0. Nutzungsbedingungen ====================== Dieses Programm wird unter der Idee der Share-Ware angeboten, die Nutzung ist zu Test-Zwecken frei. Bei Gefallen und weitergehender Nutzung ist eine Gebühr von 10,- DM an mich zu entrichten. Ich kann natürlich eine Nutzung des Programm nicht kontrollieren, aber über Bugreports nicht registrierter Benutzer bin ich verständlicherweise nicht sehr erfreut. Es wird keine eingeschränkte Version des Programms zu Testzwecken geben, ich kann also nur an das Gewissen der Viel-Nutzer appellieren sich registrieren zu lassen. Ich übernehme keinerlei Garantie für Fehlerfreiheit des Programms. Die Anwendung dieses Programms kann die üblichen Fehler bis hin zu Verlust der Daten der Platte bei unglücklichen Abstürzen hervorrufen. Das Archiv darf ausschließlich mit der unveränderten Anleitung, der BUGREPORT.FORM, SimpleSort und SimpleSort020 weitergegen werden. Weitere Dateien haben im Archiv nichts zu suchen. Die Verursacher von .displaymes und anderen schwachsinnigen Texten werden mit Lindenstraße nicht unter 10 Folgen bestraft (mit Ton !!). 1. Einführung ============= 1.1. Das War :-( (Motivation) ----------------------------- Jeder der bislang den Dos-Befehl Sort benutzen mußte wird zweierlei festgestellt haben : Er braucht mindestens die Länge der Eingabedatei und er ist vor allem recht langsam. Zwischenzeitlich kamen mehrere Alternativen heraus, von denen llsort zwar schnell ist aber die doppelte (!) Länge der zu sortierenden Datei als zusammenhängenden Speicherblock braucht. Weiterhin gibt es noch avlsort, welches sich neben seines Mindestspeicherbedarfs (auch hier Länge der Eingabedatei) ebenso wie der Dos-Sort-Befehl durch extrem langsame IO-Routinen auszeichnet. Dies ist alles nicht befriedigend und spätestens bei allen Dateien die größer als der verfügbare Hauptspeicher sind wird die Sortierung entweder unmöglich oder extrem (!) langsam (wenn man den Umweg über eine virtuelle Speicherverwaltung geht). 1.2. Das Ist :-) ---------------- Nun ist die erste Version des Sortierers fertig, der all diese Nachteile ausbügelt. Hier die wichtigsten Features im Überblick : - Die Größe der sortierbaren Dateien ist lediglich durch den Plattenplatz beschränkt. - Der vom Sortierer zu benutzende Speicher kann genau vorgegeben werden. - Es werden ausgereifte Caching-Routinen eingesetzt, um die üblichen Nachteile bei Zeilenweisem Einlesen und Wegschreiben zu beheben. - Um ein vielfaches schneller als die bislang verfügbaren Sortierprogramme auf dem Amiga. - Das append odd-length problem wird zur Steigerung der IO-Geschwindigkeit erkannt und behoben. 2. Anwendung ============ 2.1 Programmaufruf ------------------ SimpleSort sortiert eine vorgegebene (ASCII-) Datei auf die Zieldatei. Die Syntax ist in der Minimal-Angabe Analog zu den bisherigen Sortierprogrammen und erfordert mindestens die Angabe des Namens der Eingabedatei und der Ausgabedatei : SimpleSort infile outfile 2.2 Optionen ------------ Zusätzlich sind zur Steuerung des Default-Verhaltens des Programm noch weitere Optionen vorgesehen, welche hinter dem Namen der Eingabe- und der Ausgabe-Datei angegeben werden können : -quiet Es werden sämtliche Ausgaben des Programms incl. der Copyright-Meldung unterdrückt. Ausgenommen hiervon sind Fehlermeldungen. -maxmem SimpleSort darf den ganzen Speicher abzüglich einer Reserve von 10 Prozent des momentanen Fastmems benutzen. -sloppy Diese Option ermöglicht die Sortierung von Binär-Dateien. Die Ausgabedatei kann hierbei eine geringfügig andere Länge haben. -outbufsize size Mit dieser Option kann man die Größe des Output-Buffers bestimmen. size wird als gewünschte Bytes aufgefaßt, ein Wert von weniger als 10000 Bytes ist nicht sinnvoll und wird (ohne Fehlermeldung) nicht akzeptiert. Default-Wert ist 256000 Bytes. -inbufsize size Mit dieser Option kann die Größe des Eingabepuffers festgelegt werden. 10 Prozent dieses Speichers gehen allerdings für das Array mit den Zeilennummern drauf. Als Default-Wert wird hier die Hälfte des momentan verfügbaren Fastmems genommen, oder wenn kein Fastmem verfuegbar ist (z.B. roher A1200) entsprechend das Chipmem. Es wird aber immer die Reserve berücksichtigt, das heißt wenn man mehr Speicher angibt als tatsächlich abzüglich der Reserve verfügbar ist, dann ist das auch kein Problem. -reserve size Diese Option bietet in Kombination mit -maxmem eine bequeme Möglichkeit eine Arbeitskonfiguration über den vom Programm zu belassenen freien Speicher zu definieren. Hierbei ist als Reserve ausschließlich Fastmem gemeint, hinzu kommt noch eventuell ;-) vorhandenes Chipmem, welches nach Möglichkeit gar nicht tangiert wird. 3. Interna =========== 3.1. (wie machen die das bloß :) -------------------------------- SimpleSort verhält sich bei Dateien die bequem ins Fastmem passen genau so wie die bisherigen Sortierprogramme, es ist nur um ein vielfaches schneller. Hierbei ist zu beachten, daß SimpleSort nicht (!) automatisch den maximal möglichen Speicher reserviert sondern immer die Hälfte. Wer mehr wünscht, und das kann manchmal bei der Sortierung von Dateien in einem Rutsch sinnvoll sein, der muß die Option -maxmem verwenden oder die Größe des zu benutzenden Speichers mit -inbufsize einstellen. Wenn nun aber Dateien sortiert werden müssen, welche leider länger sind als der verfügbare Speicher teilt simplesort diese in vorsortierte Teildateien auf. In einem zweiten Schritt (nach Meldung Phase 1 beendet) werden dann diese Einzeldateien nach dem Merge-Sort-Prinzip (sortieren von mehreren bereits vorsortierten Einzeldateien (Bändern)) zu einer neuen sortierten Datei. Hierbei machen sich besonders die Cache-Routinen besonders bemerkbar, ohne die das ganze doch ETWAS langsamer wäre, die HD-Lampe würde nur glimmen, die HD würde kräftig rappeln und die Gesamt-Performance wäre lausig. Die größte in der Testphase sortierte Datei war ein Logfile mit 66 MB Länge. Diese Datei wurde mit einer Hauptspeichernutzung von lediglich 1.5 MB in ca. 15 Minuten klaglos sortiert ! Der Nachteil des ganzen, wenn man überhaupt davon sprechen kann, ist daß man kurzfristig die zweifache Länge der zu sortierenden Datei auf der Zielplatte benötigt. Es wäre noch möglich eine Option einzubauen, die nach Abschluß der ersten Phase die Eingabedatei löscht, ich weiß aber nicht wie praxisgerecht dies wäre. 3.2. Was machen die bloß nicht :-( ---------------------------------- Tja, leider hat die Geschwindigkeit auch hier ihren Preis. SimpleSort ist kein vollständiger Ersatz des Dos-Sort. Es kennt zum Beispiel die Option Colstart nicht. Weiterhin sortiert SimpleSort schlicht nach den ASCII-Werten, was manchmal zu anderen Ergebnissen als die der bisherigen Sortierer führt. SimpleSort ist auch nicht Pipe-fähig, es lassen sich damit in der momentanen Version lediglich Dateien sortieren. 3.3. Known bugs :-(( -------------------- Es gibt einen Fehler im Quicksort (es wird der vom Compiler angebotene benutzt) der dazu führt daß dieser bei bestimmten Eingabekonfigurationen nicht terminiert. Dies hängt anscheinend von der Anzahl der zu sortierenden Zeilen und der Konsistenz der Daten ab. Ich hatte bisher zwar lediglich eine Beispieldatei finden können bei der sich dieses Verhalten zeigte (eine 4 MB lange Liste von einzelnen Wörtern), aber einmal ist einmal zuviel. Abhilfe schafft hier nur die Reduzierung des inbufsize, dann werden auch solche Dateien ordentlich sortiert. Sollte sich dieser Fehler in der Praxis in der realen Welt häufiger zeigen werde ich wohl den Quicksort selbst programmieren. Bei Dateien die nicht mit einem cr enden werden in der Zieldatei alle Zeichen danach abgeschnitten. 4. Nachwort (Shareware-Info) ============================ Die Entwicklung dieses Programms hat mich einige Arbeit gekostet. Ich bitte jeden dies bei Gefallen zu honorieren und die Gebühr zu entrichten. Eine Weiterentwicklung des ganzen ist auch von der Resonanz abhängig. Meine Bankverbindung lautet : Helmut Neumann Stadtsparkasse Aachen Blz. 39050000 Konto 16012726 Bei Übersendung des Geldes bitte eine Mail an mich zur Information. Bug-Reports bitte DETALLIERT (notfalls mit den verursachenden Dateien) an mich senden. Ich bitte auch am Anfang, wo sich wahrscheinlich einige DICKE Fehler zeigen, um sofortige Meldung derselben und um Meldung eigener Bedürfnisse. Dazu bitte die bugreport.form verwenden. Ich bin im Netz unter folgenden Adressen erreichbar : Z-Netz : helmutn@tron.gun.de Internet : helmutn@tron.gun.de Bis dann, Helmut.