Hadmut Danisch

Ansichten eines Informatikers

Was genau sind eigentlich “Ordnung” und Sortieralgorithmen?

Hadmut
25.7.2007 23:36

Ich habe kürzlich eine beruflich bedingte Zweitwohnung aufgelöst. Unglaublich, wieviel Zeugs sich bei doppelter Haushaltsführung so im Lauf der Zeit ansammelt. Obwohl die aufgelöste Wohnung viel kleiner als die andere war, und ich keine Möbel zurücktransportiert habe, war die andere Wohnung erst einmal mit Krempel vollgestellt. Es hat mich einige Zeit gekostet, den ganzen Krempel man durchzusortieren, auszumisten, aufzuräumen. Das zu tun, was man so gemeinhin als “Ordnung schaffen” bezeichnet.

Dabei sind mir als Informatiker ständig Überlegungen durch den Kopf gegangen, was Ordnung eigentlich genau ist, und welche Parallelen und Unterschiede es zwischen dem “ordnen” (sortieren?) von Daten oder Informationen und dem Aufräumen einer Wohnung gibt – und was denn das ordnen genau ist.

Als Informatiker kommt einem zunächst einmal der Begriff der Sortieralgorithmen in den Sinn. Quicksort, Heapsort und solche Verfahren. Kann man eine Wohnung nach dem Quicksort oder Heapsort aufräumen?

Die erste Überlegung ist, daß man es im Prinzip kann. Erst einmal alles aus den Umzugskartons zu holen, in die jeweiligen Zimmer zu tragen und dann jedes Zimmer für sich aufzuräumen, indem man wiederum verschiedene Dinge in verschiedene Schubladen, Schränke und Kästen verteilt, die es dann wiederrum aufzuräumen gilt, ist ja nichts anderes als der alte Divide-and-Conquer Ansatz zur Rekursion, also die Quicksort-Strategie. Wirklich?

Nein, ist es nicht. Denn das Aufräumen des Krempels in der Wohnung – da die Schuhe, dort die Socken, hier die Unterhosen, oder eben da die Bücher, dort die Computerteile, hier das Büromaterial usw. – ist eigentlich das gruppieren von Gegenständen nach deren Art und Gattung, eben nach deren Sorte, also ein Sortiervorgang. Deshalb heißen die unterschiedlichen Devisenwährungen in der Bank auch Sorten, und ein “gut sortierter” Laden ist nicht ein aufgeräumter, sondern einer mit einem umfangreichen und vollständigen Angebot unterschiedlicher Artikel. Also ist das, was ich in der Wohnung gemacht habe, eine Art des Sortierens.

Machen Sortieralgorithmen wie Quicksort & Co. das auch? Nein, machen sie nicht.Sie gruppieren nicht Objekte nach Sorten, sondern ordnen Objekte ein und derselben Art nach einem Ordnungskriterium an. Zahlen, Strings und solches Zeug. Aber immer nur entweder Objekte derselben Art. Also sind die Algorithmen, die seit Jahrzehnten in der Informatik als Sortieralgorithmen bezeichnet werden, keine Sortier- sondern Ordnungsalgorithmen. Wieder mal eine Art des Wissenschaftsgeplappers, das kaum einer nachprüft. Einer plapperts vor, alle plappern es nach.

Gut, bleiben wir beim Schaffen von Ordnung bei realen Gegenständen am Beispiel einer Wohnung. Was genau versteht man darunter?

Es wäre plausibel, im allgemeinen Sprachgebrauch darunter auch alle die Tätigkeiten mit anzusehen, die mittelbar dem Herstellen einer Ordnung zuträglich sind, also reparieren, reinigen, nachkaufen, wegwerfen.
Zum Zweck der Diskussion schränke ich das jetzt aber mal so ein, daß weder die Gegenstände, noch die Gegenstandsmenge verändert werden. Wir befinden uns einfach nur in einer Wohnung voller Gegenstände, in der es Ordnung zu schaffen gilt. Was machen wir also nun? Wie fassen wir das in Worte, was wir tun?

Eine einheitliche algorithmische Beschreibung scheitert daran, daß es ganz unterschiedliche Vorgehensweisen gibt. Mir ist aufgefallen, daß ich in der kleinen Wohnung ganz anders vorgegangen bin als in der großen. Gemeinsam war den Vorgehensweisen nur, daß sie auf eine Optimierung hinausliefen. Aber Optimierungen mit unterschiedlichen Zielfunktionen:

