Skip to content

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.

Chemnitzer Linux-Tage 2009

Nun sind sie wieder vorbei, die Chemnitzer Linux-Tage. Zwei Tage als Linux-Familienfest.

Wie schon im letzten Jahr hatte ich auch dieses Jahr den Aufruf zum Einreichen von Vorträgen verpasst. Daher kam ich hauptsächlich als Besucher. Einige der Vorträge klangen recht interessant und so wollte ich die Zeit nutzen, um mir diese anzuhören und Ideen zu sammeln. Doch wie so oft kam alles ganz anders. Ich hielt mich sehr häufig außerhalb der Räume auf, traf eine Menge nette Leute und unterhielt mich über verschiedene Themen. Doch natürlich besuchte ich auch Vorträge (wenn auch meist nur zur Hälfte ;-)):

Notensatz mit Lilypond für den Hobbymusiker
Kurz nach meinem Eintreffen in Chemnitz hüpfte ich in diesem Vortrag. David Kastrup stellte das Notensatzsystem Lilypond vor. Das erste Beeindruckende war, dass Emacs auch PDF-Dokumente zeigen kann und zwar inline. David meinte später, dass das mit der aktuellen CVS-Variante (Emacs23) geht. Das PDF zeigte Noten zu Kalinka an und David spielte diese live auf seinem Akkordeon. Der Vortrag wurde immer mal wieder durch solche netten Einlagen unterbrochen. Auf diese Weise war er recht kurzweilig, auch wenn ich über Lilypond nahezu nichts lernte.
Die Telematik im Gesundheitswesen: Was läuft auf Linux in der Arztpraxis?
Ich erwartete von dem Vortrag ein paar Aussagen zu Linux in der Arztpraxis allgemein und eine Diskussion von Vor-/Nachteilen. Die Vortragende erzählte jedoch (zu) viele Details zur elektronischen Gesundheitskarte. So fasste ich recht schnell den Entschluss, die Räume wieder zu verlassen.
I2P - anonymous low latency mix network
Der Vortrag zu I2P interessierte mich natürlich besonders, u.a. deswegen weil ich mit dem Gedanken gespielt hatte, selbst einen zu dem Thema einzureichen. Lars gab einen kurzen Einblick in die Software und die Funktionsweise. Leider war die Zeit zu knapp bemessen, um auf mehr Details einzugehen oder ein praktisches Beispiel zu zeigen. Dennoch waren viele Zuhörer interessiert. Vielleicht konnte so der eine oder andere Nutzer gewonnen werden.
Die Rechtsprechung des Bundesverfassungsgerichts zum Datenschutz: Online-Durchsuchung, Vorratsdatenspeicherung etc.
Johannes Lichdi gab einen Überblick zu den Aufgaben des Bundesverfassungsgerichtes und zeigte anhand der in den letzten Jahren gefällten Entscheidungen, dass das Gericht keineswegs immer Gesetze kippt, sondern vielmehr die Anwendung verfassungsgemäß auslegt und anderweitig minimal eingreift. Sein Fazit war, dass wir das Bundesverfassungsgericht unbedingt zum Schutz der Grundrechte brauchen und auch selbst viel tun müssen. Als kleines Detail am Rande wurde die Broschüre Meine Daten gehören mir! Datenschutz im Alltag (lokale Kopie, PDF, 1,2MB) verteilt. Seite 6 verweist auf mein Buch Anonym im Netz. ;-)
Git verstehen und nutzen
Nachmittags wollte ich mir diesen Vortrag noch anhören und hoffte, etwas Neues zu git zu erfahren. Der Vortragende glänzte mit fast 80 Folien, welche im wesentlichen das Tutorial zu git beinhalteten. Hier wäre weniger mehr gewesen. Auf alle Fälle entstand durch den Vortrag bei mir der Plan, selbst einen Workshop oder Vortrag dazu zu machen. Die grundlegenden Ideen zum Ablauf des Ganzen habe ich auch schon im Kopf. Jetzt muss ich nur noch die nächste Linux-Veranstaltung abwarten ...
Quo vadis MySQL?
Wieder ein Vortrag, zu dem ich leider viel zu spät kam. Erkan Yanar gab einen guten Überblick zum MySQL-Universum. Ich würde mich sehr freuen, wenn den Vortrag später als Audio zum Nachhören gäbe.
Analyse und Visualisierung von Daten mit R
Leider war für mich auch dieser Vortrag ein Fehlschlag. Viele Folien und wenig Inhalt. Der Vortragende las viele Funktionen von GNU R vor und am Schluss gab es eine Demo. Diese Übersicht an Funktionen lässt sich auch von der Einführung zu R oder weitergehender Dokumentation gewinnen. Bei der Demo wiederum wurden verschiedene Befehle aufgerufen, ohne dass klar war, was da gemacht wird. Mir wäre lieber gewesen, wenn der Vortragende nach der Einführung kurz erwähnt hätte, dass beispielsweise sämtliche klassischen statistischen Funktionen in GNU R abgedeckt sind (Falls es welche gibt, Ausnahmen nennen). In einer Demo hätte ich mir dann ein kleines Beispiel gewünscht, wo kurz die Datenbasis erwähnt wird und dann später der Vortragende anhand einzelner Befehle die Funktionsweise erklärt. In dem Vortrag habe ich leider nichts von dem Programm mitgenommen. Weder wurde mein Interesse geweckt noch war ich abgestossen.
Verteiltes Suchen – Ein aktueller Überblick
Der letzte Vortrag bei den Chemnitzer Linux-Tagen handelte vom verteilten Suchen. Daniel Gultsch gab einen kurzen Überblick in das Suchen allgemein und stellte später einzelne Projekte (YaCy, Lucene, Wikia und weitere) vor. Dabei kam für mich heraus, dass nur YaCy eine verteilte Suchmaschine ist. Die meisten anderen Projekte decken nur Teilaspekte des Suchens ab. Dennoch scheint YaCy nichts für den normalen Desktop zu sein. Zum einen benötigt das Programm Unmengen an RAM (unter 512MB geht nichts), CPU und anderen Systemressourcen. Zum anderen gibt es nach Aussagen des Vortragenden keine Maßnahmen gegen das Abschalten eines Peers. Der Vortrag selbst gefiel mir gut. Jedoch glänzten die Folien durch Rechtschreibfehler. Würden die Chemnitzer Linux-Tage Preise für Fehler auf Folien verleihen, hätten diese den ersten Platz sicher. Das fand ich sehr schade, da es mich vom Vortrag ablenkte.

