request_url_withoutHTTP=,canonical_url_withHTTP=,canonical_url_withoutHTTP=,request_url_withoutHTTP_realspaces=. Python (Seite 1 von 1) « Tags « Blog « Bernhard Häussner
Bernhard Häussner
Tags: Artikel mit dem Tag «Python» durchstöbern

Über Pythons kurze Listennotation

03.07.2011, 20:34
Python-Code mit Listennotation

Python-Code mit Listennotation

Als ich mir Python (3.2) anschaute, musste ich mich zunächst an das Fehlen traditioneller for-Schleifen gewöhnen, doch inzwischen finde ich großen Gefallen an den Iterationsmethoden von Python und an der Listennotation (List Comprehensions).

Zunächst ein einfaches Programm mir dieser Listenverarbeitungssyntax. Folgendes Python-Stück erstellt eine Liste mit den ersten 5 Quadratzahlen von ungeraden Zahlen:

>>> [i**2 for i in range(10) if i%2==1]
[1, 9, 25, 49, 81]

Jetzt ein Beispiel aus der Python-Dokumentation, wie man zwei Vektoren multiplizieren kann:

>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

Wobei ich anhand dieses Codefetzens zeigen will, dass sich Dinge auf vielerlei Arten und mitunter einfacher machen lassen. Man kann unter Verwendung von zip() über zwei Listen gleichzeitig iterieren: (mit enumerate() ließe sich auch noch über den Index iterieren)

>>> [e1*e2 for e1,e2 in zip(vec1,vec2)]
[8, 12, -54]

An den nächsten Codezeilen sehen wir erstmals, wie schön in Python ähnliche Datentypen die gleichen Operatoren verwenden: Der Intervall-Itarator, welcher von range() zurückgegeben wird, kann als Sequenztyp wie eine Liste zerstückelt werden:

>>> a=5
>>> [i for i in range(200-a*2,200,2)]
[190, 192, 194, 196, 198]
>>> [i*2 for i in range(100)[-a:]]
[190, 192, 194, 196, 198]

Sehr praktisch sind auch die Aggeregatfunktionen all(), any(), max(), min(), sum(), len() da sich mit ihnen viel Boilerplate-Code vermeiden lässt, der so ähnlich aussieht wie dieser:

>>> testlist=[1,8,9]
>>> test=False
>>> for x in testlist:
...     if(x>4):
...         test=True
...         break
...
>>> test
True

Nach dramatischer Verkürzung:

>>> any(x>1 for x in testlist)
True

Interessanterweise bleibt der Effekt von break erhalten. Das kann man prüfen, indem man mit yield-Syntax ein eigenes, iterierbares Objekt erstellt, welches beim iteriert-werden Statusmeldungen ausgibt. Hier wird die 9 nicht mehr getestet:

>>> def worker(l):
...     for i in l:
...         print("Proccessing %02d" % i)
...         yield i>4
...
>>> w2=worker(testlist)
>>> any(w2)
Proccessing 01
Proccessing 08
True

PS: In Haskell (von welchem Python seine Listennotation hat) kann man den selben Effekt noch schöner an unendlichen Listen sehen: any (> 5) [0..] ergibt True.

Man kann die Aggregatfunktionen auch auf Strings anwenden, da auch diese iterierbar sind:

>>> any(""),any("ha")
(False, True)
>>> max("Panzer")
'z'

Für eine Suchfunktion (theoretische Informatik...) brauchte ich eine Methode herauszufinden, wie lange das längste Präfix eines Strings ist, welches ein Suffix eben jenes Strings und eines weiteren Buchstaben ist. Was ich zunächst hier mit traditionellen Methoden als 10-zeilige Funktion geschrieben, habe ich dann hier als eine Listenverarbeitung schreiben können:

>>> v="abcabd"
>>> i=5
>>> b="c"
>>> max([0]+[k for k in range(0,i+2) if (v[:i]+b)[-k:]==v[:k]])
3