Minimierung des Volumens
Gerade in der kleinen Wohnung habe ich mein Ordnungsverhalten – mehr oder weniger unbewußt – danach ausgerichtet, möglichst wenig Platz zu vergeuden, Dinge also möglichst dicht zu packen. In gewisser Weise ein Kompressionsverfahren. Und wie bei Kompressionsverfahren hat das dazu geführt, daß den genauen Überblick über die Gegenstände verloren habe und es teilweise aufwändig war, einen bestimmten Gegenstand herauszuholen.
Minimierung der Suchzeit
Wie finden wir einen gesuchten Gegenstand in kürzester Zeit? Dazu würde beispielsweise auch das alphabetische Ordnen nach Bezeichnern (CDs, Videos, Bücher,..) gehören oder das Erstellen von Index-Informationen (Beschriften von Behältern usw.). So einfach wie sich das anhört, ist es nicht. Geht es um die maximale Suchzeit, also Suchen jedes beliebigen Gegenstandes? Oder um die mittlere Suchzeit, also mit stärkerer Betonung der häufiger gesuchten Gegenstände? Je öfter man etwas braucht, desto besser ordnet man es? Und wie vergleicht man überhaupt die Suchzeiten? Im Prinzip bräuchte man dafür ein Maschinenmodell, etwa eine Art Turingmaschine. Man gibt die Bezeichnung des Gegenstandes ein, läßt dessen Ortsangabe ausrechnen und zählt die Rechenschritte.
Minimierung der Zugriffszeit
Nur schnell zu wissen, wo etwas ist, reicht nicht. Manchmal muß man es auch schnell haben können. Beim Kochen ist es unsinnig, wenn man genau weiß, an welcher Stelle oben auf dem Schrank oder im Keller der Kochlöffel liegt. Die Fernbedienung zum Fernseher legt man auch nicht in den Keller in das Regal für Fernbedienungen. Und auch der Feuerlöscher ist da nicht gerade sinnvoll aufgeräumt. Die Aufgabenstellung ist also irgendwo auch mit Cache- und Storage-Algorithmen verwandt.

Das wirft eine wesentliche Frage auf: Muß ich dazu beispielsweise alle Schuhbürsten, Unterhosen, ISDN-Kabel aufräumen? Oder genügt es, wenn einige, eins oder wenige, am wohlgeordneten Platz sind? Würde man eine Wohnung als geordnet/ordentlich ansehen, wenn ich 5 Unterhosen in der Wäschekommode anordne und den Rest der Unterhosen beliebig in der Wohnung verteile, analog mit Gabeln, Zahnpasta, Kugelschreibern, Notizblöcken? Obwohl ich algorithmisch argumentieren kann, daß wenn ich etwas brauche, ich sofort weiß, wo ich zumindest einen der Gegenstände finde, würde wohl die Mehrzahl der Leser (jedenfalls die ohne Informatik-Ausbildung) der Ansicht nicht zustimme, daß die Wohnung ordentlich wäre.

Minimierung der Entropie
Man könnte sich das Aufräumen sparen, indem man alles da läßt, wo es ist, und es einfach nur präzise aufschreibt, sich also eine Liste der Orte aller Gegenstände schafft. Man könnte das größte Durcheinander ordnen, indem man alles in eine SQL-Datenbank mit Web-Frontend reinschreibt. Hauptsache, die Koordinaten sind eindeutig, präzise und im Zweifelsfall mindestens dreidimensional, unter dynamischen Umständen auch mit Berücksichtigung der Zeit-Komponente. Auch ein Informatiker-Ansatz. RFID-Technik könnte dabei nützlich sein und in dem Heimbereich Einzug finden. Wenn demnächst jeder Alltagsartikel, vor allem Kleidung wie geplant ein eingenähtes RFID-Tag hat, könnte man mit einem Scanner alle anwesenden Unterhosen katalogisieren. Es würde nebenbei die exzentrische Note unterstreichen.

Das ändert aber nichts daran, daß es wünschenswert ist, die Beschreibung kurzzu halten, damit man sie sich leicht merken kann. Anders gesagt: Das (Turing-)Programm, das zum Gegenstand den Ort ausgibt, möglichst kurz zu halten.

Ein extremes Beispiel hierfür: Bei der Bundeswehr mußte die Ausrüstung im Spind ganz exakt und besonders streng nach Vorschrift angeordnet sein, damit man sich im Alarmfall auch bei völliger Dunkelheit schnell anziehen und komplett aufrödeln kann. Ich gebe zu, ich habe mir das längst abgewöhnt.

Minimierung der Gesamtkosten
Man kann Ordnung freilich auch ganz nüchtern und leidenschaftslos als Minimierung der Gesamtkosten zum Ordnen, Aufbewahren, Suchen und Zugreifen ansehen.

Der Unterschied zu den anderen Optimierungsaufgaben ist, daß der Aufwand des Ordnens eine Rolle spielt, und das kann einen großen Unterschied machen, denn es kann durchaus sein, daß dem Aufwand des Ordnens kein adäquater Nutzen (=Einsparung beim Lagern, Suchen, Zugreifen) gegenübersteht. Es kann durchaus die billigste Variante sein, gar nichts zu ordnen und bei Bedarf zu Suchen (beispielsweise durch optische oder vollständige sequentielle Suche).

