FL vs. HL – Unbedingt mal reinschauen. Teilweise...

[sape]

...eigenartige Erkenntnisse.

*** Eine kleine Spielerei um mich mit der Funktionalen Programmierung vertraut zu machen. ***

Abkürzungen: FL = Funktionale Lösung; HL = Herkömmliche Lösung (in dem Sinne das ich das normalerweise so machen würde. Daher den Begriff "Herkömmlich" nicht Falsch interpretieren).


Folgende Aufgabenstellung wollte ich einmal in der Herkömmlichen Variante (prozedural) implementieren und in einer Funktionalen Variante. Anmerkung: Die Anforderung für mich war aber, das die Funktionale Variante in einem Schritt und nicht in mehreren implementiert wird (*² Also durch eine einzige Variable die einen LC enthält dessen Bestatteile aus mehreren maps, filter, lambda, etc besteht )

Aufgabenstellung:

• 1. Eine liste wird von 0 – n gefüllt. (liste)
• 2. Jede Zahl wird mit sich selbst potenziert.
• 3. Jede potenzierte Zahl die nicht gerade (aber einen Rest von 1 ergibt und nur das) und nicht 1 ist, landet in eine Neue Liste (liste2)
• 4. Jede potenzierte Zahl die gerade ist landet in eine neue Liste. (Liste3)
• 5. Es entstehen durch Punkt 2 bis 4 zwei Listen (liste2, liste3) der gleichen Länge.
• 6. Anschließend wird die erste Liste (liste) gelöscht (list=[]).
• 7. Jedes Zahl der zweiten Liste (liste2) wird von der jeder Zahl der dritten Liste (liste3) subtrahiert und dann in die erste Liste hinzugefügt, die ja zuvor gelöscht wurde und somit leer ist. (liste.append(liste2[n] - liste3[n]))

Anmerkung:
Ist zwar trivial aber dennoch komplex genug für mich, da ich mich mit FP erst seit letzter und dieser Woche auseinander setze, um das zu versuchen nach obiger Bedienung*² als FL zu implementieren.

EDIT: Punkt 3 editiert. (Hat sich ein Fehler eingeschlichen.)

[sape]

Hier mal die FL:

Code: Alles auswählen

from itertools import ifilter, imap
# Funktionale Lösung  
def fl (range_):
    return [
        map(lambda x, y: x-y,
            ifilter (lambda x: x%2 == 1 and x is not 1,
                    imap(lambda x: x**x, [x for x in xrange(range_)])
            ),
            ifilter (lambda x: x%2 == 0,
                    imap(lambda x: x**x, [x for x in xrange(range_-1)])
            )
        )
    ][0]

Ist eigentlich recht simpel.


Beginne wir bei zweiten ifliter-Block bei dem die evalaulierung beginnt.
Zweiter ifilter-Block:

Code: Alles auswählen

ifilter (lambda x: x%2 == 0,
         imap(lambda x: x**x, [x for x in xrange(range_-1)])
)

imap:
- Die LC (Zweites Argument von imap) erzeugt eine liste von 0 bis n-1 (minus 1 ist wichtig weil bei einigen Zahlen eine Exception ausgelöst werden würde z.B. wenn range_ = 11 ist Das muss erstmal als Erklärung langen. Nur soviel, das hängt mit damit zusammen das bei einigen range_ die Listen nicht gleich groß werden z.B. bei 11. Diesen Seiteneffekt beuge ich so vor).
- Der lambda (erstes Argument) potenziert jede Zahl der LC mit sich selber.

ifliter:
- das eben beschrieben ist also das zweite Argument von ifilter! Es wird also in jeder iterration eine mit sich selbst potenzierte zahl zurückgegeben! So, ifliter sorgt, nun dafür das jede potenzierte Zahl gerade sein muss oder besser gesagt: Nur gerade zahlen werden akzeptiert und ungerade nicht! Das wird durch das erste Argument bewerkstelligt (lambda x: x%2 == 0).
Kurz gesagt: Potenziere jede Zahl von 0 bis range_-1 mit sich selber und filtere jede ungerade Zahl heraus.

Erster ifilter-Block:

Code: Alles auswählen

ifilter (lambda x: x%2 == 1 and x is not 1,
         imap(lambda x: x**x, [x for x in xrange(range_)])
)

Das gleiche wie oben, bloß das hier jede Zahl herausgefiltert werden soll die gerade (EDIT: aber nur eine Rest von 1 hat) ist oder eine 1 ist (lambda x: x%2 == 1 and x is not 1).

.

Code: Alles auswählen

return [
    map(lambda x, y: x-y, [Erster ifilter-Block], [Zweiter ifilter-Block])
][0]