Oder ich habe gemessen, dass die Diagonale in einem Rechteck 29,4° geneigt ist, aber wie war das Seitenverhältnis? Da sorted() eine lexikographische Ordnung herstellt, kann man mehrere Tupel sortieren, wobei der erste Eintrag das Sortierkriterium ist und die weiteren die Ausgangsdaten. Dann baut man noch eine zweite Listennotaton außen herum zum Formatieren. Hiermit findet man also heraus, dass es wohl 16:9 war:

>>> import math,fractions
>>> ", ".join(["{}:{}".format(b,a) for diff,a,b in sorted(
...     [(abs(math.atan(a/b)-((29.4/360)*2*math.pi)),a,b)
...         for a in range(20) for b in range(20)
...       if b>a>0 and fractions.gcd(a,b)==1 ]
... )[:3]])
'16:9, 7:4, 9:5'

Hier sieht man schon ein Problem der Listennotation: Sie wird schnell unübersichtlich, da dutzende Befehle in einem Ausdruck stehen, und man auch eher von hinten nach vorne lesen muss.

Da man mit dem +-Operator Listen konkatenieren kann, kann auch die sum()-Funktion beliebig viele Listen aus einer Liste konkatenieren. Hiermit werden je 3 Zahlen startend bei 0,9 und 18 in eine Liste geschrieben:

>>> sum([range(i,i+3) for i in range(0,27,9)],[])
[0, 1, 2, 9, 10, 11, 18, 19, 20]

Das einzige, was man hier tun muss, ist sum() eine leere Liste als zweites Argument zu übergeben, da sonst die Listen zum Standartanfangswert 0 addiert werden würden (Exception). Etwas komisch ist dann leider das:

>>> sum((str(i) for i in [1,2,345,6,78]),"")
Traceback (most recent call last):
  File "", line 1, in 
TypeError: sum() can't sum strings [use ''.join(seq) instead]

Und wenn man denkt, man weiß alles über Listen, fängt man mit Mengen an:

>>> noprimes={j for i in range(2, 8) for j in range(i*2, 50, i)}
>>> set(range(2, 50))-noprimes # Primzahlen!
{2, 3, 5, 7, 41, 11, 13, 47, 17, 37, 19, 43, 23, 29, 31}
>>> {chr(i) for i in range(97,97+26)} - set( # Pangram powers!
... "The quick brown fox jumps over the lazy dog" )
set() 

Wie man sieht bilden die Iterator- und Sequenztypen ein mächtiges Instrument, wenn man Python programmiert. Wie vieles kann man sie aber auch missbrauchen.

Kommentare: keine

Bilder züchten

12.02.2009, 17:32

Mit freeSq gezüchtetes Bild

Der neueste Trend ist es ja anscheinend genetisch zu Programmieren (bzw. programmieren zu lassen). Der Webcomic xkcd greift das Thema auf und Roger Alsing zeigt wie es geht. Mir geht es natürlich nicht darum Algorithmen genetisch zu basteln, oder Bilder nach zu stellen, sondern ich wollte einfach mal den Computer etwas herumprobieren lassen. Da wir in Kunst zurzeit kubistische Bilder malen müssen, habe ich mir gedacht, so etwas könnte doch auch ein Computer hin bekommen. Der Computer malt also Rechtecke, und versucht sie so hin zu bekommen, dass es ungefähr aussieht, wie das Originalbild.

Da das Vorgehen ja ein bisschen an die Biologie angelehnt sein sollte, benutzte ich so etwas, wie einen genetischen Algorithmus. (Es ist also nicht der Algorithmus, der „genetisch“ erzeugt wurde). Im ersten Versuch habe ich dem Computer fünfhundert, zunächst gleiche, weiße Rechtecke auf schwarzem Hintergrund vorgesetzt. Der Computer hat dann immer ein zufälliges Rechteck genommen und zufällig platziert. Die neuen Bilder waren also so etwas wie Kinder. Dann hat eine Fitting-Funktion überprüft, ob sich die Ähnlichkeit zur Vorlage verbessert hat. Wenn ja, hat er dieses neue zufällige Rechteck gespeichert (also in die „DNA“) aufgenommen und dieses Kind als neues Mutterelement verwendet. Hat sich nichts verbessert, hat er einfach ein weiteres Kind erzeugt.