Das ist pädagogisch heikel, denn wenn die Eltern ihren Filius mal wieder tadeln und anweisen, er möge sein Zimmer in Ordnung bringen (wie es mir damals immer gesagt wurde), könnte es sein, daß sie damit falsch liegen, denn selbst wenn es darin aussieht, als hätte eine Bombe eingeschlagen, könnte dies bereits die optimale, weil insgesamt billigste Ordnung sein. So manches Kind findet sein Spielzeug am schnellsten und leichtesten, wenn es einfach alles auf dem Boden verteilt, während sich der Zeitverlust durch Aufräumen keinesfalls über Einsparungen durch effizienteres Spielen amortisiert.

Das heißt aber, daß beim Vergleich von Ordnungsverfahren stets das Verfahren gar nichts zu tun, berücksichtigt werden muß. So absurd, wie es sich anhört, ist es nicht, es handelt sich dabei nicht um ein degeneriertes Ordnungsverfahren. Im Gegenteil findet es häufig in Verbindung mit Divide-and-Conquer Anwendung, analog zum Hash-Verfahren in der Informatik: Man gibt Gegenstände einer gewissen Sorte oder Gattung in einen Behälter, den man nach einem der bekannten Ordnungsverfahren aufräumt, etwa indem man die Kisten ordnet und beschriftet. In der Kiste kann man aber durchaus einfach alles reinwerfen, weil dies keine Nachteile hat und ein Ordnung und Anordnen viel schwieriger, aufwändiger und damit teurer würde, als bei Bedarf eine vollständige Suche zu veranstalten. Beispielsweise habe ich Kisten mit ISDN-Kabeln oder Adaptersteckern für die seriellen Schnittstellen, in die einfach alles reingeworfen wurde. Bei Bedarf wird in der Kiste gesucht.

Minimierung von äußeren Einflüssen
Manchmal muß man Dinge so anordnen, daß irgendeine negative Wirkung ausbleibt (oder positive Wirkung eintritt). Textilien stauben unvermeidlich, es hat Vorteile, sie in einem separaten Zimmer zu lagern. Pflanzen brauchen Licht, solange sie leben. Werden sie erst einmal als Lebensmittel angesehen oder gar zu Saft und dergleichen transformiert, stellt man sie eher dunkel. Auch Hygiene spielt eine Rolle, man wird Lebensmittel nicht direkt auf dem Boden und auch nicht zusammen mit den Unterhosen in derselben Schublade lagern. Gewisse Dinge müssen so gelagert werden, daß sie dabei nicht kaputtgehen. Es sind also einfach gewisse äußere Randbedingungen einzuhalten.
Äußere Vorgaben
Wie hieß es im kleinen grünen Kaktus? “Bewahr’n Sie Ihren Kaktus gefälligst anderswo, Falleri, Fallera, Fallero!” Gewisse Dinge darf man nicht. Das Gewehr hat im Waffenschrank zu stehen, die Pornosammlung nicht im Kinderzimmer, und im steuerlich absetzbaren Arbeitszimmer vieles nicht, dafür die Buchführung.
Optisches Erscheinungsbild
Auch das Aussehen stellt eine Form der Ordnung dar. Normalerweise wird man eine Ordnung als “schön” ansehen, wenn sie gewisse regelmässige Muster erkennen läßt und damit gewisse neurologische Wirkungen im Sehbereich des Gehirns hervorruft. Das hat hier erstaunlicherweise wieder mehr mit Sortieren als mit Ordnen zu tun. Oftmals nehmen weibliche Mitbewohner hier gewaltigen Einfluß auf das Verfahren (etwa bei der Auswahl eines Wohnzimmer-PCs, aber das führt hier zu weit…).

Erstaunlicherweise können solche Anordnungen dem Suchen zuträglich sein, etwa wenn man optisch sucht, aber auch abträglich, wenn dadurch eine andere Ordnung gesucht wird.

Beispielsweise sieht ein Bücherregal viel ordentlicher aus, wenn man Bücher der Größe und/oder der Farbe und dem Erscheinungsbild nach ordnet. Das kann einerseits die thematische Ordnung völlig durcheinanderbringen und dazu führen, daß man nichts mehr findet. Es kann umgekehrt dazu führen, daß man ein Buch, dessen Aussehen man kennt, sogar schneller finden kann.

Ganz pervers: Mir ist zufällig mal aufgefallen, daß ein Bücherregal gleich viel ordentlicher und professioneller aussieht, wenn man alle Bücher zuerst ca. 1-2 cm über die Kante nach vorne raus zieht und sie dann alle gleichzeitig mit einer Holzleiste wieder bis exakt an die Vorderkante des Regalbretts zurückschiebt. Völlig beknackt, sieht aber sehr eindrucksvoll aus.