Wider recht einfach. Wir nehmen hier map statt imap, das eine liste zurückgibt und nicht eine iterrator. So, das lambda (Erstes Argument von map) subtrahiert die zurückgegebene zahl vom erster ifilter-Block mit der Zahl vom zweiten ifilter-Block. Jedes Ergebnis wird dem LC entsprechende in eine temporäre Liste erzeugt die dann mit return zurückgegebne wird.
Das [0] am ende sorgt dafür das mir eine Liste zurückgegeben wird und nicht die Liste vom map in einer liste -> statt das [[23, 2869, 776887]] wird [23, 2869, 776887] zurückgegeben. -> Klar, ich hätte die ganze map Anweisung nicht im LC packen brauchen, _aber_ so wollte ich mir die Möglichkeit offen halten das ich da noch mit for statements, etc arbeiten kann, ohne alles neu einrücken zu müssen Ich will da noch einiges später hinzufügen als Übung für mich

Soviel dazu. An dieser stelle entschuldige ich mich für die lange Erklärung des Codes. Ich habe das an dieser stelle gemacht, weil ich von euch Feedback haben möchte ob ich die evaulierung die ich mir da gebastelt habe auch richtig verstehe

Fazit: Problem gelöst und, für mich überraschender weise, sehr kurzer und übersichtlicher Form. Man kann also mit FP vieles in kurzer Schreibweise lösen.

EDIT: from itertools import ifilter, imap vergessen im Script einzufügen.

[sape]

Hier mal die HL:

Code: Alles auswählen

def hl(range_):
    liste = [x for x in xrange(range_)]
    liste2 = []
    liste3 = []
    
    for li in liste:
        p = li ** li
        if p % 2 == 1 and p != 1:
            liste2.append(p)
        if p % 2 == 0:
            liste3.append(p)
    
    liste = []    
    for n in xrange(len(liste2)):
        liste.append(liste2[n] - liste3[n])
    
    return liste

Ja, ein wenig länger und wohl auch leichter(?) zu verstehen. Was wohl hier als erstes aufält ist das mehr Speicherplatz verbraucht wird weil 3 Listen erzeugt werden. Aber ist das ein Trugschluss?

Hmm, ich habs mir so erklärt und da an BlackJacks Worte gedacht (ungefähr so meinte er das): "imap ist das gleiche wie map aber liefert nur einen iterrator was weniger platz verbraucht als wenn er eine Liste zurückliefert." Das heißt wohl wen ich im FL-Beispiel alle imaps, ifliter, etc durch die i-lose variante ersetze, würde kein iterrator zurückgeliefert sondern immer die ganze liste was zu einem kurzzeitigen erhöhten Speicherverbrauch führt.

Sehe ich das richtig? Wenn dem zutrifft dann ist die Antwort auf die eben gestellte frage: Ja die HL Variante verbraucht mehr Speicher weil genau 2 listen mehr gebraucht werden, statt nur eine wie im FL -> Tatsächlich liefert return [map()] vom FL-Beispiel eigentlich nur eine Liste weil der [] teil nur ne Blinder Liste ist (ich nenne es mal so), weil die ja nur ein Element erhält und zwar die Zurückgelieferte Liste von map(). Eine Liste mit einem Element verbraucht ja nicht soviel wie eine Liste mit 100 Ich hoffe ich interpretiere das richtig(?)

So, bis hier hin war es das. Was meint ihr, habe ich das soweit alles begriffen? Sind mein Erklärung i.O. oder verstehe ich viele zusammenhänge nicht wirklich? Aber wie auch immer, die FL-Variante funktioniert, macht also das gleiche wie die HL. ^^

[sape]

Damit ihr euch vergewissern könnt dass beide das gleiche machen

Code: Alles auswählen

[...]
count = 200
print fl(count)
print hl(count)
[...]

Und hier der Beweise das alle Zahlen ungerade sind

Code: Alles auswählen

count = 40
val = hl(count)
print "len:", len(val)

for x in enumerate(val):
    if x[1] % 2 == 1:
        print "Nr. %-10d %d" % (x[0]+1, x[1])

Ihr werdet sehen das die Länge der Liste 19 ist und alle 19 Zahlen ungerade sind. Gibt auch ruhig mal bei count 400 ein

Aber Vorsicht: Solltet ihr 20.000 eintragen dann macht auch auf eine hohen Laufzeit gefasst. Bei FL beträgt sie ca. 12 Minuten Bei 400 ca. unter 1 Sekunde.

[sape]

Etwas wirklich eigenartiges - Benchmark: HL vs. FL
Natürlich wollte ich auch wissen welche Variante den nun die schnellere ist Es ist schließlich eine Funktion die ein hohes Laufzeit verhalten hat.

Was ihr braucht: benchmark.py v1.0.4 beta
Link: http://paste.pocoo.org/show/83/
Thread: http://www.python-forum.de/topic-7735,30.html

