Stephan Lamprecht postet über Vivisimo, eine Metasuchmaschine, die ihre Suchergebnisse in Clustern gruppiert. Hier die Zusatzinfo: Clusty ist das „Kunden“-Interface, Vivisimo ist laut FAQ eher für Geschäftskunden. Clusty biete auch Toolbars an (habe ich noch nicht ausprobiert). Clusty ist jedenfalls ein Abfrage wert, gerade wenn die zu erwartenden Treffer sehr unterschiedliche Themen ansprechen.
2005-10-21
2005-10-11
Fernsehkanäle und Sortieralgorithmen
Wir haben letztens unseren defekten Videorekorder durch einen neuen ersetzt. Nun stand ich vor dem Problem, alle Kanäle so einzuspeichern wie auf dem Fernseher. Ich habe mich dafür entschieden, einen automatischen Sendersuchlauf durchzuführen und dann mit der vorhandenen Funktion „2 Kanäle vertauschen“ alle Kanäle an ihren richtigen Platz zu bewegen.
Welcher Algorithmus ist hier der beste? Gegeben sei eine unsortierte Liste von Zahlen (die Zahl steht für die entgültige Senderplatzierung) sowie eine Vergleichsfunktion und eine Funktion zum Vertauschen von zwei Kanalplätzen. Gesucht ist der günstigste Algorithmus, um die Zahlen zu sortieren. Günstig meint minimal bzgl. der Summe der Distanzen, über die Kanäle vertauscht werden. Die Distanzen sind deshalb wichtig, weil ich auf der Fernbedienung entsprechend oft „vor“ bzw. „zurück“ drücken muss. Dies sollte minimal sein.
Die erste Idee ist natürlich, die klassischen Suchalgorithmen zu untersuchen. Ich bin nach Selection Sort vorgegangen. Quicksort fällt mir ein, weil dort auch Elemente vertauscht werden. Auch Bubble Sort nicht vergessen, weil dort nur benachbarte Elemente vertauscht werden, die Distanz also immer 1 ist.
Vielleicht gibt es einen anderen günstigen Algorithmus, weil wir hier ja Besonderheiten vorliegen haben: Gegeben ist eine Permutation von Zahlen 1 .. N, nicht eine beliebige Zahlenfolge.
Ich werde mal einige Untersuchungen durchführen und die Ergebnisse an dieser Stelle veröffentlichen.
Update 03.11.2005: Ich habe drei Algorithmen untersucht: BubbleSort, SelectionSort und QuickSort.
Den Standard-BubbleSort-Algorithmus habe modifiziert, s.d. die Liste vorwärt und rückwärts durchschritten wird – da die Distanz zwischen zwei Vertauschungen wichtig ist, hilft dies, diese Distanzen zu veringern.
Während ich SelectionSort aus dem Lehrbuch angewendet habe, ist meine Quicksort-Implementierung mit den „üblichen“ Optimierungen versehen: für kleine Teilmengen wird SelectionSort angewendet. Die Wahl des Pivot-Elementes ist einfach, da die Positionsnummer mit dem Wert zusammenfällt und damit immer der „mittlere“ Wert einer Liste genommen werden kann.
Zu den Ergebnissen: BubbleSort bleibt am wenigsten effizient. SelectionSort und QuickSort liefern sich ein Kopf-an-Kopf-Rennen, wobei es darauf ankommt, ab welcher Listenlänge QuickSort auf SelectionSort zurückfällt.
Wie folgendes Diagramm zeigt, „gewinnt“ BubbleSort gegen SelectionSort ziemlich unabhängig von der Anzahl der Kanäle: der durchschnittliche Rang beträgt 1,8 (Rang 1 für den Gewinner, Rang 2 für den Verlierer, bei 2000 zufälligen Kanalbelegungen).
Beim Rennen SelectionSort gegen QuickSort ist der Ausgang abhängig von der Anzahl der Kanäle sowie dem Schwellwert, ab dem Quicksort in SelectionSort übergeht. Mit zunehmender Anzahl von Kanälen wird Quicksort stärker, bei ca. 39 Kanälen gibt es im Mittel ein „Unentschieden“. Der Einfluss des genannten Schwellwertes läßt sich schlecht beschreiben. Das folgende Diagramm zeigt eine „Draufsicht“ auf ein 3D-Diagramm. Die X-Koordinate ist der genannte Schwellwert, die Y-Koordinate die Anzahl der Kanäle. Die Farbe kodiert den mittleren Rang. Alles „ab“ orange (und „höher“) stellt den Gewinn (im Mittel) für QuickSort dar. Die blaue Fläche rechts der Diagonale steht „keine Messung“, da dort der Schwellwert höher als die Hälfte der Anzahl der Kanäle liegt.
Es scheint also so zu sein, dass eine „Vorsortierung“ mittels Quicksort desto vorteilhafter ist, je größer die Anzahl der Kanäle.
Es bleibt die Frage, ob es einen anderen, günstigeren Algorithmus gibt.
Kommentare deaktiviert für Fernsehkanäle und Sortieralgorithmen
2005-10-07
Selbstdisziplin
Steve Pavlina hat eine Artikelserie über Selbstdisziplin geschrieben. Für ihn ist Selbstdisziplin die Fähigkeit, etwas zu tun (das man sich vorgenommen hat), unabhängig davon, wie man sich fühlt. Dies stimmt auch in etwa mit dem überein, was die deutsche Wikipedia dazu sagt.
In diesem Post gebe ich Pavlinas Grundgedanken wider und vergleiche mit dem, was ich im deutschsprachigen Web zum Thema Selbstdisziplin finde.
Selbstdisziplin ermöglicht also das Erreichen eines Ziels unabhängig von der momentanen emotionalen Verfassung und ich betrachte es daher als erstrebenswert.
Während im Wikipedia-Artikel und unter dem Stichwort Selbstdisziplin auf der Persönlichkeitsentwicklungsseite zeitzuleben im Wesentlichen nur auf Motivation verwiesen wird, gibt es für Pavlina viel mehr dazu zu sagen. Für ihn gibt es fünf Säulen der Selbstdisziplin :
- Akzeptanz
- Willenskraft
- Schwerstarbeit
- Fleiß
- Ausdauer
Akzeptanz bezieht sich auf das Setzen des Ziels, für dessen Erreichen Selbstdisziplin eingesetzt werden soll. Man müsse die Realität, d.h. die Grenzen der eigenen Möglichkeiten akzeptieren. Wenn ich völlig untrainiert bin, wird es mir auch mit der besten Selbstdisziplin der Welt gelingen, schon morgen einen Marathon in Weltbestzeit zu laufen. Realistisch wäre eher die Vollendung eines Marathons nach einem einjährigem Training.
Für die Entwicklung von Selbstdisziplin solle man – analog zum Sportraining – sein Ziel nahe an die Grenze des Machbaren setzen – so könne man Erfolg erleben, gleichzeitig Leistung fordern und – wie im Gewichtstraining – seine Selbstdisziplin stärken.
Willenskraft ist für mich der eigentliche Kern der Selbstdisziplin – sie ist es, die uns den „inneren Schweinehund“ besiegen und an dem gesetzen Ziel arbeiten läßt. Pavlina meint allerdings, dass Willenskraft nicht über einen längeren Zeitraum aufrecht erhalten werden kann. Daher rät er dazu, ein Problem nicht direkt mit der Willenskraft anzugehen, sondern die Umwelt mit Hilfe der Energie aus der Willenskraft so zu verändern, dass Umsetzung der Problemlösung soweit vereinfacht wird, dass sie auch ohne permanente Willenskraft umsetzbar ist. Als Beispiel nennt Pavlina eine Diät: statt ständig mittels Willenskraft ungesundem Essen zu widerstehen, solle man die Willenskraft dazu benutzen, das Umfeld zu verändern: genügend gesunde Lebensmittel einkaufen, Essen vorkochen (um es bei Appetit schnell zuzubereiten zu können und nicht Fast Food zu verfallen), sich bei Weight Watchers anzumelden und die Diät-Unterlagen abzuholen etc. Diese Vorbereitung soll es dann im Alltag erleichtern, sich gesund zu ernähren.
Ich finde diese Beobachtung bemerkenswert. Ob man allerdings immer herausfindet, wie man das Umfeld in seinem Sinne verändern kann, sei dahingestellt.
Pavlina schlägt einen 3-Punkte-Plan zur Einsetzung der Willenskraft vor:
- Ziel bestimmen
- Angriffsplan ausarbeiten
- Zuschlagen
Während die Punkte 1 und 2 ruhig etwas längern dauern können, muss Punkt 3, der die eigentliche Willenskraft benötigt,
zügig erfolgen, sonst ist die Willenskraft erschöpft, bevor der Angriffsplan „abgearbeitet“ ist.
Schwerstarbeit. Pavlina definiert Schwerstarbeit (hard work) als etwas, das Dich herausfordert. Hier bezieht er sich darauf, dass der schwere Weg dem leichten vorzuziehen ist, denn da der leichte Weg bereits von vielen beschritten wurde bzw. wird, ist auf dem schweren eher ein Blumentopf zu gewinnen. Das gilt nicht nur für die Arbeit / das Kommerzielle: Pavlina bemerkt, dass
eine glückliche Beziehung haben Schwerstarbeit ist, ebenso Kinder großziehen, Ziele setzen, Pläne machen und verfolgen, gesund leben etc. All das ist Schwerstarbeit. Sie zahle sich aus: je tiefer man graben kann, desto mehr kann man – potentiell – finden, meint Pavlina.
Fleiß bezieht Pavlina auf die tägliche Arbeit oder allgemeiner der sich wiederholenden Arbeit vom Abwaschen bis zur Steuererklärung. Diese Arbeiten konzentriert und zügig durchzuführen bringe mehr Zeit für die wesentlichen Dinge des Lebens.
Ausdauer meint Durchhalten, solange dies sinnvoll ist – auch wenn die Motivation schwankt. Ausdauer erbringe Resultate und Resultate Motivation, was wiederum die Ausdauer fördere. Eine positive Feedbackschleife also. Wann ist es aber sinnvoll, aufzuhören statt durchzuhalten? Wenn das Ziel nicht mehr „stimmt“, für das man Selbstdisziplin und Ausdauer einsetzt. Wenn man sich neue Ziele setzt, muß man oft wohl oder übel alte Ziele aufgeben, weil sie nicht mehr aktuell sind und nicht mehr zur Lebensvision passen.
Zusammenfassend meine ich, dass Willenskraft und Ausdauer Selbstdisziplin im engeren Sinne umschreiben. Nimmt man das „Ziele setzen“ ebenfalls zur Selbstdisziplin (wie etwa im Buch „Selbstdisziplin“ von Marc Stollreiter und Johannes Völgyfy), dann gehört auch Akzeptanz dazu – obwohl ich das eher unter dem allgemeinen Begriff „Selbstmanagement“ fassen würde. Schwerstarbeit und Fleiß sind für mich Anwendungsgebiete von Selbstdisziplin.
Bei blueprints.de gibt es einen Artikel über Selbstdisziplin mit durchaus nützlichen kleinen Tipps: Ziele setzen und konsequent verfolgen, Fakten schaffen („ins kalte Wasser springen – da muss man schwimmen“), Planen und Belohnen.
Das war’s dann auch schon im deutschsprachigen Web zum Thema Selbstdisziplin. Ansonsten finde ich nur „man braucht für XYZ Selbstdisziplin“, „mir mangelt es an Selbstdisziplin“ etc.
Und Bücher? Hm. Mal schauen: „Simplify your life“ von W. Küstenmacher hat keinen Eintrag „Selbstdisziplin“ im Index. Das Bumerang Prinzip“ vom Zeitmanamgenent-Papst Seifert hat auch keinen Eintrag – schreibt dafür über Faulheit. Aha, vor lauter Selbstdisziplin also nicht vergessen, die Seele auch mal baumeln zu lassen! 🙂
Kommentare deaktiviert für Selbstdisziplin