Soziale Wirkung
Man wird auch eine Einbindung in soziale Normen kaum verleugnen können. Wenn Freunde zu Besuch oder auch mal der Handwerker, der Schornsteinfeger oder der Heizungsableser kommt, möchte man natürlich, daß es “ordentlich” aussieht, was wohl – so genau weiß ich das auch nicht – eine Mischung aus optischer Erscheinung, Mode und gesellschaftlichen Normen (ist das Bad sauber?) darstellt.

Letztlich ist das Ordnen eine Mischung aus allen diesen Aspekten, in unterschiedlicher Mischung, je nach persönlichen Preferenzen. Oder eben der Größer der Wohnung.

Ein Kommentar (RSS-Feed)

Stefan
27.7.2007 3:40
Kommentarlink

Ein Problem das man in der Informatik seltener hat, ist der Rührlöffel, der in Schublade mit dem Besteck, in das Fach ‘Sonderwerkzeuge’ gehört, aber nicht reinpaßt.

Bei einer kleinen Elektrokram-Sammlung besonders häufig, die vielen kleinen und wenigen großen Teile, die auch in der Form stark abweichen, und sich schlecht ordnen lassen, so lange man von jedem Subtyp nur 1 oder 2 Exemplare hat.

3x habe ich begonnen das Problem Kabel naiv nach der Methode der spontanen Idee zu lösen.
Spontane Idee 1: Alle Kabel in eine Kiste.
Audio, Telefon/Modem, Strom- und Computerkabel in eine Kiste.

Das nächste Mal eine neue Idee: Audio zu Audio (mit Boxen, Kopfhörer, …) Strom zu Lampen und Schaltern, PC-Kabel zu Grafikkarten –

Es müßte symbolische Links aus der Audiokiste in die Kabelkiste geben, an denen man das Kabel herausziehen kann, so daß es scheinbar in zwei Kisten zugleich ist, in der einen aber keinen Platz beansprucht.

Ob ‘Sortieren’ so falsch ist möchte ich noch hinterfragen.
Wenn ich Bücher ordne, dann sortiere ich sie nicht nach Größe , Preis, Autor oder Buchrückenfarbe als RGB-Wert.
Da ich eine Ordnung herstelle darf ich das Ordnen nennen.
Andererseits wird das Zusammenstellen einheitlicher Objekte als ‘ordentlich’ bezeichnet – die Sprache läßt sich da einfach nicht festlegen.

Bezüglich der Suche kann es kontraproduktiv sein, alle Papiere in einheitlichen Ordnern abzulegen.
Das sieht hübsch ordentlich aus, aber wenn Versicherungen, Banksachen, Berufliches, Zeugnisse, … – alles im gleichen Orndertyp abgelegt ist, sieht es zwar ordentlich aus – finden läßt es sich leichter, wenn die Ordner unterschiedlicher Farbe sind.
Rechnungen 2001, 2002, 2003 wieder sind in einheitlichen Ordnern gut aufgehoben, solange die Ordner sortiert sind.

Dann gibt es das Problem, das ähnlich wie beim Rührlöffel ist: Ein Objekt gehört nicht nur dem Wesen nach zu einer Gruppe, sondern die Gruppe wird auch da gelagert, wo sie gebraucht wird, und neben der Frage, ob da auch genug Platz ist, stellt sich die Frage, ob das zu lagernde auch gelagert werden kann – kann es hängen, stehen, liegen?
Manche Sachen kann man an Haken hängen – andere nicht.
Zur Not kann man ein Loch bohren, oder eine Öse befestigen, um das Objekt so wie die anderen aufzuhängen.

Schlimm sind vorab entworfene Ordnungssysteme, die unflexibel sind.
Der Messerblock, der verhindert, daß man sich ein 7tes Messer kauft, der Gewürzständer für 16 Gewürze, der Kalender, der aufträgt an den 2 Tagen des Wochenendes nicht mehr zu tun, als an einem Werktag.

Die endgültige Lösung der Ordnungsfrage besteht aber in einem radikalen Just-in-time-Konzept: Man wirft alles sofort weg, und kauft bei Bedarf neu.
Für Dokumente ist das nicht praktikabel, und auch ansonsten sehr kostspielig.

Die fortgeschrittenste Technik mag in den wenigen Fällen hilfreich sein, in denen wir etwas suchen und suchen, aber fast alle Zugriffe des Alltags geschehen so rasch, daß jede Frage an die ‘intelligente’ Wohnung: “Wo ist das Käsemesser” zigfach länger dauert – ganz zu schweigen von Installation, Wartung, Training, Pflege und Unterhalt.