Lindenmayer die 2te

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Antworten
thelittlebug
User
Beiträge: 188
Registriert: Donnerstag 20. Juli 2006, 20:46
Wohnort: Wien
Kontaktdaten:

Sehr geehrter Beurteiler,

Wie nicht anders zu erwarten war komme ich mit meiner Aufgabe in Ihrer Freizeit. Bitte kontrollieren Sie meinen Beitrag den ich mit größter Sorgfallt erstellt habe.
:D

Ich habe heute ein wenig meine Python Kenntnisse aufgefrischt und sogar erweitern können. Eigentlich wollte ich nur ein wenig am alten Lindenmayer Script herumprobieren, ist aber doch einiges mehr geworden.
Das ganze braucht nun Pygame (grafische Ausgabe lässt sich deaktivieren) wenn man Bilder mag.

Ich habe versucht einiges was ich über OO gelesen habe in diesem Script praktisch anzuwenden, da ich aber erst in Kapitel 4 od. 5 von geschätzen 15 bin wird sicher auch aus OO Sicht nicht alles perfekt sitzen ;)

Wenn mich nicht alles täuscht sollte man es sogar als Modul in eigene Skripte einbinden können, z.b. wenn man meine Pygame Turtle Version braucht.

Ich bitte natürlich wie immer um Kritik. Ich hoffe das es diesmal nicht so viel sein wird ;)

lgherby

edit: Achso, dumm, das ganze findet man unter http://www.thelittlebug.org/ da es über 300 Zeilen Code hat.

Bild
BlackJack

Igitt, das sieht ja aus wie Java.

Statt der `LindenmayerRules`-Klasse hätte eine einfache Liste genügt.

Die `Lindenmeyer`-Klasse beinhaltet nur eine einzige Methode die `self` nicht benutzt. Das ist eine *Funktion*. Python hat so etwas. Kein Grund jeden Sch*#% in eine Klasse zu zwingen.

`LindenmeyerDraw` hat immerhin schonmal eine `__init__()` und in der einzigen Methode wird `self` benutzt, aber *nötig* ist der ganze Klassenzauber hier auch nicht.

Die ``if``/``elif``-Kaskade in `Lindenmeyer.calc()` könnte man man verkürzen und oft wiederholtes ``+=`` ist keine gute Idee weil dabei jedesmal eine neue Zeichenkette erstellt wird. Ungetestet:

Code: Alles auswählen

    for dummy in xrange(depth):
        tmp = list()
        for char in path:
            tmp.append(rules.get(char, char))
        path = ''.join(tmp)
    
    for old, new in (('R', 'F'), ('L', 'F'), ('r', 'f'), ('l', 'f')):
        path = path.replace(old, new)
    
    return
Beim Zeichnen könnte man auch ein Dictionary statt der ``if``\s benutzen:

Code: Alles auswählen

def draw(path, startstate, angle, length, turtle):
    turtle_stack = list()
    
    def down_forward():
        turtle.down()
        turtle.forward(length)
    
    def up_forward():
        turtle.up()
        turtle.forward(length)
    
    dispatch = {'F': down_forward,
                'f': up_forward,
                '-': lambda: turtle.left(angle),
                '+': lambda: turtle.right(angle),
                '|': lambda: turtle.left(180),
                '[': lambda: turtle_stack.append(turtle.getstate()),
                ']': lambda: turtle.setstate(turtle_stack.pop())}
    
    for instruction in path:
        dispatch[instruction]()
thelittlebug
User
Beiträge: 188
Registriert: Donnerstag 20. Juli 2006, 20:46
Wohnort: Wien
Kontaktdaten:

