Skip to content

Der totale Overflow

Meine Anfänge im Internet gehen in das Jahr 1996 zurück. Vielleicht auch etwas eher. So genau weiß ich das nicht mehr. Damals versuchte ich das unbekannte Territorium ein wenig zu erobern. Da gab es so merkwürdig klingende Dienste wie Gopher, Archie oder Veronica. Das, was heute fälschlicherweise als das Internet bezeichnet wird, nämlich das WWW existierte ebenso wie ein Dienst namens Usenet. Das war und ist ein riesiges weltweites Diskussionsforum mit einzelnen Räumen, den Newsgroups oder Gruppen. Das Usenet ist hierarchisch aufgebaut.Beispielsweise gibt es eine deutschsprachige Hierarchie. Darunter gibt es Gebiete für Diskussionen um Computer, um Wissenschaft, um Erholung etc. Diese teilen sich dann weiter auf in Computerhardware oder Mathematik oder Kartenspiele. In den einzelnen Gruppen fanden in der Regel sehr wertvolle Diskussionen statt, es wurden sinnvolle Lösungen weitergegeben etc. Mit dem Aufkommen von Foren, Blogs und guten Suchmaschinen begann der Stern des Usenet zu sinken. Die Diskussionen verlagerten sich an andere Stellen und heute schließen diverse Firmen Newsserver. Die Schreiber der Gruppen gehen andere Wege.

Der große Vorteil des Usenet ist aus meiner Sicht die einfache Bedienung, die Qualität der Beiträge und das Offline-Archiv. Geschrieben und gelesen wird das Usenet in der Regel in einem Programm, dem Newsreader. Google Groups bietet ebenso eine Schnittstelle zum Usenet. Zum Verfassen eines Beitrages kann ich somit den Editor bedienen und seine Stärken ausnutzen. Damit lässt effektiv ein Beitrag verfassen. Dies lassen die Webforen vermissen. Beiträge müssen im Webbrowser verfasst werden. Der bringt in der Regel keine Unterstützung für erweiterte Funktionen (Abkürzungen, Ersetzen etc.) mit. Ein Problem der Webforen ist die Aufsplitterung. Stellt euch vor, ich habe ein Problem mit meinem imaginären Opel und suche nach einem Opel-Forum. Welches von den sechs Millionen Funden ist das Richtige? Im Usenet gab es die Gruppe de.etc.fahrzeug.auto. Dort fanden alle Diskussionen zu dem Thema statt. Die ließen sich herunterladen und, während man mit der Bahn unterwegs war, konnte man sich zu dem Problem mit dem Opel belesen. Wie geht das bei einem Webforum?

Der letztgenannte Punkt ist heute kein großes Problem, dank UMTS und WLAN. Die ungelösten Probleme sterben nicht aus und wenn ich mich auf die Suche nach einer Lösung begebe, stoße ich in letzter Zeit gehäuft auf Stackoverflow. Die Seite richtet sich vorrangig an Programmierer und fiel mir durch qualitativ hochwertige Antworten auf. Die Suchergebnisse sind dementsprechend bei Google immer recht weit oben gelistet.

Stackoverflow ist prinzipiell ein Webforum. Jedoch wählt es einen anderen Ansatz. Einerseits sind alle Beiträge für jedermann lesbar. Das steht im Gegensatz zu manchem Webforum, bei dem man sich erst anmelden muss, um Beiträge zu lesen. Wer macht das schon? Der Ansatz von Stackoverflow geht aber noch weiter. Jeder kann ohne Anmeldung auch Beiträge verfassen. Das heißt, Fragen stellen, kommentieren oder beantworten. Die Macher der Seite setzen hier auf die Weisheit der Massen. Um das Ganze ein wenig zu unterstützen, gibt es ein Bonussystem. Wer sich nämlich bei der Seite anmeldet, bekommt Bonuspunkte für gestellte Fragen, für Antworten und einiges mehr. Je mehr Punkte jemand besitzt, desto mehr Rechte bekommt er. Dieses Bonussystem wirkt sich nach meiner Beobachtung auf die Psyche aus. Wer alte Diskussionen aus dem Usenet kennt, der kennt RTFM und andere Abkürzungen, die einem Fragenden entgegengeworfen werden. Bei Stackoverflow herrscht hingegen eine weitgehend freundliche Atmosphäre. Antworten fallen schon einmal länger aus und enthalten Beispiele. Denn für eine gute Antwort bekommt der Antwortende Punkte. Jeder kann Fragen und Antworten bewerten und die Seite zeigt automatisch, die am besten bewerteten Antworten oben an. Das ist wiederum für den Suchenden sehr praktisch.

