Archive for Oktober 2008

h1

Benchmark regular Expressions

Oktober 31, 2008

Da ich schon vor kurzem einen Artikel über das Filtern von Text nach E-Mailadressen mithilfe von awk geschrieben habe, sind Charly und ich auf die Idee gekommen, zu vergleichen, welche Sprache oder welches Tool denn nun besser mit regulären Ausdrücken klarkommt. Dazu haben wir als Testobjekt eine Textdatei mit 720950 Zeilen genommen und haben mithilfe von regulären Ausdrücken alle E-Mailadressen aus der Datei gefiltert. Den Test haben wir mit awk, grep, Python und Perl durchgeführt.

Der Pythoncode:

#!/usr/bin/python
# Reads all lines from a file, validates email adresses
# as fast as it can
import re

file = open('sales10.txt')
pattern = re.compile('[-_.a-zA-Z0-9]*@[-a-zA-Z0-9]*\.[a-zA-Z]{2,9}')

for line in file.readlines():
  if(pattern.search(line)): pass;

Der grep-Befehl:

grep -c '[-_.a-zA-Z0-9]*@[-a-zA-Z0-9]*\.[a-zA-Z]\{2,9\}' sales10.txt

Damit grep nicht unötig lange ausgaben macht, die das Ergebnis erheblich verfälschen würden, verwende ich die Option -c, die nur am Ende die Anzahl der übereinstimmenden Zeilen ausgibt.

Das awk-Script:

{
    if ($0 ~ /[a-zA-Z\-_0-9\.]*@[a-zA-Z\-0-9]*\.[a-zA-Z]{2,9}/ )
    {
    }
}

Das Perlscript:

#!/usr/bin/perl -w

use strict;

while (<>) {
    if ( /[-_.a-zA-Z0-9]*@[-a-zA-Z0-9]*\.[a-zA-Z]{2,9}/ ) {
    }
}

Hier die Ergebnisse:

awk:       0m15.353s – 0m15.380s – 0m15.245s

Python:  0m5.091s – 0m4.986s – 0m4.994s

grep:      0m0.633s – 0m0.639s – 0m0.630s

Perl:       0m0.494s – 0m0.492s – 0m0.512s

Die Ergebnisse wurde mit dem Bashbefehl time ermittelt und sind von der schlechtesten zur besten Zeit sortiert. Erstaunlich ist vor allem, das grep nicht die besten Zeiten hat, obwohl es genau auf diese Aufgabe spezialisiert ist.

Advertisements
h1

Ubuntu Desktop wird nicht angezeigt (keine Symbole)

Oktober 31, 2008

Ab und an kommt es vor, dass auf dem Desktop keine Symbole  angezeigt werden. In diesem Fall ist das einfachste, den  XServer neu zu starten.

Dazu drückt man einfach:

Strg+Alt+Backspace

h1

Sortieralgorithmik in Python Teil2 – Selectionsort

Oktober 31, 2008

Heute werden wir uns geschwindikeitsmaßig ein wenig steigern, denn es folgt Selectionsort!

Doch zuerst einmal das Prinzip:

Man stelle sich vor S sei der sortierte Teil einer Liste und U der Unsortierte, deshalb ist bei einer unsortierten Sequenz der S Teil anfangs leer.
Beim Aufruf der Funktion wird nun das kleinste Element der Liste herausgesucht und an den Anfang gesetzt. So wird der Reihe nach die ganze Liste durchgelaufen, bis die Liste sortiert ist!

Hier ein Bild zum Verständnis des Prinzips:

Selectionsort

Selectionsort

Hier die Standardimplementation in Python inklusvie Zeitmessung und automatisch erzeugter Liste:

# SelectionSort Python
  2 import random
  3 import time
  4
  5 def selectionsort(seq):
  6     for k in range(len(seq) - 1):
  7         j = i = k
  8         for i in range(k, len(seq)):
  9             if seq[i] < seq[j]:
 10                 j = i
 11         seq[j], seq[k] = seq[k], seq[j]
 12     return seq
 13
 14 list = []
 15 for rand in range(100000):
 16         rand = random.randint(1,100000)
 17         list.append(rand)
 18
 19 zeit1 = time.clock()
 20 ausgabe = selectionsort(list)
 21 zeit2 = time.clock()
 22 print ausgabe
 23 print zeit2-zeit1,"s"