BlackJack hat geschrieben: Statt der `LindenmayerRules`-Klasse hätte eine einfache Liste genügt.
Ist als Platzhalter gedacht da hier später wie in der ToDo Liste beschrieben zumindest Lade- wenn nicht sogar noch Bearbeitungsmethoden folgen. Wie sieht es nun mit dieser Zusatzinformation aus?
BlackJack hat geschrieben: Die `Lindenmeyer`-Klasse beinhaltet nur eine einzige Methode die `self` nicht benutzt. Das ist eine *Funktion*. Python hat so etwas. Kein Grund jeden Sch*#% in eine Klasse zu zwingen.
Deto, ich bin mir hier nicht sicher ob hier nicht doch noch einige Methoden dazukommen. Insgesammt spiele ich mit dem Gedanken es etwas genereller hinzubekommen. Da es auch mehrere Ersetzungssysteme gibt wäre die Klasse spätestens dann notwendig. Momentan ist sie alleine gesehen relativ witzlos.

BlackJack hat geschrieben: `LindenmeyerDraw` hat immerhin schonmal eine `__init__()` und in der einzigen Methode wird `self` benutzt, aber *nötig* ist der ganze Klassenzauber hier auch nicht.
Hier wollte ich einfach zusammenfassen was zum Zeichnen zusammengehört um hier flexibilität bei der Auswahl der 'lowlevel'-Zeicheklasse zu bewahren, Denkbar wäre es mehrere "LindenmayerDraw"'s zu haben für z.b. meine Turtle implementation, die Tkinter Version und eine hätte ich garantiert noch probiert, siehe ToDo-Liste: OpenGL :D
BlackJack hat geschrieben: Die ``if``/``elif``-Kaskade in `Lindenmeyer.calc()` könnte man man verkürzen und oft wiederholtes ``+=`` ist keine gute Idee weil dabei jedesmal eine neue Zeichenkette erstellt wird. Ungetestet:
Leider nein da path.replace ein anderes Ergebnis liefert, weil wir nicht einfach alle, sagen wir, F's auf einmal ersetzen dürfen sondern einen Platzhalter nach dem anderen da es das Lindenmayer System so erforder. Ich war am Anfang auch auf deine Lösung gekommen, leider ist Sie nur bei ganz einfachen Systemen die nur mit einer Ersetzungsregel gleichzeitig arbeiten richtig. Würdest du mir meine Lindenmayer Klasse lassen könnte man ja eine spezialisierte Version mit replace machen ;)
BlackJack hat geschrieben: Beim Zeichnen könnte man auch ein Dictionary statt der ``if``\s benutzen:
Ah, das gefällt mir gut, das werd ich gleich einbauen. Da hab ich auch schon etwas darüber gelesen und mir selbst versprochen dieses "Dispatchen" zu merken, aber... :)

thx & lg herby

edit: btw., hab mir auch Python Ge-Packt gekauft, ist wirklich eine nützliche Referenz, konnte Sie hier bereits gut verwenden. thx an gerold für den tipp
BlackJack

Du fragtest nach Kommentaren zum Programm so wie es ist.

Dieses, man muss alles in Klassen packen und jede Kleinigkeit herausfaktorisieren, weil man diese Flexibilität irgendwann, vielleicht mal brauchen könnte, kenne ich von Java und finde ich nicht besonders gut. Da kommt in der Regel viel Quelltext bei heraus, der am Ende doch nicht gebraucht wird. Und in einigen Fällen hat man dann sogar eine Klassenhierarchie, bei der sich zu spät heraus stellt, dass sie nicht so aufgebaut ist, wie man es letztendlich eigentlich bräuchte.
thelittlebug hat geschrieben:
BlackJack hat geschrieben: Statt der `LindenmayerRules`-Klasse hätte eine einfache Liste genügt.
Ist als Platzhalter gedacht da hier später wie in der ToDo Liste beschrieben zumindest Lade- wenn nicht sogar noch Bearbeitungsmethoden folgen. Wie sieht es nun mit dieser Zusatzinformation aus?
Nicht so viel anders. Was Du bei einer Liste in diesem Zusammenhang benötigst ist der Indexzugriff ``rules[5]`` und eventuell die Länge ``len(rules)``. Diese Schnittstelle kann man auch in einer eigenen Klasse anbieten, wenn man die Liste ersetzen möchte.