Innerhalb von Stackoverflow gibt es Tags, die zu Fragen vergeben werden. Diese stellen eine Art thematische Sortierung dar. Wer Fragen zu PHP, Haskell oder C++ stellen bzw. beantworten will, schaut sich den entsprechenden Tag an. Mehrere tausend Tags sind derzeit vergeben.

Nun stieß ich auf eine weitere Seite aus dem Stackoverflow-Universum, der Area51. Diese setzt eine weitere Idee aus dem Usenet um. Wer nämlich eine neue Diskussionsgruppe im Usenet errichten wollte, musste einen formalen Prozess aus verschiedenen Schritten durchlaufen. Das sollte sicherstellen, dass nicht sinnlos Gruppen für Partikularinteressen gegründet werden. Ähnlich ist Area51. Die Seite erlaubt wieder jedem einen Vorschlag für eine neue Seite einzubringen. Danach findet dazu eine Diskussion statt, d.h. andere müssen Beispielfragen bringen, die gut in das Thema passen würden. Andere diskutieren diese Fragen und vergeben Punkte, ob diese wirklich gute Fragen sind. Nach Abschluss des Prozesses werden Leute gesucht, die sich verpflichten für einen begrenzten Zeitraum Fragen zu beantworten. Kommen genügend Stimmen zusammen, so wird die Seite ins Leben gerufen. Das stellt sicher, dass hier nicht das n-te tote Forum im Web steht. Neben Stackoverflow kenne ich derzeit:

Serverfault
Eine Seite für Sysadmins
Superuser
Allgemeine Computerfragen
Meta
Meta-Fragen zur Seite selbst
Stackapps
Fragen zur Stack Exchange API
Cooking
Die Kochseite ist erst kürzlich der Area51 entsprungen und befindet sich jetzt in der Testphase.

Insgesamt macht es richtig Spass, auf den Seiten herumzustöbern, Fragen zu lesen und auch zu beantworten. Aus meiner Sicht müssen noch ein paar kleinere Usability-Schwächen behoben werden. Aber insgesamt kann ich die Seite nur empfehlen. Werft mal einen Blick und sagt mir eure Meinung. Ich bin gespannt!

Code optimieren

Erathostenes lehrt in Alexandria

Bislang konnte ich die Eulerschen Probleme mit einem naiven Programmieransatz lösen. Das heißt, die erste Idee, die mir in den Kopf kam, schrieb ich runter und bekam eine Lösung. Das zehnte Problem warf mir einen Stock zwischen die Beine. Erstmals musste ich mir Gedanken über die Optimierung des Codes machen.

Das zehnte Problem klingt erstmal ganz harmlos: Finden Sie die Summen aller Primzahlen, die kleiner als 2 000 000 sind.. Ha, das ist ja eine einfache Fingerübung:

sieb = [ i for i in xrange(2,2000000) ]
for i in xrange(2,2000000):
  for j in xrange(2,2000000):
    if i*j in sieb:
      sieb.remove(i*j)

Die Werte in sieb müssen dann nur noch addiert werden und fertig. Jedoch kam ich gar nicht soweit. Denn das Programm lief und lief und lief.

Zahlenkolonnen

Das brachte mich zum Nachdenken, woran das liegen könnte. Letztlich ist die Ursache offensichtlich. Denn der Code berechnet jedes Produkt. Dafür werden schon 2 000 000 * 2 000 000 = 4 000 000 000 000 Berechnungen durchgeführt. Wenn man von der (viel zu optimistischen) Variante ausgeht, dass jede Berechnung ein CPU-Zyklus ist, würde das Programm auf aktuellen Architekturen länger als eine halbe Stunde laufen. In der Realität lief es 15 Stunden. Wie lässt sich die Laufzeit nun verbessern?