Die Fitting-Funktion

Ich habe ein kleines Python-Script gebastelt, dass die Übereinstimmung zweier Bilder ausrechnen kann. Da alles in schwarz-weiß passiert, geht es jeden Pixel durch und addiert jeweils die Differenz der Rotwerte. Je größer die Zahl ist, desto schlechter passt das Bild. Der Computer favorisiert also Kinder mit kleineren Werten.

Zweiter Algorithmus

Da der erste Algorithmus zwar mit nur 500 Rechtecken immer bessere Näherungen erreicht hat, aber zum Ende hin sehr viele Versuche brauchte um wieder ein besser angepasstes Kind zu finden habe ich einen zweiten Algorithmus gebastelt, der diese Probleme vermeiden soll:

Er züchtet aus einem Elternelement zunächst 500 Kinder. Die Zucht-Funktion fügt allerdings jetzt jeweils ein schwarzes oder weißes Rechteck hinzu, wodurch Fehler schneller korrigiert werden können. Beim alten Algorithmus konnte ein fehlerhaftes Rechteck ja nur verschoben werden, wenn es zufällig gewählt und zufällig richtiger platziert wurde. Die Zahl der Rechtecke entspricht also der der Generation.

Die 500 Kinder sind zunächst noch klein und es werden nur 25% der Pixel gerastert. Die Kinder werden dann mit einer kleineren Version der Vorlage verglichen, und nur die besten 10 werden erwachsen und dann in voller Größe vergleichen. Damit werden nicht mehr so viel Ressourcen (Rechenzeit) für grobe Fehlplatzierungen verschwendet. Aus den letzten 10 Kindern wird dann das, welches in groß am Besten passt, als neues Elternelement gewählt, aus dem wiederum 500 neue Kinder-Bilder gezüchtet werden. Die 499 anderen Kinder werden für immer gelöscht, sodass nun nur noch die Elternelemente (die mit Verbesserungen) konserviert werden um meine Felsplatte zu schonen. So werden immer weiter bessere Merkmale vererbt, bzw. alte Fehler in den Merkmalen korrigiert.

Die DNA

Genau wie bei der echten DNA auch, werden die Informationen so gespeichert, dass die Kinder „wachsen“ können, nämlich als SVG. PHP kann durch seine DOM-Funktionen die DNA leicht verändern und die Rechtecke sind in einem angemessenen Format gespeichert. Mit dem Programm rsvg lassen sich die Rechtecke auch schnell rastern in allen beliebigen Größen.

Das Ergebnis

Der erste Algorithmus „500“ hat nach 21 Stunden 50830 Generationen erzeugt und einen dabei Das Original recht nett angenähert. Ursprünglich habe ich geplant ein kleines Video daraus zu erstellen, doch selbst bei 30 fps wäre es etwa eine halbe Stunde lang, und man würde hauptsächlich die Fehlschläge sehen. Deshalb nur einige Auszüge aus dem Werdegang:

Der zweite Algorithmus „freeSq“ ist so gebaut, dass er ohne Probleme unterbrochen werden kann und deswegen werde ich ihn wohl noch deutlich länger laufen lassen. Aber nach den ersten rund 2 Stunden und 255 Generationen (127500 Versuchen) ist das Entsanden (links Vorlage):

Seltsamerweise ist es etwas zu klobig, es wirkt bisher nicht so fein, dafür ein bisschen komplexer, doch es wird sich zeigen, wie es nach einigen weiteren Generationen aussieht. Da das Ganze sehr viel Zufall beinhaltet, könnte bei einem weiteren Durchlauf auch ein völlig anderes Bild entstehen. Ich bin gespannt.

Übrigens: So sieht Evolution bei den Simpsons aus.

Kommentare: keine
[ Seite 1 ]
 
Χρόνογραφ
© 2008-2017 by Bernhard Häussner - Impressum - Login
Kurz-Link zur Homepage: http://1.co.de/