Wobei vielleicht noch die Frage ist, was genau so eine `Rules`-Klasse an Bearbeitungsmethoden bieten soll, die Listen nicht bieten. Denn wirklich bearbeiten möchte man ja eher die Regeln *in* der Liste.
BlackJack hat geschrieben: Die `Lindenmeyer`-Klasse beinhaltet nur eine einzige Methode die `self` nicht benutzt. Das ist eine *Funktion*. Python hat so etwas. Kein Grund jeden Sch*#% in eine Klasse zu zwingen.
Deto, ich bin mir hier nicht sicher ob hier nicht doch noch einige Methoden dazukommen.
Wenn Du nicht sicher bist, warum dann eine Klasse? Wenn es doch zu Funktionen kommt, die einen gemeinsamen Zustand brauchen, rückt man die einfach ein, schreibt ein `self` in die Argumentlisten und ``class Irgendwas(object)`` davor.
Insgesammt spiele ich mit dem Gedanken es etwas genereller hinzubekommen. Da es auch mehrere Ersetzungssysteme gibt wäre die Klasse spätestens dann notwendig.
Nicht zwingend, man könnte auch verschiedene Funktionen anbieten.

Falls sich die Systeme erheblich unterscheiden, zum Beispiel auch in den Eingangsdaten, die sie benötigen, wäre das vielleicht in einer `Rule`-Klasse besser aufgehoben. Das wäre dann ein Fall, wo Daten und dazugehörige Funktionen in einem Objekt gekapselt werden.
BlackJack hat geschrieben: `LindenmeyerDraw` hat immerhin schonmal eine `__init__()` und in der einzigen Methode wird `self` benutzt, aber *nötig* ist der ganze Klassenzauber hier auch nicht.
Hier wollte ich einfach zusammenfassen was zum Zeichnen zusammengehört um hier flexibilität bei der Auswahl der 'lowlevel'-Zeicheklasse zu bewahren, Denkbar wäre es mehrere "LindenmayerDraw"'s zu haben für z.b. meine Turtle implementation, die Tkinter Version und eine hätte ich garantiert noch probiert, siehe ToDo-Liste: OpenGL :D
Das wäre aber doch immer die gleiche Funktion, die einfach nur eine andere `turtle` übergeben bekäme.
BlackJack hat geschrieben: Die ``if``/``elif``-Kaskade in `Lindenmeyer.calc()` könnte man man verkürzen und oft wiederholtes ``+=`` ist keine gute Idee weil dabei jedesmal eine neue Zeichenkette erstellt wird. Ungetestet:
Leider nein da path.replace ein anderes Ergebnis liefert, weil wir nicht einfach alle, sagen wir, F's auf einmal ersetzen dürfen sondern einen Platzhalter nach dem anderen da es das Lindenmayer System so erforder. Ich war am Anfang auch auf deine Lösung gekommen, leider ist Sie nur bei ganz einfachen Systemen die nur mit einer Ersetzungsregel gleichzeitig arbeiten richtig. Würdest du mir meine Lindenmayer Klasse lassen könnte man ja eine spezialisierte Version mit replace machen ;)
Ich benutze nicht `replace()` um die Regeln zu ersetzen, sondern *am Ende* um die 'L's und 'R's durch 'F's zu ersetzen, weil das für den Quelltext zum Zeichnen einfacher wird.

Das Ersetzen der Regeln mache ich genau wie Du. Nur dass ich nicht ``+=`` auf Zeichenketten benutze und damit wesentlich weniger temporäre Zeichenketten und damit Kopieraktionen verursache. Ab Python 2.5 ist ``+=`` in bestimmten Fällen optimiert, aber darauf sollte man sich nicht verlassen.