Bei vielen anderen Vorträgen hoffe ich, dass es später die Folien oder sogar die Audios gibt.

Liste mit
  Hashsummen
Jens beim
  Erklären

Am Samstagabend stand nun noch das Keysigning auf dem Programm. Ich hatte vorher die nebenstehenden Hashwerte ausgedruckt. Das sollte helfen, meine Stimme zu schonen und nicht alle Zahlen/Buchstaben durch die Halle brüllen zu müssen. Danach gab ich eine kurze Erklärung zum weiteren Ablauf und Sven bestand auf einem Gruppenfoto.

Schließlich hieß es Aufstellung nehmen. Wir hatten etwa 60 Teilnehmer mit fast 80 Schlüsseln. Ich machte den Anfang und wanderte von Teilnehmer zu Teilnehmer. Der Marsch ging sogar recht zügig. Denn viele hatte ich bereits unterschrieben. Auf dem untenstehenden Foto seht ihr einen Blick in die Menge:

Mir haben die Chemnitzer Linux-Tage in diesem Jahr wieder sehr viel Spass gemacht. Auch wenn die von mir gewählten Vorträge eher Mittelmaß waren. Dafür entschädigt die nette Atmosphäre und die perfekte Organisation. Für mich ist das wirklich wie ein Familientreffen der Linuxfreunde und ich freue mich schon auf nächstes Jahr.

Blick in die Runde der Teilnehmer

caff einrichten

Keysigning zur ApacheCon 2006

Das nächste Keysigning steht an und wieder einmal stellt sich für alle Teilnehmer die Frage, wie man am besten alle Schlüssel unterschreibt. Ich nutze dafür caff und will euch im folgenden kurz eine Einführung in die Konfiguration des Programmes geben. Hoffentlich hilft das, leichter und schneller zu Ergebnissen zu kommen.

Die Software gehört bei Debian und darauf basierenden Distributionen zum Umfang der Distribution und wird im Paket signing-party ausgeliefert. Andere Distributionen können die Dateien aus dem Subversion auschecken.

caff wird über die Datei .caffrc gesteuert. Im folgenden sind einige Einstellungen genauer erläutert. Dabei reichen meist die ersten vier oder fünf genannten Einstellungen, um caff zum Laufen zu bekommen.

$CONFIG{’owner’} = ‘Max Mustermann’;

$CONFIG{’email’} = ‘mm@example.org’;