Benchmark:
1000 Datensätze : 130ms
10000 Datensätze : 12.81s
100000 Datensätze : 1749.96s

und Morgen: Mergesort..

h1

Sortieralgorithmik in Python – Teil1 Bubblesort

Oktober 29, 2008

Wie der Titel schon unschwer erkennen lässt, startet hiermit eine kleine Serie, die euch in die Sortieralgorithmen einführt.

Dabei wird jeden Tag ein Artikel mit einem Sortierverfahren veröffentlicht. Die Reihenfolge geht dabei von extrem langsam nach sehr schnell.

Wir starten heute mit einem der langsamsten Sortieralgorithmen überhaupt: Bubblesort

Funktionsweise:
Bubblesort ist ein stabiler Sortieralgorithmus
Es werden der Reihe nach benachbarte Elemente des zu sortierenden Objekts vertauscht. Dieser Vorgang wird solange wiederholt, bis die Liste komplett sortiert ist. Dazu benötigt man in der Regel mehrere Durchläufe.
Hier ein Bild zur verdeutlichung des Schemas: http://upload.wikimedia.org/wikipedia/commons/3/37/Bubble_sort_animation.gif

Implementierung in Python

#BubbleSort Python

def bubblesort(sequenz):

	durchlaeufe = len(sequenz)

	while durchlaeufe >= 1:

		for k in range(len(sequenz) - 1):

			if sequenz[k] > sequenz[k+1]:

				temp = sequenz[k]

				sequenz[k] = sequenz[k+1]

				sequenz[k+1] = temp

		durchlaeufe = durchlaeufe - 1

	return sequenz

Um nun damit auch etwas sortieren zu können, fügen wir noch folgenden Code zum erstellen einer Zufallsliste mit Zahlen hinzu:

import random
import time

und nach der Definition der Funktion

for rand in range(10000):

	rand = random.randint(1,10000)

	list.append(rand)

zeit1 = time.clock()

result = bubblesort(list)	

zeit2 = time.clock()

print result

print "Berechnungszeit: ",zeit2 - zeit1,"s"

Ich habe auch gleich noch eine kleine Zeitmessung für die Ausführung der Funktion mit eingefügt, damit wir das ganze später auch mit den andren Algorithmen vergleichen können.

Hier also eine kleines Benchmark:

100 Datensätze : 10ms
1000 Datensätze : 410ms
10000 Datensätze : 40.19 s
100000 Datensätze : Das hat einfach zu lange gedauert 😉 (über 15min)

Wer mehr über Bubblesort erfahren will: http://de.wikipedia.org/wiki/Bubblesort

Morgen kommt: Selectionsort…

h1

Bot für das Pennergame [3]

Oktober 28, 2008

Der dritte Teil des Pennergamebots sammelt von einem Account alle Links zu „Pennern“ ein, die ihm schon gespendet haben. Es gibt eine „Spendenstatistik“, auf der alle diese „Penner“ aufgeführt werden, dort muss man nur noch die Links herausfiltern und in eine Datei schreiben. Ist das Programm durchgelaufen, erhält man in der Datei spenden.txt (definiert in der Variable $spendendatei), alle seine Spender. Dabei kommt ein Spender der mir 10 mal gespendet hat auch 10 mal in der Datei vor. Im Anfangskommentar des Scripts steht auch ein Beispiel wie man diese Informationen verwerten kann.

#!/usr/bin/perl -w
#
# Name: spenden.pl
# License: GPL
# 
# Liest die Spendenstatistik vom Pennergame des Accounts $username mit dem Passwort $passwort aus.
# Speichert alle aufgeführt Spender sortiert in spender.txt.
# Daten kann man dann z.b. mit einem Shellscript weiterverarbeiten:
# "for link in `cat spender.txt | uniq`
# do
#     anzahl=`cat spender.txt | grep $link | wc -l`
#     echo $anzahl $link
# done | sort -rn > spender.sort.txt"
#
# You may use, distribute or modify this program
# under the terms of the GPL.

use strict;
use LWP::UserAgent;