Es ist recht offensichtlich, dass das Programm zuviel berechnet. Im ersten Schleifendurchlauf gibt es die Multiplikationen: 2*2, 2*3, 2*4, ..., 2*1999999 = 3999998. Beim zweiten Schleifendurchlauf: 3*2, 3*3, 3*4, ..., 3*1999999 = 5999997. Am klarsten fällt es im letzten Durchlauf auf: 1999999*2, 1999999*3, ..., 1999999*1999999 = 3999996000001. Die Berechnung 3*2 wurde schon im ersten Schritt (nur umgekehrt mit 2*3) durchgeführt. Hier wirkt das Kommutativgesetz. Also kann die Schleife im zweiten Durchlauf erst bei drei beginnen. Im dritten Durchlauf würde nach obigem Algorithmus 4*2, 4*3, 4*4 usw. berechnet werden. Verallgemeinert lässt sich also sagen, dass die Variable der zweiten Schleife genausogroß oder größer als die erste Variable sein muss. Dieser Schritt halbiert die Zahl der Berechnungen.

In der obigen Darstellung wird klar ersichtlich, dass das Programm nicht in jedem Fall bis zum Maximum von 2 000 000 laufen muss. Schon im ersten Durchlauf werden Werte über 2 000 000 berechnet. Das heißt, das Produkt i*j muss kleiner oder gleich 2 000 000 sein. Umformen nach j ergibt: j?2 000 000/i. Eine weitere oft genutzte Optimierung ist es, die erste Schleifenvariable nur bis ?2000000 laufen zu lassen.

Weiterhin fiel mir auch ein, dass man schon die initiale Liste nicht mit Zahlen von 2 bis 2 000 000 füllen muss. Denn es ist bekannt, dass alle Vielfachen von 2 sofort ausfallen. Man kann sogar soweit gehen, dass man nur Zahlen nach dem Muster 6*n-1 und 6*n+1 aufnimmt. Denn die Zahlen 6*n+0, 6*n+2 und 6*n+4 sind gerade und damit keine Primzahlen. Die Zahl 6*n+3 entspricht 3(2*n+1) und ist somit durch drei teilbar. Es verbleibt das obige Muster.

Theoretisch hätetn die obigen Anpassungen schon reichen sollen, um die Laufzeit unter eine Minute zu drücken. Jedoch lief das Programm immer nach weitaus länger. Nach einigem Stöbern fiel mir dann auf, dass in Python die Listenoperationen in und remove die Listen von Beginn an durchsuchen. Das bringt natürlich nochmal eine extreme Pessimierung der Laufzeit. Stattdessen sollte man hier Sets oder Dictionaries nutzen. Ich habe es mit Sets probiert und prompt lief das Programm schnell genug.

sieb = {}
for i in xrange(2, 2000000):
  sieb[i] = True
for x in xrange(2,int(math.sqrt(2000000))+1):
  if sieb[x] == True:
    for y in xrange(2000000/x, x-1,-1):
      t = x * y
      sieb[t] = False

Grundsätzlich lassen sich weitere Möglichkeiten der Optimierung ausdenken. Jedoch reichte mir das obige Ergebnis, um das Ziel zu erreichen. Wahrscheinlich benötige ich in späteren Aufgabe noch eine weitere Verbesserung.

Funktionale Programmierung -- Wo fange ich an?

Unter dem (englischen) Titel gibt es eine sehr schöne PDF-Datei mit einer Art Anleitung. Darin werden verschiedene Probleme vorgestellt und der Lösungsweg skizziert. Aus der Zusammenfassung:

This paper introduces a problem solving method for teaching functional programming, based on Polya’s `How To Solve It’, an introductory investigation of mathematical method. We first present the language independent version, and then show in particular how it applies to the development of programs in Haskell. The method is illustrated by a sequence of examples and a larger case study.

tweetbackcheck