Code: Alles auswählen

import mylib.benchmark as bm
count = 4000
bench = bm.Benchmark()
bench.add_function(fl, 'fl', count)
bench.add_function(hl, 'hl', count)
bench.run()
bench.print_ranking()

Output 1 – Count = 4000:

Code: Alles auswählen

[Die Laufzeit wird ermittelt]
run:      fl - fl         OK (8.19sec.)
run:      hl - hl         OK (4.27sec.)

[Ranking wird erzeugt]
Ranking wurde erzeugt.
-------------------------------------------------------------------------------
Funktion: fl - fl         ist am langsamsten; Zeit: 8.191885 sec
Funktion: hl - hl         ist um 91.66% schneller; Zeit: 4.274086 sec
-------------------------------------------------------------------------------

Output 2 – Count = 20000:

Code: Alles auswählen

[Die Laufzeit wird ermittelt]
run:      fl - fl         OK (739.02sec.)
run:      hl - hl         OK (373.39sec.)

[Ranking wird erzeugt]
Ranking wurde erzeugt.
-------------------------------------------------------------------------------
Funktion: fl - fl         ist am langsamsten; Zeit: 739.020739 sec
Funktion: hl - hl         ist um 97.92% schneller; Zeit: 373.394677 sec
-------------------------------------------------------------------------------

Im zweiten Output bei count=20.000, beträgt die Laufzeit für fl() 12,32 Minuten und für hl() 6,22 Minuten!

Nun seid ihr an der reihe. Wie kommt das den zustande? Ist doch ein wenig eigenartig das gerade die Funktionale Lösung fast das Doppelte braucht.

LG XtraNine
P.S.: Have Fun

[BlackJack]

Warum diese überflüssige Liste in `fl`, die Du mit einem Element erstellst nur um dann gleich wieder dieses eine Element heraus zu nehmen!?

Nächster Punkt: ``[x for x in xrange(range_)]``. Da hättest Du gleich ``range(range_)`` schreiben können. In beiden Fällen wird unnötig Speicherplatz für die gesamte Liste belegt und letzteres ist wesentlich schneller, da in C implementiert. Letztendlich bedeutet das aber, dass Deine funktionale Lösung wesentlich mehr Speicherplatz belegt als nötig wäre.

Zum Benchmark: Die funktionale Lösung berechnet mehr. Die beiden `ifilter()` Ausdrücke berechnen erstmal das gleiche, also doppelt und schmeissen dann jeweils die Hälfte weg. ``x**x`` wird deshalb in `fl` doppelt so oft berechnet wie in `hl`. Dazu kommt dann noch das unsinnige Elementeweise kopieren ohne Effekt bei ``[x for x in ...]``, das Du in `fl` auch zweimal machst und in `hl` nur einmal.

Letztendlich kann man Deine funktionale Lösung auf das hier reduzieren:

Code: Alles auswählen

from operator import sub

def f1(range_):
    return map(sub,
               (x**x for x in xrange(3, range_, 2)),
               (x**x for x in xrange(2, range_ - 1, 2)))

Was wesentlich aufgeräumter aussieht, als eine effiziente "herkömmliche" Lösung.

Deine "HL" sieht "absichtlich ineffizient" aus, IMHO. Ich hätte es wohl eher so geschrieben:

Code: Alles auswählen

def f3(range_):
    result = list()
    tmp = None
    for x in xrange(2, range_):
        if tmp is None:
            tmp = x**x
        else:
            result.append(x**x - tmp)
            tmp = None
    return result

In Haskell habe ich's auch noch mal implementiert und da eine alternative Lösung geschrieben, die sowohl gerade als auch ungerade Potenzen berechnet, immer zwei aufeinanderfolgende Listenelemente (umgedreht) zu einem Tupel zusammenfasst und dann die Zahlen in den Tupeln subtrahiert:

Code: Alles auswählen

pairing []       = []
pairing (x:y:xs) = (y,x):pairing xs

f range = map (uncurry (-)) $ pairing $ [x^x| x <- [2..range]]

[sape]

Ok schön, dann hab ich also nichts verstanden. Ich danke dir das du dir die Zeit genommen hast. Bin nun um einiges schlauer

Warum diese überflüssige Liste in `fl`, die Du mit einem Element erstellst nur um dann gleich wieder dieses eine Element heraus zu nehmen!?

Hatte ich doch erwähnt warum. Hast aber recht für das beispiel hier hätte ich das aber entfernen sollen. Hatte aber nicht die lust extra nochmal alles einzurücken für das Beispeie hier, da ich ziemlich lange daran gesessen habe die 4 Posts hier im Thread zu schreiben. (hab vorher alles in Word geschriben und dan noch mal ca. 1/2 Stunde gebraucht bis ich das hier alles so gepostet/formatiert hatte wie ichs mir denke ^^)