# neuen Browser erstellen
my $browser = LWP::UserAgent->new;

my $url;
my $response; # Beinhaltet die Antwort eines Seitenaufrufs
my $username = "muster";
my $password = "passwort";
my $line; # Wird in foreach-Schleifen verwendet, um etwas zeilenweise einzulesen
my $count; # Beinhaltet später die Anzahl der Seiten, die die Statistik hat
my $i; # Schleifenvariable
my @spender; # Beinhaltet am Ende alle bisherigen Spender
my $link; # Beinhaltet einen einzelnen Link als Zwischenspeicher
my $spenderdatei = "./spenden.txt";

# Cookies einschalten
$browser->cookie_jar({});

# Einloggen bei pennergame.de mit $username und $password
$url = "http://www.pennergame.de/login/check/";
$response = $browser->post( $url,
   [
     "submitform" => "submitform",
     "username" => $username,
     "password" => $password
   ],
 );
die "Konnte $url nicht laden" unless defined $response;

# Rückgabestatus = 302 --> Weiterleitung nach erfolgreichem Einloggen (Optional)
if ($response->status_line =~ m/.*?302.*?/) {
    $url = $response->header("Location");
    $response = $browser->get($url);
    die "Fehler bei $url\n" unless defined $response;
}

$url = "http://www.pennergame.de/change_please/statistics/"; # Anlaufpunkt, Statistikseite 1
$response = $browser->get($url);
die "Fehler beim laden von $url\n" unless defined $response;

# Antworte in Tempfile ablegen, um es dann zeilenweise wieder einzulesen. Überflüssig, habe aber nicht genug Perl kenntnisse, um das anders zu lösen
open(TMPFILE, ">/tmp/pennergame.tmp") || die "Fehler beim Öffnen des Tempfiles\n";
print TMPFILE $response->content || die "Kann nicht in das Tempfile schreiben\n";
close(TMPFILE) || die "Kann nicht in das Tempfile schreiben\n";

# Zeilenweise (!) wieder aus dem Tempfile lesen, ermitteln wieviele Statistikseiten vorhanden sind
open(TMPFILE, "/tmp/pennergame.tmp") || die "Kann das Tempfile nicht zum Lesen öffnen\n";
while ($line = <TMPFILE>)  {
    chomp($line);
    if ($line =~ s/.*?<a href="\/change_please\/statistics\/([0-9]+)\/">.*/$1/ ) {
        $count = $line; # $count bekommt sie Seitenzahlen
    }
}
close(TMPFILE) || die "Kann das Tempfile nicht schließen\n";

# Jede Seite ansteuern und die Spender heraussammeln
for ($i = 1; $i <= $count; $i++) {
    $url = "http://www.pennergame.de/change_please/statistics/$i/";
    $response = $browser->get($url);
    die "Fehler beim Laden von $url\n" unless defined $response;

    # Response ins Tempfile schreiben, um zeilenweise wieder einzulesen
    open(TMPFILE, ">/tmp/pennergame.tmp") || die "Fehler beim Öffnen des Tempfiles\n";
    print TMPFILE $response->content || die "Kann nicht Schreiben ins Tempfile\n";
    close(TMPFILE) || die "Kann nicht Tempfile wieder schließen\n";

    # Tempfile einlesen und Zeilenweise bearbeiten
    open(TMPFILE, "/tmp/pennergame.tmp") || die "Kann Tempfile nicht zum Lesen öffnen\n";
    while ($line = <TMPFILE>) {
        # Passt auf regulären Ausdruck? --> Rest abschneiden und $link zur Liste der Spendern hinzufügen
        if ($line =~ s/.*?(\/change_please\/[0-9]{7}\/).*/$1/ ) {
            $link = "http://www.pennergame.de" . $line;
            push(@spender, $link);
        }
    }
    close(TMPFILE) || die "Kann Tempfile nicht wieder schließen\n";
}

@spender = sort(@spender);

# sortierte Liste in spender.txt schreiben
open(SPENDER, ">$spenderdatei") || die "Fehler beim öffnen von $spenderdatei\n";
foreach $line (@spender) {
    print SPENDER $line || die "Fehler beim schreiben in $spenderdatei\n";
}
close(SPENDER) || die "Fehler beim schreiben in $spenderdatei\n";
h1

