Optimierungsbedarf Code von BMaxzu Python

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Yogi
User
Beiträge: 80
Registriert: Montag 21. Januar 2008, 16:35
Wohnort: Bonner

Optimierungsbedarf Code von BMaxzu Python

Beitragvon Yogi » Freitag 1. Februar 2008, 22:46

Hi,

da ich ja ernsthaft mit dem Gedanken spiele mein Projekt (den Serverteil) mit Python und den Modulen zu erstellen, wollte ich mal testen, wie ich generell klar komme und vor allem wie schnell Python ist.

Im ersten Schritt habe ich einen kleinen Teil sinngemäß nach Python übertragen, also quasi Python pur. Natürlich ist was da rauskommt viel viel zu langsam. Aber ich denke mal, dass man da noch vieles optimieren kann, bevor ich anfange Bereiche nach C/C++ aus zu lagern. Dazu bräuchte ich mal eure Hilfe.
BlitzMax braucht für 1000 Instanzen weniger als eine Sekunde.
Mein Python Skript braucht knapp 30 Sekunden. Das schockiert mich jetzt recht wenig, da ich die 30 Sekunden auch mit BMax geschafft habe, und zwar durch die Verwendung einer Liste nur um indexweise an den Inhalt zu gelangen. Das gleiche habe ich denke ich mal jetzt auch in Python gemacht.

Ich habe dann in BlitzMax die Liste in ein Array konvertiert und durch casting auf die einzelnen Elemente zu gegriffen. Resultat: von 30 Sek auf <1 Sek.

Python hat ja nun keine Arrays in dem Sinne. Was wäre denn euer Vorschlag das ganze zu optimieren??

Hier schon mal mein Python Code: http://paste.pocoo.org/show/25236/

Witziger Weise gibt de Profiler Werte zurück die rein gar nichts zu tun haben mit der eigentlichen Ausführungszeit. Warum eigentlich?

Edit (BlackJack): Code ausgelagert.
Yogi
User
Beiträge: 80
Registriert: Montag 21. Januar 2008, 16:35
Wohnort: Bonner

Beitragvon Yogi » Freitag 1. Februar 2008, 23:29

Heilige Sch****!!

Das hätte ich ja jetzt so nicht erwartet. Ich habe mal Psyco verwendet und schon wurde die Zeit auf 891 Millisekunden gedrückt? Das ist ja wahnsinn!

Tja was nun? Bringt es noch was das ganze trotzdem noch in Python selbst zu optimieren? Bringt Pyrex viel mehr? Psyco ist ja leider nur für intel 386 cpus konzipiert. Dumm nur, dass die meisten Mietserver nur AMD haben.
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Beitragvon BlackVivi » Samstag 2. Februar 2008, 00:01

Yogi hat geschrieben:Heilige Sch****!!

Das hätte ich ja jetzt so nicht erwartet. Ich habe mal Psyco verwendet und schon wurde die Zeit auf 891 Millisekunden gedrückt? Das ist ja wahnsinn!

Tja was nun? Bringt es noch was das ganze trotzdem noch in Python selbst zu optimieren? Bringt Pyrex viel mehr? Psyco ist ja leider nur für intel 386 cpus konzipiert. Dumm nur, dass die meisten Mietserver nur AMD haben.
Wo hast'n das gelesen? Er ist vllt auf x86 optimiert, aber bestimmt nicht nur auf Intel... Ich hab'n AMD...
Yogi
User
Beiträge: 80
Registriert: Montag 21. Januar 2008, 16:35
Wohnort: Bonner

Beitragvon Yogi » Samstag 2. Februar 2008, 00:28

BlackVivi hat geschrieben:Wo hast'n das gelesen? Er ist vllt auf x86 optimiert, aber bestimmt nicht nur auf Intel... Ich hab'n AMD...


http://psyco.sourceforge.net/psycoguide/req.html

okok, also auch amd, das ist gut, obwohl amd bei Berechnungen wohl per se eher Probleme bereitet, es sei denn man installiert einen entsprechenden Treiber. Weiss jetzt aber nicht ob die Anbieter das getan haben. Aber ich denke es wird wohl für meine Belange reichen..
BlackJack