Was sich bei dem Programm wie es jetzt ist, anbieten würde, ist eine `Rule`-Klasse, die eine einzelne Regel kapselt. Regeln bestehen aus einem Startwert und den Ableitungsregeln für die einzelnen Zeichen und man kann sie expandieren und zeichnen. Das sind Daten und neben der `__init__()` noch zwei Methoden die ganz gut zusammenpassen.
thelittlebug
User
Beiträge: 188
Registriert: Donnerstag 20. Juli 2006, 20:46
Wohnort: Wien
Kontaktdaten:

Ich beschwere mich ja nicht das du mein Programm zerflederst, ich versuche nur zu erfahren warum du anderer Meinung bist als meine Quellen, z.b. http://www.galileocomputing.de/openbook/oo/
Ich sehe das ganze auch nicht so ernst, sondern freue mich auf deine Meinungen, in der Hoffnung von der Erfahrung anderer zu profitieren ;) Dennoch sollte es klar sein das ich Meinungen nicht ungeprüft übernehme. Garnichtdenker gibt es ja schon genug.
BlackJack hat geschrieben: Kein Grund jeden Sch*#% in eine Klasse zu zwingen.
Kein Grund mit Sonderzeichen um sich zu werfen, wir sind ja nicht im Perl Forum :D

Wie sieht es mit diesen beiden aus:

Code: Alles auswählen

tmp = list()
tmp = []
Macht es irgendeinen Unterschied das eine dem anderen vorzuziehen?
BlackJack hat geschrieben:Du fragtest nach Kommentaren zum Programm so wie es ist.
Ja, wahrscheinlich wäre es hilfreicher gewesen wenn ich meine Gedanken auch dazugeschrieben hätte. Sicherlich Faulheit, aber ich werde mich bessern, ich versprechs :)
BlackJack hat geschrieben: Da kommt in der Regel viel Quelltext bei heraus, der am Ende doch nicht gebraucht wird. Und in einigen Fällen hat man dann sogar eine Klassenhierarchie, bei der sich zu spät heraus stellt, dass sie nicht so aufgebaut ist, wie man es letztendlich eigentlich bräuchte.
Hmm... ist das aber nicht eher ein generelles Problem das man überall, auch ohne Klassen haben könnte? Am Ende kommt man auf vieles drauf, Datenformat passt nicht, Zeichenroutinen fürn "Popsch", nichts passt zusammen. Ich glaub das liegt nicht an den Klassen selbst. Selbst wenn die Klassenhierarchie, von Klassen die man benutzen muss und vielleicht selbst nicht ändern kann da es z.b. "Fremdklassen" sind, nicht passt bietet doch gerade OO die Lösung diese Klassen zu kapseln. Und Performance lass ich hier nicht gelten, immerhin programmieren wir hier in Python und nicht in C.

Die Frage die sich mir nun stellt: Sind Klassen böse? Brauchen sie womöglich so viel mehr "Ressourcen"? Was passt an Ihnen nicht um sie eben nicht für alles zu verwenden? Ich persönlich sehe jetzt keinen Grund auf die Strukturierungen mithilfe von Klassen zu verzichten selbst wenn nur eine Liste drinnen ist. Sind es wirklich die 4 Zeilen Code mehr die ich dazu zu tippen habe an denen sich viele stören? Darf ich sie nicht dazu verwenden etwas Struktur zu erreichen? Wandern wir hier möglicherweise wieder in ein Gebiet voller Angst vor verlorener Performance ab? Wenn nicht, was ist es dann?
BlackJack hat geschrieben:Nicht so viel anders. Was Du bei einer Liste in diesem Zusammenhang benötigst ist der Indexzugriff ``rules[5]`` und eventuell die Länge ``len(rules)``. Diese Schnittstelle kann man auch in einer eigenen Klasse anbieten, wenn man die Liste ersetzen möchte.