Bot für das Pennergame [2]

Oktober 28, 2008

Das zweite Script des Pennergamebots loggt sich zunächst bei pennergame.de mit den vorgegebenen Benutzerdaten ein. Danach liest es zeilenweise den Inhalt der in $linkliste angegebenen Datei ein und ruft jeden Link vom Account aus auf. Außerdem gibt es zwischen jedem Aufruf eine zufällige Wartezeit zwischen 0 und 1 Sekunde, weil es bei pennergame.de einen „Botschutz“ gibt, den wir umgehen müssen. Das Script gibt außerdem immer die Anzahl der bisher aufgerufenen Links aus und den Responsestatus des Aufrufs.

#!/usr/bin/perl -w
#
# Name: spenden.pl
# Autor: Thomas Wienecke
# License: GPL
# 
# Loggt sich als User $username mit dem Passwort $passwort bei pennergame.de ein.
# Klickt dann vom Account aus alle Spendenlinks aus der Datei in $linkliste an.
#
# You may use, distribute or modify this program
# under the terms of the GPL.

use strict;
use LWP::UserAgent;

# neuen Browser erstellen
my $browser = LWP::UserAgent->new;

my $url;
my $response;
my $username = "muster";
my $password = "passwort";
my $link;
my $zaehler = 0;
my $linkliste = "links_uniq.txt"; # Muss vorhanden sein und in jeder Zeile ein Link stehen haben
my @links;

# Cookies einschalten
$browser->cookie_jar({});

# Einloggen
$url = "http://www.pennergame.de/login/check/";
$response = $browser->post( $url,
   [
     "submitform" => "submitform",
     "username" => $username,
     "password" => $password
   ],
 );
die "Konnte $url nicht laden" unless defined $response; # Fehlermeldung + Beenden

# Kommt 302 im Status vor -> Weiterleitung nach erfolgreichem Login (Optional)
if ($response->status_line =~ m/.*?302.*?/) {
    # url auf die weitergeleitet wird, herausfiltern
    $url = $response->header("Location");
    $response = $browser->get($url);
    die "Fehler bei $url\n" unless defined $response;
}

# Links aus Datei lesen
open(LINKLISTE, $linkliste) || die "Konnte $linkliste nicht öffnen\n";
@links = <LINKLISTE>;
close(LINKLISTE) || die "Konnte $linkliste nicht schließen\n";

# Für jeden Link tue...
while(1) {
    foreach $link (@links) {
            $response = $browser->get($link); # Link aufrufen
            die "Fehler beim Spenden\n" unless defined $response; 

            print $response->status_line . "\n"; # Rückgabestatus ausgeben

            sleep(rand()); # rand() gibt Wert zwischen 0 und 1 zurück. Solange schlafen, damit Account nicht gesperrt wird
            $zaehler++;
            print $zaehler . ". Durchlauf\n\n"; # Der wievielte Link wird behandelt?
    }
    sleep(60*60);
}
h1

Bot für das Pennergame [1]

Oktober 28, 2008

Ich spiele ja beim Pennergame mit. Also habe ich jetzt einen Bot für selbiges in Perl geschrieben, bestehend aus 3 Teilen.

Der erste Teil durchforstet die Seiten eines Forumsthemas nach Spendenlinks. Ungefähr 1900 verschiedene Pennergamespieler haben z.Z. dort ihren Spendenlink gepostet. Das Perlprogramm durchforstet also diese ganzen Seiten und sucht mithilfe von regulären Ausdrücken in jeder Zeile nach Spendenlinks. Am Ende wird diese Liste von Spendenlinks sortiert und in die Datei „links.txt“ geschrieben. Allerdings sind dort auch Einträge mehrfach vertreten, weil ich noch nicht weiß, wie man in Perl „uniq“ auf ein Array anwendet (Seid mir deswegen nicht böse, ich hab erst gestern angefangen Perl zu lernen 😉 ). Dieser Mangel lässt sich aber in der Bash mit einem „uniq links.txt > links_uniq.txt“ leicht beheben.

Wer Kritik an dem Quellcode hat – ich bitte darum, Verbesserungsvorschläge als Kommentar zu posten 😀