Beitragvon BlackJack » Samstag 2. Februar 2008, 01:12

Da steht "Intel 386 compatible" und AMDs Prozessoren sind natürlich kompatibel.

Und was für einen Treiber soll man bei AMD-Prozessoren für Berechnungen brauchen!?

Der Benchmark ist ziemlich komisch. Bist Du sicher, dass Du das mit Klassen und Instanzattributen verstanden hast?
Yogi
User
Beiträge: 80
Registriert: Montag 21. Januar 2008, 16:35
Wohnort: Bonner

Beitragvon Yogi » Samstag 2. Februar 2008, 01:35

BlackJack hat geschrieben:Da steht "Intel 386 compatible" und AMDs Prozessoren sind natürlich kompatibel.

Und was für einen Treiber soll man bei AMD-Prozessoren für Berechnungen brauchen!?

http://blitzmax.com/Community/posts.php?topic=70456#788238
Aber sehe gerade, dass es scheinbar nur die Dual AMD's betrifft ( also auch die meisten Server, zumindest unter Windows, Linux?

Der Benchmark ist ziemlich komisch. Bist Du sicher, dass Du das mit Klassen und Instanzattributen verstanden hast?


Ich habe versucht meinen BMax Code zu portieren, zumindest kommt das richtige raus. Ob es eleganter geht? mag sein. Und ich bilde mir zumindest ein den Unterschied zwischen Klassen- und Instanzattributen verstanden zu haben. Aber ich bilde mir nicht ein, die Python Art zu programmieren zu können. Aber dafür bin ich ja hier um zu fragen, aber bis jetzt kommt wenig dies bezüglich ;)
BlackJack

Beitragvon BlackJack » Samstag 2. Februar 2008, 10:13

Das "AMD-Problem" hat nichts mit Berechnungen im allgemeinen zu tun, sondern mit Timing-Code in einem BlitzMax-Programm der sich darauf verlässt dass ein Prozessor durchgehend mit dem gleichen Takt läuft. Das müsste Single-Core-Prozessoren und Intel-Prozessoren, die die Taktfrequenz im Betrieb ändern, auch betreffen.

Woher kannst Du bei einem Programm, dass zufällige Werte ausspuckt wissen, dass das richtige heraus kommt?

Was das Verständnis der Zusammenhänge angeht: `Universum` ist jetzt was ─ ein Universum oder ein Planet. Es versucht anscheinend beides zu sein. Warum heisst `countPlanets` nicht einfach `planets`? Warum sind `countPlanets` und `countBingo` Klassenattribute?

Die `getBingos()`-Methode ist übrigens überflüssig, man sollte besser direkt auf das Attribut zu greifen.

Dir ist klar, dass insgesamt 1002 Universum-Objekte erzeugt werden und dass der `direkt()`-Aufruf 1001 Universen und nicht 1000 bearbeitet!? In `planet` sind aber nur die ersten 1000. Ist das so gewollt? Warum?

Und dann habe ich ein Problem mit den 30 Sekunden Laufzeit. Bei mir sind's nämlich nur ca. 3½ Sekunden, und ich denke nicht dass Du sooo einen langsamen Rechner hast, der den Unterschied erklären würde.

Ausserdem müsstest Du mal beschreiben, was das Programm eigentlich tun soll. Denn sonst könnte man wahrscheinlich das ganze Programm zu einem ``print`` zusammen schrumpfen lassen, was einfach eine entsprechende Zufallszahl im erwarteten Bereich ausgibt.

Zum Profiler: Welcher? Was hat der geliefert und in wie fern weicht das von dem ab, was Du erwartet hast?
BlackJack

Beitragvon BlackJack » Samstag 2. Februar 2008, 11:52

Also hier die Optimierungsvorschläge. Dein Original aus dem ersten Beitrag braucht bei mir bei 3000 (bzw. 3001) `Universum`-Objekten 23.7 Sekunden.

Die folgende Variante braucht nur noch 3.81 Sekunden. Haupsächlich weil unnötige Attribut- und Indexzugriffe minimiert wurden, und der Vergleich der `dingens` nicht in einer expliziten Schleife steckt, sondern der ``==``-Operator auf den Listen verwendet wird.