Wobei vielleicht noch die Frage ist, was genau so eine `Rules`-Klasse an Bearbeitungsmethoden bieten soll, die Listen nicht bieten. Denn wirklich bearbeiten möchte man ja eher die Regeln *in* der Liste.
Primär ging es mir hier um das Speichern und Laden der Regeln. Interessant wäre es auch wenn sich das Datenformat (die Liste selbst) aus mir noch nicht bekannten Gründen ändern würde. Dann würde man nach außen hin nichts von der Änderung merken, ich dachte das dies eine Grundüberlegung von OO sei. Natürlich, im mom. Zustand der Daten wäre eine Liste einfacher, aber auch um soviel besser? "Aus mir noch nicht bekannten Gründen" ist natürlich falsch und ein Platzhalter, denkbar wäre z.B. für ein 'F' mehrere Regeln mit Warscheinlichkeiten zu definieren um "Wildwuchs" bei Pflanzen zu ermöglichen. Da ist es natürlich schön wenn man sich außerhalb nicht mehr darum kümmern muss.
BlackJack hat geschrieben: Ich benutze nicht `replace()` um die Regeln zu ersetzen, sondern *am Ende* um die 'L's und 'R's durch 'F's zu ersetzen, weil das für den Quelltext zum Zeichnen einfacher wird.
Interessant wäre es sicherlich auch die L's und R's eigen zu lassen, ich habe z.b. Implementationen gesehen die damit die Zeichenfarbe ändern (damit lassen sich hübsche Pflänzchen malen). Natürlich hast du recht, ich habe deinen Code nicht auf Anhieb verstanden und ihn absolut falsch gesehen ;) Aber ist das nicht auch wieder voreilige Optimierung?
BlackJack hat geschrieben: Das Ersetzen der Regeln mache ich genau wie Du. Nur dass ich nicht ``+=`` auf Zeichenketten benutze und damit wesentlich weniger temporäre Zeichenketten und damit Kopieraktionen verursache. Ab Python 2.5 ist ``+=`` in bestimmten Fällen optimiert, aber darauf sollte man sich nicht verlassen.
Ich sehe das jetzt einfach mal als voreilige Optimierung an, da:
1. Du hast du optimiert bevor du wahre Engpässe erkannt hast. In der Tat ist es nämlich eher so das die Zeichenroutine selbst ausschlaggebend für die Performance ist. Warum sollte ich an anderen Stellen optimieren die realtiv wenig Gewinn bringen?
2. Die Ausbeute bei path.append() ist nicht berauschend. Meiner Meinung nach liest sich += auch einfacher und kann eher nachvollzogen werden.
Testparameter: 'Islands and Lakes' mit depth=6, ohne Zeichnen, ohne Ausgabe auf Konsole
Wie groß wird eigentlich der endgültige Zeichenstring?

Code: Alles auswählen

thelittlebug@ubuntu:~/Desktop/python$ ./linden.py -p --system=20 | wc
      1       1 277370836
277 Mio. Zeichen, das ist ne ganze Menge, und wie lange dauert das mit der alten aber besser lesbaren "+="-Methode?

Code: Alles auswählen

thelittlebug@ubuntu:~/Desktop/python$ time ./linden.py --system=20

real    0m21.208s
user    0m17.385s
sys     0m2.764s
Deine Methode mit path.append.

Code: Alles auswählen

thelittlebug@ubuntu:~/Desktop/python$ time ./linden.py --system=20

real    0m18.286s
user    0m16.337s
sys     0m1.044s
Mich haut das Ergebnis nicht um. Ich hätte mir hier mehr erwartet da ich wahrscheinlich so wie du immer über das böse "+=" bei Strings gelesen habe.

Bei der "alltäglichen" Arbeit fällt der unterschied der beiden Methoden mit 0.009 Sekunden in einen Bereich den ich als absolut "wurscht" bezeichnet hätte. Die ganze Zeit die wir da schon darüber gequatscht haben hat schon wesentlich mehr Zeit gekostet als wir hier jemals einsparen könnten :D