#!/usr/bin/perl -w
#
# Name: get_spendenlinks.pl
# License: GPL
# Sucht Spendenlinks von
# 'http://www.cheat-lexikon.de/spiele-forum/pc-f3/brauche-geld-fuer-meine-penner-t31.html'
# für das Pennergame (pennergame.de)
# Schreibt die Links in "./links.txt"
# Im Ergebnis kommen Links mehrfach vor, da Leute ihren Link mehr als einmal eintragen
#     --> Nachbereitung: 'cat links.txt | uniq > links.uniq.txt'
# Uniq kann auch noch implementiert werden, weiß durch geringe Perl-Kenntnisse noch nicht wie.
# 
# You may use, distribute or modify this program
# under the terms of the GPL.

# "Strengen Compiler" benutzen
use strict;
# Das Modul, das den "Browser" beinhaltet
use LWP::Simple;

my $url;
my $content;
my $zeile;
my $nextlink; # Welcher Link ist als nächstes dran?
my $lastlink; # Welcher Link war gerade - zum Vergleichen
my @zeilen;
my @links; # Beinhaltet am Ende alle Spendenlinks
my $anzahl; # Zeigt, auf der wievielten Seite man ist

$nextlink = 'http://www.cheat-lexikon.de/spiele-forum/pc-f3/brauche-geld-fuer-meinen-penner-t31.html'; # Startseite
$lastlink = ""; # Leer, sonst kommt es zu einem Fehler beim ersten Vergleich
$anzahl = 0;

# Solange der letzte Link nicht gleich dem nächsten ist, es also noch "unerkundete" Seiten gibt
while ($lastlink ne $nextlink) {
    print ++$anzahl . ". Durchlauf\n"; # Ausgabe der aktuellen Seitenzahl
    $lastlink = $nextlink; # Falls kein neuer Link gefunden wird, ist nextlink und lastlink gleich --> Abbruchbedingug erfüllt

    $content = get $nextlink; # get ruft die Url in nextlink auf. Gibt den Inhalt zurück
    die "Couldn't get $nextlink" unless defined $content; # Fehlerausgabe + Beenden

    # Schreibt die Seite in ein Tempfile, weil ich noch nicht weiß, wie man $content anders in Zeilen zerlegt.
    open(TMPFILE, ">/tmp/cheat_lexikon.htm") || die "Fehler beim Öffnen der Tempdatei zum schreiben\n";
    print TMPFILE $content || die "Fehler beim Schreiben in die Tempdatei\n";
    close(TMPFILE) || die "Fehler beim Schreiben in die Tempdatei\n";

    # Tempfile lesend öffnen und Inhalt in ein Array @zeilen einlesen
    open(TMPFILE, "/tmp/cheat_lexikon.htm") || die "Fehler beim Öffnen der Tempdatei zum lesen\n";
    @zeilen = <TMPFILE>;
    close(TMPFILE) || die "Fehler beim Schließen der Tempdatei\n";

    # Den Inhalt zeilenweise bearbeiten
    foreach $zeile (@zeilen) {
        # Passt der Inhalt auf die Zeile auf den regülären Ausdruck? --> Rest abschneiden und zu @links hinzufügen
        if ($zeile =~ s/.*?(http:\/\/www\.pennergame\.de\/change_please\/[0-9]{7}\/).*/$1/ ) {
            push(@links,$zeile);
        # Passt die Zeile auf den regülären Ausdruck, für die nächste Seite?
        } elsif ($zeile =~ s/.*?<a href="\.(\/pc-f3\/brauche-geld-fuer-meinen-penner-t31-s[0-9]{2,5}.html)">Nächste<\/a>.*/$1/ ) {
            $nextlink = "http://www.cheat-lexikon.de/spiele-forum" . $zeile;
        }
    }
}

@links = sort(@links);

# Zeilen in die Linkdatei (links.txt) schreiben
open(LINKDATEI, ">./links.txt") || die "Kann die Linkdatei nicht öffnen\n";
foreach $zeile (@links) {
    print LINKDATEI $zeile || die "Kann nicht in die Linkdatei schreiben\n";
}
close(LINKDATEI) || die "Kann nicht in die Linkdatei schreiben\n";

print "Fertig ;)";