Code: Alles auswählen

    def direkt(self):
        print 'Start'
        start = datetime.datetime.now()
       
        dingens = [planet.dingens for planet in self.countPlanets]
        count = len(dingens)
        indexes = ((i, j) for i in xrange(count)
                          for j in xrange(i + 1, count))
        Universum.countBingo = sum(dingens[i] == dingens[j]
                                   for (i, j) in indexes)
       
        return datetime.datetime.now() - start


Wenn man das *richtig* beschleunigen will, muss man von der quadratischen Laufzeit weg. Also muss ein anderer Algorithmus her. Die `dingens` sortieren und gruppieren und für jede Gruppe gleicher "Dingens" die Anzahl der "Bingos" berechnen und aufsummieren zum Beispiel:

Code: Alles auswählen

    def direkt(self):
        def full_edges(n):
            return (n - 1) * n // 2
       
        print 'Start'
        start = datetime.datetime.now()
       
        dingens = sorted(planet.dingens for planet in self.countPlanets)
        Universum.countBingo = sum(full_edges(sum(1 for d in equal_dingens))
                                   for dummy, equal_dingens in groupby(dingens))
       
        return datetime.datetime.now() - start


`groupby()` kommt aus dem `itertools`-Modul. Das braucht jetzt nur noch etwas mehr als eine hundertstel Sekunde für 3001 `Universum`-Objekte. Das kann man sogar mit 100000 Objekten im Bruchteil einer Sekunde machen.
Yogi
User
Beiträge: 80
Registriert: Montag 21. Januar 2008, 16:35
Wohnort: Bonner

Beitragvon Yogi » Samstag 2. Februar 2008, 12:10

Hallo und guten Morgen!

Dieses kleine Progrämmchen ist eine 1:1 Übersetzung aus meinem in BlitzMax erstellten Proxy-Programm. Nachher werde ich alles weg schmeissen und sauber neu aufsetzen, wenigstens so sauber ich kann ;)

In Endeffekt geht es darum bei einer Anzahl von tausend Planeten (countPlanets[]) für die spätere Berechnung einen Filter zu setzen. Dieser Filter prüft auf übereinstimmende Kriterien (self.dingens). In diesem Beispiel sind es 5 Kriterien. Erst wenn alle fünf Kriterien übereinstimmen (countBingo) wird das aktuelle Planetenpärchen für die spätere Berechnung berücksichtigt (noch nicht in dem Code hier drin).
Ach ja, eigentlich müsste die Klasse Planeten heissen :)

Dir ist klar, dass insgesamt 1002 Universum-Objekte erzeugt werden und dass der `direkt()`-Aufruf 1001 Universen und nicht 1000 bearbeitet!? In `planet` sind aber nur die ersten 1000. Ist das so gewollt? Warum?


Nein, absolut nicht!! Wieso erzeugt planet = [Universum ( ) for i in range(1000)] 1002 Planeten?? Verstehe ich nicht.

Die `getBingos()`-Methode ist übrigens überflüssig, man sollte besser direkt auf das Attribut zu greifen


Ist das Python typisch? Ich kenne aus Java immer die getter und setter Methoden? Die finde ich auch logischer, weil ich dadurch die Variable verstecken kann und nachher nicht überall nach ihr im Code suchen muss.

Und dann habe ich ein Problem mit den 30 Sekunden Laufzeit. Bei mir sind's nämlich nur ca. 3½ Sekunden, und ich denke nicht dass Du sooo einen langsamen Rechner hast, der den Unterschied erklären würde.


Ich programmiere momentan lieber auf meinem alten Rechner (P4 2.66 GHz), weil der so schön leise ist. Der neue Core Duo 6600 hat eine 8800GTS drinne, die unheimlich aufheizt und trotz WAKÜ für CPU und SB Zusatz-Lüfter braucht, weil die GraKa genau auf einen Chip bläst, der mächtig aufheizt. Aber das nur am Rande.

