Überlegungen zur Quicksort-Optimierung
Wednesday, 16. April 2008
Der Quicksort ist vom Prinzip schon sehr effektiv. Trotzdem kann er in natürlich optimiert werden, um den Wort-Case seltener eintreten zu lassen und die reale Performance zu erhöhen - nur wie? Welche Verfahren sind praktikabel, welche Kleinigkeiten kann man beachten?
Ich muss da selbst noch einiges lernen. Was mir aber bei meinen Versuchen bisher aufgefallen ist:
1. Kleinigkeiten nützen schon etwas. Wenn man nicht das mittlere Element als Pivot, sondern das linke oder das rechte wählt, dann kann man den jeweiligen Cursor auch links bzw. rechts vom Pivot ansetzen.
2. Noch eine Kleinigkeit: Beim Tauschen darauf achten, dass die zu tauschenden Elemente nicht sowieso schon gleich sind (evtl. ist das auch schlecht: kostet die Abfrage mehr Leistung als das unnötige Tauschen?)
3. Es gibt eine (relativ) naive Implementierung, bei der das linke, das mittlere und das rechte Element verglichen werden und der Mittelwert als Pivot gewählt wird. Wenn man die sowieso manuell betrachtet, kann man sie auch sortiert zurückschreiben: das kleinste nach links, das größte nach rechts, das Pivot in die Mitte.
Meinen bisherigen Tests nach hilft das enorm bei halbwegs geordneten Listen, schadet aber ein kleines bißchen bei komplett ungeordneten Zahlenabfolgen.
4. Wenn nur noch zwei Elemente in der zu sortierenden Liste sind, sollte das linke zum Pivot werden. Das kann aber natürlich auch eine Macke in meiner Implementation sein.
Noch testen will ich, wie es sich auswirkt, wenn man mehrere Threads nutzt und wie man das am besten anstellt.
Und sowieso: Ist es in der Realität nicht eher besser, auf die Kleinigkeiten zu verzichten und sich auf die Wahl eines guten Pivots zu beschränken, weil so Abfragen gespart werden - oder wiegen die gesparten Arrayzugriffe das wieder auf?
Trojaner in Arbeit
Tuesday, 15. April 2008
Zitat aus dem Spiegel: Der Präsident des Bundeskriminalamts (BKA), Jörg Ziercke, sagte, man arbeite derzeit "mit Hochdruck" an einer entsprechenden Software.
Hahaha. Einfach mal so einen plattformunabhängigen Trojaner aus dem Ärmel schütten. Lächerlich, unmöglich, naiv, dumm.
Was sind das für Menschen?
Zuallererst Bedrohungen für diesen Staat. Jedem daran beteiligten Beamten muss klar sein, dass er damit gegen seinen Diensteid verstößt.
Die kranke Tastatur
Monday, 14. April 2008
Meine Tastatur hat Schreibstörungen. Ich schätze, es ist ein psychisches Problem. Zuerst konnte ich im Bootloader Grub nichts auswählen, dann wollte kein Text im Terminal erscheinen. Hier jedoch funktioniert alles eindwandfrei, die Akkus sind also nicht leer.
Vielleicht verträgt sie sich ja nicht mit dem neuen Netzteil?
Das sind keine Leerzeichen
Monday, 14. April 2008
Gerade habe ich mich ein bißchen mit sed herumgeärgert. Ich wollte aus der Ausgabe von du -s alles ab den Leerzeichen entfernen. Die Ausgabe selbst sieht normalerweise so aus:
$ du -s temp
7496 temp
Die eigentliche Lösung um mehrere Leerzeichen zu entfernen wäre
du -s datei | sed 's/ *//g
und wollte einfach nicht funktionieren.
Warum? Ganz einfach: Das sind keine Leerzeichen. Das ist ein Tab.
du -s temp | sed 's/\t.*//g'
ging dann auch.
Sun plant freien Video-Codec
Monday, 14. April 2008
Es würde durchaus eine Verbesserung bedeuten, wenn in baldiger Zukunft der Formatdschungel gelichtet werden würde.
Als Linuxnutzer ist es immer wieder ärgerlich, wenn mal hier Flash spinnt, dort ein "echtes" Video gar nicht angezeigt wird, und dann wieder nur der Player so schlecht funktioniert, dass man das Video schließlich lieber doch nicht anschaut.
Absurderweise ist es auf meinem Hauptsystem (Dapper Drake) inzwischen am komfortabelsten, wenn die Videos als Flashvideos vorliegen. Bei normalen Formaten passiert es schonmal, dass erst das Video geladen wird, vollständig, danach der Player startet, dieser aber keinen Zugriff auf die vorher geladenen Daten bekommt und daher beim Abspielen nachlädt und ruckelt.
Gut, mit der neuen Leitung ist das auch kein ganz so gravierendes Problem mehr, aber die ZDF-Mediathek z.B. kann ich nicht nutzen.
Sicher wird hier auch durch die normale Verbesserung der Player einiges aufgefangen, mit Hardy wird es besser, aber solche Initiativen können den entscheidenden Unterschied bewirken.
Geek and Poke
Monday, 14. April 2008
Diesen Zeichner-Blog hab ich dank Dirks Logbuch gefunden. Jeden Tag ein neuer Cartoon, den teilweise nur Einwohner des Internets, teilweise nur Programmierer, verstehen dürften.
Pearls Before Breakfast
Thursday, 10. April 2008
Ich bin gerade über Anke Gröner zu diesem Artikel der Washington Post gelangt. Er hat mich total gefangen, man sollte ihn lesen. Absolut beeindruckend geschrieben, ziemlich bewegend, ohne dabei durch Überemotionalisierung abzuschrecken.
Arbeitsloser im Hungerstreik
Thursday, 10. April 2008
Mit Arbeitslosen kann man es ja machen. Illegal das Geld zum Leben kürzen, sie schikanieren. So passierte es dem Gütersloher Bernd Pfeifer. In der Telepolis steht ein vollständiger Artikel über seinen 6-wöchigen Hungerstreik. Einfach nur entsetzlich, was für Auswirkungen diese Hartz-4-"Reform" hat: Sie kostet Menschenleben.
Eigentlich war das aber schon im Voraus klar. Was soll man mit Menschen auch anfangen, die der Gesellschaft nichts nützen? Deser Gedanke spricht aus all den Maßnahmen. Sie ins gesellschaftliche Abseits drängen, entmündigen und enteignen, als Zwangsarbeiter nutzen, ins Existenzminimum zwängen, wenn denn Existenz überhaupt sein muss.
Dieses System ist jeder Demokratie unwürdig, es ist dem Grundgesetz unwürdig, es widerspricht ihm sogar. Nur ist das irrelevant, wenn man in einem Land lebt, das weder eine Demokratie ist noch das eigene Grundgesetz achtet.
Legends of Heroes angeschaut
Wednesday, 9. April 2008
Gestern bin ich über Legends of Heroes gestolpert. Es ist ein Fantasy-Rollenspiel mit interessanten Ideen.
So werden die Fähigkeiten bei Benutzung trainiert. Das ist zwar auch bei den Browserspielen nicht wirklich neu (bei echten Spielen sowieso nicht), aber doch eher selten so vollständig umgesetzt. Im mittlerweile von den Entwicklern aufgegebenen Evergore war das z.B. im Grunde auch so, nur konnte man dort Attributspunkte noch selbst verteilen.
Ansonsten scheint man sich stark an üblichen MMORPGS orientiert zu haben. Kämpfe, die fast automatisch ablaufen (PvP habe ich noch nicht getestet), Housing und Crafting integriert, und selbst die Oberfläche erinnert mehr an ein echtes Spiel als an eine Website. Das schaffen wenige Browsergames.
Schön auch, wie mit der Motivation gespielt wird. Man kann seinen Charakter für acht Stunden arbeiten schicken, hat aber ansonsten zumindestens am Anfang keinen Zeitdruck - das wirkt äußerst entspannend, besonders im Vergleich zu Zeitfressern wie Travian.
Macken gibt es natürlich auch, nicht nur, dass ich das klassischen Fantasy-Szenario nicht mehr sehen mag (immerhin liefen mir noch keine Elfen über den Weg).
Das Spiel wirkt einfach noch etwas unfertig, besonders im Balancing, z.B. bei den Werten der Gegenstände. Daran knabbern eher die Kämpfer, Handwerker dagegen beschweren sich darüber, dass sie nicht genügend Gold verdienen würden.
Auch das Kämpfen ist eigenartig. Wie oben erwähnt läuft der Kampf gegen Monster automatisch ab, man kann aber eingreifen und sich heilen. Bisher war es jedoch so, dass ich immer nur getroffen wurde, wenn auch ich das Monster traf. Das dürfte also auch noch verbesserungsbedürftig sein.
Und ich fürchte ja, dass die Langzeitmotivation eher schwach ist. Andererseits kann ich das noch nicht wirklich beurteilen.
FDP will weiter Kinderzimmer abzocken
Tuesday, 8. April 2008
Deutschland hat ja noch weitere Besonderheiten. Zum Beispiel gibt es die kostenpflichtige Erstabmahnung, dank der ganze Anwaltshorden ihren Lebensunterhalt bestreiten. Und zwar auch an Leuten, die sich ein Musikstück aus dem Internet laden, und an Leuten, die sich keines Fehlers bewußt sind, z.B. bei der wackeligen Impressumspflicht. Die Musiklader sollen dann schnell mal tausende Euro zahlen, während der Verkaufswert bei 12.99€ liegt - davon bekommt dann ein Teil die Industrie und ein Teil der Anwalt.
Solche kriminellen Machenschaften durch eine Begrenzung der Abmahngebühren zu unterbinden, ist laut FDP-Aussage "populistisch und systemwidrig". Ein äußerst schützenswertes System, in der Tat.
Ist den Herren eigentlich nicht klar, dass es die einzige Chance der Partei wäre, Position für Bürgerrechte zu beziehen? Stattdessen wird fröhlich mitgemacht beim Überwachungsstaat-bauen, und noch dazu werden wie hier (gefühlt) immer die Industrieinteressen unterstützt. Beides gegen die eigene Bevölkerung, damit gegen die eigenen potentiellen Wähler.
Wär ich da nicht bewußt nicht eingetreten, müsste ich nun austreten.
Peinliche Werbung
Monday, 7. April 2008
Es gibt einen Trend im deutschen Fernsehen: Den Trend zur schlechten Werbung.
Wann begann das eigentlich? Ich meine, es war zur Zeit der Fußball-WM, in der passend zur grotesken Patriotismus-Welle in einem Bericht oder einem Interview prophezeit wurde, dass das Auswirkungen haben werde. Nicht nur im provinziellen Bereich an sich, also dass die einzelnen Regionen der Globalisierung zum Trotz ihre regionalen Besonderheiten verstärkt pflegen und präsentieren werden. Nein, auch deutschlandweit werde man das beobachten können, z.B. in der Werbung, in der in Zukunft verstärkt deutscher Gesang samt plattem Text und kleinbürgerlichem Kitsch auftauchen werden.
Und so grausam es auch ist, so kam es (ganz zu schweigen von den ganzen Volksverdummungs-"Ich fühl mich besser mit X"-Dingern, die anscheinend die nationalstolzen hirnverlustigen Gefühlsdeutschen ansprechen sollen) - und hält bis jetzt an. Trauriger Höhepunkt derzeit ist die Iglowerbung mit dem "Love is in the Air"-Frauengesang, toll platziert in den Werbepausen aller Sendungen, die ich ab und an gucke.
Fast ebenso bezaubernd, wenn auch etwas älter, ist der Gesang des Jungen aus der Gelbe-Seiten-Werbung, der statt des Auslösens des "guten Gefühls" die Haare zu Berge stehen lässt. Kein Wunder bei Ergüssen wie:
"Und ich hab da ein gutes Gefühl.
Die Gelben Seiten kennen sich aus.
Gelbe Seiten gehör'n
gehör'n in jedes Haus"
Die Obiwerbung ist genauso platt, aber nimmt sich dabei wenigstens nicht ganz so ernst, find ich also wiederum (noch) lustig.
Insgesamt ist diese Bewegung peinlich und sorgt dafür, dass ich immer öfter während des Fernsehkonsums den Ton ausstellen muss - und dann nicht mitbekomme, wenn der Film weitergeht. Und tolle Werbung verpasse, z.B. Hornbachs (post?)materialistische Selbstfindung. Das ist die schlechte Seite.
Die gute Seite ist, dass ich nun schon zwei Produkte mehr habe, die ich bewußt nicht kaufen werde, und es werden sicher noch mehr.
Das erleichtert die Auswahl im Supermarkt.
Arsenvergiftungen in Bangladesch
Monday, 7. April 2008
Es ist gar nicht so simpel, aktuelle Informationen über die Massenvergiftung in Bangladesch zu finden. Vorläufiges Ergebnis: Laut meinen Informationen ist diese Filteraktion noch nicht erfolgreich beendet.
Es würden noch 100.000€ fehlen.
Krieg?
Wednesday, 2. April 2008
Gerade hört man entfernten Flugzeuglärm, gleichzeitig heult eine Sirene lautstark vor sich hin. Vermittelt irgendwie ein seltsam bekanntes Gefühl.
Der Medienkonsum hinterlässt Spuren.
Das Telekomdesaster
Tuesday, 1. April 2008
Bei der Familie, bei der ich normalerweise meine Wochenenden verbringe, wollte man Geld sparen und gleichzeitig etwas davon haben. In aller Eile wurde das Telekom Triple Play Angebot bestellt: Telefon, Fernsehen und Internet sollte fortan über die Telekom laufen.
Telekomtypisch lesen sich die folgenden Geschehnisse wie ein absurdes Theaterstück.
Bestellt wurde im Dezember. Kurz vor den Weihnachtsfeiertagen wurde die Leitung umgestellt, ergo blieb das Internet aus. Denn der vorhandene Router verkraftet die schnelle Leitung nicht, die neue Hardware war aber noch gar nicht da. Kurz vor Sylvester wurde dann gnädigerweise die alte Leitung reaktiviert, man müsse halt auf die Hardware warten.
Die kam vor ein paar Tagen, also Ende März. Das Zwischenspiel habe ich nicht in allen Details mitbekommen, aber es wurde wohl letztlich mit Vertragsrücktritt gedroht, vorher der Hardwareversand seitens der Telekom storniert (warum?), das volle Programm eben - ob in der Zwischenzeit der neue Preis abgebucht wurde, weiß ich nicht.
Ich hab die Hardware dann angeschlossen, also erstmal nur das Modem und den Router. Da tat sich nur nichts, egal ob mit automatischer oder mit manueller Konfiguration. Ein Anruf später wurde mir gesagt, dass die Leitung erst am Montag (also heute), um 18 Uhr umgestellt werde, vorher könne es nicht klappen. Schön, dass das so frühzeitig mitgeteilt wurde.
Das Ganze hat noch einen grundsätzlichen Haken, den ich erst entdeckte, als ich die Fernseher schonmal vorbereiten wollte. Die Familie hat nämlich zwei Fernseher. An den Router kann man aber wohl nur den einen Festplattenrecorder anschließen. Ein Festplattenrecorder (der gleichzeitig Receiver ist) für einen Fernseher. Der zweite Fernseher, zwei Stockwerke über dem ersten aufgebaut, kann damit also nicht betrieben werden. Dies bestätigte auch ein Anruf bei der Telekom (ich bin froh, dass ich den nicht selbst tätigen musste).
Mit Geld sparen ist also erstmal nichts, als fünfköpfige Familie mit (teils) erwachsenen Kindern ist ein Fernseher zu wenig, der Streit um ihn zu stressig. Das prophezeie ich zumindestens, der Hausherr selbst hat das noch nicht erkannt.
Noch dazu liegt nun ein Kabel durch die Wohnung, vom Router zum Fernseher (übrigens ist das beigelegte Kabel zu kurz, um es ordnungsgemäß hinter den Schränken entlangzuführen. Gut, dass jeder weiß, dass man einfach eine normales Lan-Kabel kaufen und dafür nutzen kann). Der Router kann zwar W-Lan, der Festplattenrecorder aber nicht (wer in Deutschland hat auch nicht den PC direkt neben dem Fernseher stehen?)
Das Angebot ist also durchweg ungeeignet: Jede Umstellung bedeutet, zumindestens meiner Erfahrung nach, Ärger mit der Telekom, die schlankgesparte Serviceabteilung ist zu besserem wohl nicht fähig. Gleichzeitig geht schon das Angebot selbst an den Bedürfnissen des Großteils der anvisierten Kunden vorbei, denn der Großteil der deutschen Familien, die an einem solchen Angebot Interesse haben könnten, haben mehr als einen Fernseher. Schön auch, wie prominent dieses Manko auf der Angebotsseite vermerkt ist, ich zumindestens sehe es nirgends.
Aber es ist fraglich, ob die Familie, von deren Erlebnissen ich hier berichte, sich je konkret damit herumärgern muss. Um 17:56 funktionierte in deren Haus nämlich kein Internet mehr.
PS: Ja. es ist durchaus möglich, dass nur die automatische Konfiguration nicht funktioniert. Die Erfahrung dort mit solchen Dingen ist begrenzt, und ich bin nicht vor Ort. Aber das sehen wir ja bald.
Update: Inzwischen funktioniert die Internetanbindung dort wieder, dieser Teil der Kritik war also unberechtigt.