Zum Thema Optimieren, ich bin kein Feind. Sollte daran erkennbar sein das ich eine eigene Turtleimplementation gebastelt habe die der Tkinter Version in Sachen Geschwindigkeit um längen vorraus ist. Die Tkinter Turtle wird, je mehr Linien am Bildschirm sind, immer langsamer. Bei ~5000 Linien war es schon unerträglich.

Bitte glaube nicht das ich deine Kritik einfach umdrehe, ich freue mich auf eine Diskussion um deine Argumente besser zu verstehen, vielleicht kann man ja gegenseitig von den Gedanken des anderen profitieren. Ich habe bewusst mehr Smileys eingesetzt als du um gewissen Stellen zu entschärfen, bei dir klingt vieles, für meinen Geschmack, viel zu hart ;) :D

lgherby & thx fürs durchlesen
BlackJack

Ich kenne das Buch von Galileo Computing nicht, darum weiss ich jetzt auch nicht genau wo meine Meinung vom Buch abweicht.
BlackJack hat geschrieben: Kein Grund jeden Sch*#% in eine Klasse zu zwingen.
Kein Grund mit Sonderzeichen um sich zu werfen, wir sind ja nicht im Perl Forum :D
'Tschuldigung. Die Hitze, die Uhrzeit, Emotionen. Werde versuchen weniger mit Perl-Syntax zu argumentieren. :-)

Ob man eine leere Liste mit ``list()`` oder ``[]`` erzeugt, ist Geschmackssache. Ich mag's als Wort "ausgeschrieben" lieber, weils deutlicher ist und man ``tuple()``, ``list()`` und ``dict()`` je nach Schriftart und -grösse besser unterscheiden kann als ``()``, ``[]`` und ``{}``. Man muss natürlich auch bedenken, dass die Funktionen im Namensraum gesucht und ausgeführt werden müssen, während das jeweilige Literal vom Übersetzer schon in entsprechenden Bytecode übersetzt wird.

Code: Alles auswählen

In [7]: dis.dis(lambda: list())
  1           0 LOAD_GLOBAL              0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE

In [8]: dis.dis(lambda: [])
  1           0 BUILD_LIST               0
              3 RETURN_VALUE
Das die Architektur nicht hinhaut kann mit Funktionen auch passieren, aber bei Klassenhierarchien sind IMHO die Probleme grösser wenn sie dann auftauchen. Teilweise weil bei Klassenhierarchien oft Entwurfsentscheidungen getroffen werden, bevor die Funktionalität in der Praxis gebraucht wird. Besonders bei Java+UML werden manchmal "Monsterhierarchien" entworfen, mit vielen Klassen und Interfaces, bei denen erst während der Implementierung der einzelnen Methoden klar wird, dass das Zusammenspiel nicht so wirklich optimal ist.

Das ist natürlich immer Abwägungssache wieviel Architekturplanung vorher notwendig ist, und wieviel von der Architektur beim Programmieren aus den Anforderungen heraus "wachsen" darf und sollte.

Mit Geschwindigkeit will ich bei den überflüssigen Klassen übrigens gar nicht argumentieren, sondern mit unnötiger Komplexität. Das KISS-Prinzip -- Keep It Simple and Stupid. Die einfachste Lösung, die das aktuelle Problem löst. Natürlich mit einem Blick auf Erweiterbarkeit. Das wäre für die Regeln erst einmal eine Liste.

Klassen sind von Haus aus nicht böse, aber alles in eine Klasse stecken, wo eine einfache Liste oder Funktion ausreicht erfüllt den Sinn von Strukturierung nicht. Damit sollen Programme ja einfacher und übersichtlicher werden. Es ist nicht das mehr an tippen, sondern das mehr an lesen und verstehen müssen.

Ein Objekt, dass nur eine Liste kapselt, kann man auch nur mit einer Liste umsetzen. Hier reichen ja erst einmal ``rules`` und ``len(rules)`` aus. Das ist die KISS-Lösung. Erweiterbar ist sie auch, denn wenn da später Methoden hinzukommen kann man einfach in der Klasse `__getitem__()` und `__len__()` implementieren und die Liste durch ein Objekt dieser Klasse ersetzen.