Aber ich teste heute nochmal...??? jetzt brauche ich auch nur noch 3 Sekunden?? Hab doch den Rechner gar nicht mehr ausgemacht...
Aus der Shell und einem anderen Verzeichnis heraus sogar knapp unter 3.
Ich habe doch alles aufgehabt und aufgelassen?? Hilfe es spukt!!

Nee, ich kriegs nicht mehr hin, habe jetzt nochmal die MaxIde dazu aufgemacht, jetzt brauche ich auch nur noch 26 Millisekunden statt vorher knapp 1 Sekunde. Mir scheint als ob der Virenscanner (GDAta Antivir) was ausbremst. Ich hatte gestern Abend Probleme mit dem aktualisieren der Virensignaturen, fand keine Verbindung zum Server. Vielleicht hat er dann solange den Scanner ausgeschaltet?? Werds mal testen. Aber auf jeden Fall eine gute Nachricht.

Aber jetzt mal wieder zurück zum eigentlichen Thema, was bremst die Ausführungszeit im Code aus? Die For Schleife? der Zugriff auf die Listen?

Ein Kumpel hat mir meinen Skript nach C++ übersetzt. Bei 1000 Planeten 0.015 Dauer. Bei 10.000 Planeten 0.735 Sekunden. Schon beachtlich.

Hier der C++ Code: http://paste.pocoo.org/show/25237/

Edit (BlackJack): Code ausgelagert.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Samstag 2. Februar 2008, 12:48

Yogi hat geschrieben:
Dir ist klar, dass insgesamt 1002 Universum-Objekte erzeugt werden und dass der `direkt()`-Aufruf 1001 Universen und nicht 1000 bearbeitet!? In `planet` sind aber nur die ersten 1000. Ist das so gewollt? Warum?


Nein, absolut nicht!! Wieso erzeugt planet = [Universum ( ) for i in range(1000)] 1002 Planeten?? Verstehe ich nicht.

Das erstellt tausend. Danach erstellst du aber mit jedem Universum() noch ein weiteres - also 1002.

Yogi hat geschrieben:
Die `getBingos()`-Methode ist übrigens überflüssig, man sollte besser direkt auf das Attribut zu greifen


Ist das Python typisch? Ich kenne aus Java immer die getter und setter Methoden? Die finde ich auch logischer, weil ich dadurch die Variable verstecken kann und nachher nicht überall nach ihr im Code suchen muss.

Ja. In Python versteckt man keine Variablen. Wenn es nötig ist, Berechnungen an den Variablen auszuführen gibt es immer noch Properties, gegen die Getter und Setter alt aussehen.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Yogi
User
Beiträge: 80
Registriert: Montag 21. Januar 2008, 16:35
Wohnort: Bonner

Beitragvon Yogi » Samstag 2. Februar 2008, 13:57

@BlackJack: Ich muss zugeben, dass ich jetzt was Zeit brauchen um das zu verstehen. Das ist ja ganz außerhalb der herkömmlichen Programmierung wie in Java oder Blitzmax. Kannst du mir denn Literatur empfehlen welches die Python-Denke auch richtig erläutert? Oder wie lerne ich am besten Python so zu programmieren wie es sein soll.

Ich habe eben den zweiten Versuch bei mir laufen lassen und ich bekomme meinen Mund nicht mehr zu :shock: gut,das ich den nicht zum tippen brauch :) Bei 10.000 nur 0.031 Sekunden!! Psyco ändert daran auch nichts mehr.

Aber auf jeden Fall, kann ich mich wohl getrost in Python einschießen.

@Leonidas:
Das erstellt tausend. Danach erstellst du aber mit jedem Universum() noch ein weiteres - also 1002.


Hmmm, immer noch nix versteh. Ich erstelle tausend, genau, aber wieso mit jedem neuen Universum noch ein weiteres und warum dann 1002?

In Python versteckt man keine Variablen

Aber es gibt doch gute OOP-Argumente diese zu verstecken. Warum gilt das nicht für Python?
Benutzeravatar
veers
User
Beiträge: 1219
Registriert: Mittwoch 28. Februar 2007, 20:01
Wohnort: Zürich (CH)
Kontaktdaten:

Beitragvon veers » Samstag 2. Februar 2008, 14:13