$CONFIG{’keyid’} = [ qw{01234567890ABCDE} ];

In den beiden Variablen legt ihr euren Namen, E-Mail-Adresse und die Key-ID eures Schlüssels fest. In der letzten Einstellung kann auch eine Liste von Schlüsseln stehen. Die Key-ID bzw. den Fingerprint eures Schlüssels erhaltet ihr durch Eingabe des Befehls: gpg --fingerprint emailadresse.

$CONFIG{’mail-template’} = <<’EOM’
Text der E-Mail
EOM

Diese Variable trägt den Text der E-Mail, die an die Adressaten verschickt wird. Ihr könnt dort beliebigen Text reinschreiben und auch Variablen lassen sich expandieren. So wird {$owner} durch den oben festgelegten Namen ersetzt, {$key} steht für die Key-ID und {@uids} ist ein Array über alle UIDs. In der Beispieldatei, die mitgeliefert wird, findet ihr auch ein Beispiel zur Anwendung dieser Variablen.

$CONFIG{’mailer-send’} = [ ‘smtp’, Server => ‘mail.example.org’, Auth => [’mm’, ‘GehHeim’] ];

Wenn ihr einen lokalen Mailserver habt, dann ist die obige Einstellung nicht nötig. Sie betrifft vielmehr Anwender, die üblicherweise Programme wie Thunderbird, Evolution etc. nutzen und ohne lokalen Mailserver unterwegs sind. Dann hier muss caff wissen, wie es die E-Mails versenden soll. Meist wird zum Versand ein Smarthost des Providers genutzt. Der Name des Mailservers wird oben eingetragen und innerhalb der eckigen Klammern nach Auth kommen die Zugangsdaten (Benutzername und Passwort).

$CONFIG{’keyserver’} = ‘subkeys.pgp.net’;

Es könnte sein, dass ihr einen anderen Keyserver als den obigen standardmäßig eingestellten Nutzer wollt. Dann solltet ihr subkeys.pgp.net durch den Keyserver eurer Wahl ersetzen. Im Allgemeinen ist dieser aber eine gute Wahl.

Die Software bietet noch eine Vielzahl weiterer Möglichkeiten zur individuellen Steuerung. Diese sind in der Handbuchseite zu caff erklärt. Wie ihr oben schon gesehen habt, hat jede Option den Aufbau $CONFIG{’optionsname’} = ‘einstellung’;. So könnt ihr auch die weiteren in der Manpage genannten Optionen belegen.

Nachdem alle Einstellungen getroffen sind, kannst du dich ans Unterschreiben machen. Das Programm muss mit einer Liste von Key-IDs aufgerufen werden. Doch woher kommen diese? Ich stelle bei den Keysignings, die ich leite, am Ende einen Keyring aller Teilnehmer zur Verfügung. Das macht es einfach, die Key-IDs zu extrahieren:

gpg --no-default-keyring --keyring=KEYRINGDATEI --with-colons --list-keys \
 | awk -F: ‘/^pub/ { print $5 }’

Nun ruft ihr das Programm auf: caff -m yes -u 0x012345 KEYIDS. Die Variable -m steht dafür, die E-Mails ohne Nachfrage zu versenden. Es gibt vier Möglichkeiten, diese zu belegen und wer es will, kann die Einstellungen auch in der .caffrc treffen. Ich persönlich nutze hier lieber die Kommandozeile, um die Option zu übergeben. Mittels -u übergebt ihr die Key-ID eures eigenen Schlüssels. Auch diese Einstellung kann bereits in der .caffrc getroffen werden. Nach einem beherzten Druck auf die Entertaste geht die eigentliche Arbeit los. Ihr werdet Schlüssel für Schlüssel nach eurer Unterschrift gefragt und könnt unterschreiben.

Ich hoffe, diese Anleitung ist für Teilnehmer an einem Keysigning nützlich und hilft, den Aufwand auf ein Minimum zu reduzieren.

Foto von NoirinP.

CLT in einer Woche

In einer Woche ist das Warten wieder vorbei. Dann beginnen die Chemnitzer Linux-Tage. Zwei Tage mit spannenden Vorträgen und Workshops. Natürlich gibt es wieder eine Keysigningparty. Wenn ihr also Zeit habt und euch für Freie Software interessiert, dann ist ein Besuch in Chemnitz ein Muss. Ich wünsche allen Besuchern viel Spass.

Zur Einstimmung findet ihr bei Pro Linux ein Interview mit dem Orgateam.

tweetbackcheck