Nächster Punkt: ``[x for x in xrange(range_)]``. Da hättest Du gleich ``range(range_)`` schreiben können. In beiden Fällen wird unnötig Speicherplatz für die gesamte Liste belegt und letzteres ist wesentlich schneller, da in C implementiert.

Seit wann ist 'range' schneller und in C implementiert? 'xrange' ist schneller und in C implementiert. Warum hätte ich mir den LC sparen können? Ich dachte 'map' und 'imap' nimmt nur LCs als letztes Argument an? *gleich-nochmal-doku-lesen-bzw-selber-teste-^^*

Letztendlich kann man Deine funktionale Lösung auf das hier reduzieren:

Code: Alles auswählen

from operator import sub

def f1(range_):
    return map(sub,
               (x**x for x in xrange(3, range_, 2)),
               (x**x for x in xrange(2, range_ - 1, 2)))

[/code]

hmm...Sehr schön...wusste ich nicht das damit die gleichen zahlen rauskommen, wie wenn ich das mit 'lambda x: x%2 == 1 and x is not 1' und 'lambda x: x%2 == 0' überprüfe. Aber ich denke ich hab begriffen -> Nächstest mal gleich testen, ob nicht die gleiche folge auch mit entsprechendem start, end und schrittmänge bei 'xrange' rauskommt.

Deine "HL" sieht "absichtlich ineffizient" aus, IMHO. Ich hätte es wohl eher so geschrieben:

Stimmt, jetzt wo ich dein Code sehe hätte ich gleich über den 'range' iterrieren können und dann x**x in 'tmp' speichern und bei jeder anderen iterration x**x - tmp...
War echt keine Absicht, das es so ineffizient aussieht.

...

Ich hoffe der Thread verschwindet in der Versenkung, so schlecht ist der ^^ Mit Abstand mein bisher schlechtester Thread...

Danke das du dir die Zeit genommen hast. Ich weiß das zu schätzen Jack.

lg

P.S.: Bis zum nächsten 'sinnlosen' thread von mir ^^ Nein will nicht auf den Arm
P.P.S: Der nächste Thread von mir wird bestimmt sehr gut ^^ Ernst gemeint

[BlackJack]

Warum diese überflüssige Liste in `fl`, die Du mit einem Element erstellst nur um dann gleich wieder dieses eine Element heraus zu nehmen!?

Hatte ich doch erwähnt warum. Hast aber recht für das beispiel hier hätte ich das aber entfernen sollen. Hatte aber nicht die lust extra nochmal alles einzurücken für das Beispeie hier, da ich ziemlich lange daran gesessen habe die 4 Posts hier im Thread zu schreiben. (hab vorher alles in Word geschriben und dan noch mal ca. 1/2 Stunde gebraucht bis ich das hier alles so gepostet/formatiert hatte wie ichs mir denke ^^)

In *Word*!?

Minimale Änderung wäre gewesen die äusseren eckigen Klammern durch Runde zu ersetzen und das ``[0]`` zu entfernen. Da hättest Du an der Einrückung nichts ändern müssen.

Nächster Punkt: ``[x for x in xrange(range_)]``. Da hättest Du gleich ``range(range_)`` schreiben können. In beiden Fällen wird unnötig Speicherplatz für die gesamte Liste belegt und letzteres ist wesentlich schneller, da in C implementiert.

Seit wann ist 'range' schneller und in C implementiert? 'xrange' ist schneller und in C implementiert. Warum hätte ich mir den LC sparen können? Ich dachte 'map' und 'imap' nimmt nur LCs als letztes Argument an?

Nein die nehmen beide beliebige "iterable"-Objekte als Argumente. Und ich habe nicht ``xrange(n)`` mit ``range(n)`` verglichen, sondern ``[x for x in xrange(n)]`` mit ``range(n)``. Im ersten Fall wird in einer Python-Schleife eine Liste Element für Element erzeugt, im zweiten Fall steht hinter dem Aufruf C-Code der genau die Grösse der zu erzeugenden Liste kennt und die sehr schnell auf einen Schlag erzeugen kann.

wusste ich nicht das damit die gleichen zahlen rauskommen, wie wenn ich das mit 'lambda x: x%2 == 1 and x is not 1' und 'lambda x: x%2 == 0' überprüfe. Aber ich denke ich hab begriffen -> Nächstest mal gleich testen, ob nicht die gleiche folge auch mit entsprechendem start, end und schrittmänge bei 'xrange' rauskommt.

Hm, das die Eigenschaft gerade/ungerade bei "Selbstpotenzierung" erhalten bleibt, fand ich irgendwie offensichtlich.