Yogi hat geschrieben:Aber es gibt doch gute OOP-Argumente diese zu verstecken. Warum gilt das nicht für Python?
Das hat soweit mit der Idee der Objekt Orientierung selbst wenig zu tun mehr mit der Implementierung. Wenn du in Python bei einer Variable "Finger weg" sagen willst mach ein _ davor. Dann ist "jedem" klar das diese Variable nicht (oder nur mit einem sehr guten Grund) verändert werden soll. In den Meisten OO Sprachen gibt es übrigens auch Wege auf Fremde private Member zuzugreifen. Sei es Pointer biegen in C++ oder Reflection in C#.
My Website - 29a.ch
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Samstag 2. Februar 2008, 14:21

Yogi hat geschrieben:@Leonidas:
Das erstellt tausend. Danach erstellst du aber mit jedem Universum() noch ein weiteres - also 1002.


Hmmm, immer noch nix versteh. Ich erstelle tausend, genau, aber wieso mit jedem neuen Universum noch ein weiteres und warum dann 1002?

Ich nehme mal deinen Code auf, um das zu erklären:

Code: Alles auswählen

planet = [Universum ( ) for i in range(1000)]
zeit = Universum().direkt()
print zeit
print Universum().getBingos()

In der ersten Zeile erstellst du 1000 Universen. In der zweiten Zeile erstellst du ein weiteres, tausendestes Universum, wo du nur eine Funktion aufrufst und das Universum selbst wieder verwirfst. Dann machst du das gleiche in Zeile 4 - ein Universum wird erstellt - das tausendzweite, eine Funktion wird aufgerufen, und das Universum wird verworfen.

In Python versteckt man keine Variablen

Aber es gibt doch gute OOP-Argumente diese zu verstecken. Warum gilt das nicht für Python?[/quote]
Nein, das ist eigentlich kein OOP-Argument sondern ein Java-Argument. Oft wird dargestellt, das Java == OOP, aber dem ist schlichtweg nicht so.

Ich lege dir mal den Thread "Was ist OOP eigentlich?" ans Herz, dort wird diskutiert was OOP ist und was nicht.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
BlackJack

Beitragvon BlackJack » Samstag 2. Februar 2008, 14:22

@Yogi: Es ist ein Unterschied, ob man die Treffer zählt, oder wirklich die Paare zusammen stellt. Im ersten Fall gibt's nämlich die Formel um die Zahl der Paare bei `n` passenden Planeten zu berechnen, ohne dass man die Paare wirklich erstellen muss.

Aber auf jeden Fall kann man von meinem letzten Lösungsansatz den ersten Schritt, nämlich das Gruppieren von gleichen Planeten übernehmen. Dann hat man nur noch innerhalb der Gruppen quadratische Laufzeit und nicht mehr über alle Planeten auf einmal. Statt `groupby()` kann man auch ein "Histogramm" mit Hilfe von einem Dictionary erstellen. Etwas mehr Quelltext, aber zumindest in O-Notation schneller als das Sortieren und vielleicht etwas verständlicher für Leute denen funktionale Programmierung fremd ist.

Die Klasse müsste eher, wie auch im C++-Quelltext in zwei, `Planet` und `Universum`, aufgeteilt werden. Denn `direkt()` hätte auf `Planet`-Instanzen irgendwie nichts zu suchen. Ausserdem sollte die Methode die Anzahl der Treffer besser als Ergebnis liefern und nicht an das Objekt binden. Wie's jetzt ist, kann es zu Inkonsistenzen zwischen den Planeten und der Trefferzahl kommen, wenn man nach der Veränderung der Planeten vergisst die Methode auf zu rufen.

Um Python-Quelltext zu "mikro"-optimieren sollte man soviel wie möglich in C machen, d.h. wo möglich Funktionen und Methoden benutzen, die in C implementiert sind, und Attribut- und Indexzugriffe minimieren.

Nachdem ich den C++-Quelltext repariert habe:

Code: Alles auswählen