Laden und speichern würde ich als Funktionen implementieren falls mehrere Formate geplant sind. Ein Container mit Regeln, egal ob nun Liste oder eigenes Objekt, muss IMHO nicht wissen wie die Daten mal auf Platte aussahen, oder aussehen werden. Beispiel: es gibt drei Formate: Pickle, XML und JSON. Es gibt Regeln die als Pickle vorliegen und welche die als XML vorliegen, ich möchte beide Laden und als JSON speichern. Wo ist der Unterschied zwischen dem Container mit den ehemals gepickleten Regeln und denen, die irgendwann mal als XML vorlagen? Eigentlich sollte es keinen geben. Wie kann ich beide Container zusammenführen? Und dann als JSON speichern?

Das mit den 'F's und Wahrscheinlichkeiten ist etwas was Regeln selbst etwas angeht, und nicht den Container. Wie schon im letzten Beitrag gesagt: Du hast für alles (un)mögliche Klassen eingeführt, aber dass was so ein Lindenmeyer System als zentralen Baustein ausmacht, die Regeln selbst, sind bei Deiner Lösung keine Objekte mit selbst definiertem Verhalten.

Statt ``+=`` in einer Schleife, `join()` zu verwenden, ist ein sehr gängiges Python-Idiom. Ich würde es nicht als voreilige Optimierung sondern als Wahl des effizienteren Algorithmus bezeichnen. Die Schleife mit ``+=`` hat quadratische und `join()` lineare Laufzeit. Da geht's nicht nur um Geschwindigkeitsgewinn, sondern auch um Stil.

Bei der Messung bekomme ich ähnliches heraus. Nur die "Expansion" als einzelne Funktion mit ``+=``:

Code: Alles auswählen

real    0m13.240s
user    0m10.537s
sys     0m2.696s
Mit `join()`:

Code: Alles auswählen

real    0m11.793s
user    0m11.397s
sys     0m0.368s
Hier ist der gravierende Unterschied zwischen den `sys`-Zeiten interessant. Den kann man wahrscheinlich auf den Unterschied in der Anzahl der Speicheranforderungen zurückführen. Dass heisst das Ergebnis dürfte stark von der Speicherverwaltung der C-Laufzeitbibliothek und des Betriebssystems abhängen.

Voreilige Optimierung hätte bei mir übrigens so ausgesehen:

Code: Alles auswählen

def expand_3(start, rules, depth):
    result = [start]
    get = rules.get
    for dummy in xrange(depth):
        result = [get(character, character)
                  for characters in result
                  for character in characters]
    return ''.join(result)
Die dazugehörige Zeitmessung:

Code: Alles auswählen

real    0m6.813s
user    0m6.424s
sys     0m0.336
Die Lösung IMHO ist sogar noch recht lesbar. Besser wäre natürlich eine Funktion in C oder handoptimiertem Assembler. ;-)

Andererseits hätte ich grundsätzlich eher ein Speicherplatzproblem gesehen und die expandierte Form nicht wirklich angelegt, sondern eine rekursive Generatorfunktion geschrieben.

Die ganzen Smileys kannst'e Dir bei mir denken. Ist wirklich nicht bös' oder gemein von mir gemeint. Einiges ist sicher auch Geschmacksfrage und/oder Starrsinn meinerseits. :-)
thelittlebug
User
Beiträge: 188
Registriert: Donnerstag 20. Juli 2006, 20:46
Wohnort: Wien
Kontaktdaten:

ich grabe alte threads aus weil:
1. ich kann

hey blacky, auch noch da? :)
Benutzeravatar
noisefloor
User
Beiträge: 3843
Registriert: Mittwoch 17. Oktober 2007, 21:40
Wohnort: WW
Kontaktdaten:

Hallo,

@thelittlebug: BlackJack hat sich schon vor längerem hier im Forum abgemeldet.

Gruß, noisefloor
Antworten