bj@s8n:~$ diff -u test1.cpp test.cpp
--- test1.cpp   2008-02-02 13:08:35.000000000 +0100
+++ test.cpp    2008-02-02 13:08:40.000000000 +0100
@@ -1,8 +1,7 @@
 // Universum.cpp : Defines the entry point for the console application.

-#include "stdafx.h"
-#include "stdlib.h"
-
+#include <cstdlib>
+#include <cstdio>
 #include <ctime>

 class CPlanet {
@@ -49,7 +48,7 @@
     }
 };

-int _tmain(int argc, _TCHAR* argv[])
+int main(int argc, char** argv)
 {
     clock_t start,finish;
     double dif;


bekomme ich für 10000 Planeten auch in etwa 0.71 Sekunden Laufzeit. Für das gleiche Ergebnis ist meine letzte Python-Lösung mit nur 0.05 Sekunden aber *deutlich*, nämlich 14× schneller als das C++-Programm. Für 100000 Planeten braucht Python 0.22 Sekunden ─ das C++-Programm habe ich nach einer halben Minute abgebrochen. Boah, ist C++ langsam. ;-)

Letztendlich kommt für `check_doubles()` Maschinencode heraus, der auf einem zweidimensionalen Integer-Array operiert und wahrscheinlich alle nötigen Variablen in Prozessorregistern hält. Dass das immer schneller ist, als der gleiche Algorithmus in einer interpretierten Hochsprache, sollte klar sein. Das ``break`` in der Funktion hast Du übrigens gar nicht in Deinem Python-Quelltext gehabt.

Ob der Code mit dem Gruppieren typisch "Python-Denke" ist, kann ich nicht sagen, es ist eher typisch funktional, wobei man das in Python gut anwenden kann. Ich mache das jedenfalls gerne. Zum Leidwesen anderer. ;-)

`psyco` kommt am besten mit Python-Quelltext zurecht, der "wie C" geschrieben ist. Generatoren kennt `psyco` soweit ich weiss gar nicht, kann da also auch nichts beschleunigen.

Universum Nummer 1001: ``zeit = Universum().direkt()``. Wird von `direkt()` berücksichtigt.

Universum Nummer 1002: ``print Universum().getBingos()``.

Die guten Gründe für triviale Getter/Setter gibt's nur in Sprachen, die keine Properties kennen. Siehe Doku zur `property()`-Funktion.
Yogi
User
Beiträge: 80
Registriert: Montag 21. Januar 2008, 16:35
Wohnort: Bonner

Beitragvon Yogi » Samstag 2. Februar 2008, 18:55

Warum muss ich immer weg , wenn es spannend wird ..?
.
.

Also wurde immer dann eine Instanz erzeugt, als ich eigentlich nur auf eine Klassenmethode bzw. Klassenvariable zugreifen wollte??

Wenn dem so ist, wie greife ich dann darauf zu ohne eine Instanz zu erzeugen?

Tum Thema getter und setters habe ich das hier gefunden.
Titel: get/set/del Methoden und Property Generator

Vor allem der Spruch
Oder willst du nur Java in Python programmieren?
trifft ins schwarze bei mir. Ich glaube, dass wird die grösste Schwierigkeit sein, mich von altem Ballast zu befreien.

Ich habe mir eben einen Artikel über properties durch gelesen Python how to program - properties Wenn ich das so richtig verstanden ist das ja sehr raffiniert. Es baut quasi auf die getter und setter auf und fasst sie zusammen und versteht aus dem Kontext heraus, welche Methode ich brauche. Sehr nett!

@Blackjack: Ob ich das funktionale hinkriege bezweifele ich momentan. Das hat so was Perliges ;) Aber je mehr ich mich damit befasse, desto mehr imponiert mir die Sprache. Aber komplex ist sie trotzdem. Die Tücke liegt im Detail aber auch im wesentlichen. Ich habe leider noch keine ansprechende Literatur finden können. Immer nur Syntax oder die bekannte Rangehensweise.

Was hast du übrigens mit dem C++ Code gemacht, jetzt verstehe ich ja gar nichts mehr...?

Muss ich eigentlich was besonderes beachten, wenn ich vorhabe später Teile in C oder C++ zu implementieren? Funktional geht da wohl eher nicht oder ;)

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder