Ich muss eine Funktion beschleunigen. Sollte ich Cython, Ctypes oder etwas anderes verwenden?

Question

Ich habe viel Spaß beim Erlernen von Python, indem ich eine Anwendung der genetischen Programmierung schreibe.

Ich hatte auf dieser Seite einige gute Ratschläge von Torsten Marek, Paul Hankin und Alex Martelli.

Das Programm besteht aus 4 Hauptfunktionen:

• erzeugen (zufällig), um einen Ausdrucksbaum.
• bewerten die Eignung des Baumes
• Mischlings
• mutieren

Da alle erzeugen, kreuzung und mutieren 'die Fitness bewerten' nennen. es ist die verkehrsreichste Funktion und ist der primäre Engpass in der Geschwindigkeit.

Wie ist die Natur der genetischen Algorithmen, muss es einen immensen Lösungsraum suchen, je schneller desto besser. Ich möchte jede dieser Funktionen beschleunigen. Ich beginne mit dem Fitness-Evaluator. Meine Frage ist, was der beste Weg ist, dies zu tun. Ich habe Cython, Ctypes und "Linking and Embedding" untersucht. Sie sind alle neu für mich und im Moment ziemlich jenseits von mir, aber ich freue mich darauf, eins und schließlich alle zu lernen.

Die 'Fitness-Funktion' muss den Wert des Ausdrucksbaums mit dem Wert des Zielausdrucks vergleichen. Es wird also aus einem Postfix-Evaluator bestehen, der den Baum in einer Postfix-Reihenfolge liest. Ich habe den ganzen Code in Python.

Ich brauche Ratschläge, die ich jetzt lernen und verwenden sollte: Cython, Ctypes oder Verknüpfung und Einbettung.

Vielen Dank.

Answer 1

Ignorieren Sie jetzt die Antwort von allen anderen. Das erste, was Sie lernen sollten, ist der Profiler. Python kommt mit einem Profil/cProfile; Sie sollten lernen, die Ergebnisse zu lesen und zu analysieren, wo die echten Engpässe liegen. Das Ziel der Optimierung ist dreifach: Reduzieren Sie die für jeden Anruf aufgewendete Zeit, reduzieren Sie die Anzahl der durchzuführenden Anrufe und reduzieren Sie die Speicherauslastung, um das Festplatten-Thrashing zu reduzieren.

Das erste Ziel ist relativ einfach. Der Profiler zeigt Ihnen die zeitaufwendigsten Funktionen und Sie können direkt zu dieser Funktion gehen, um sie zu optimieren.

Das zweite und dritte Ziel ist schwieriger, da dies bedeutet, dass Sie den Algorithmus ändern müssen, um so viele Anrufe zu vermeiden. Suchen Sie nach den Funktionen mit einer hohen Anzahl von Anrufen, und versuchen Sie, Wege zu finden, um die Anzahl der Anrufe zu reduzieren. Nutzen Sie die integrierten Sammlungen, sie sind sehr gut optimiert.

Wenn Sie alle oben genannten und immer noch Leistungsproblem haben und Sie sind auf einer x86-Plattform (im Grunde die meisten CPU), dann fangen Sie an, Psyco zu betrachten. Psyco kann einen Python-Code mit der Notwendigkeit optimieren, Ihren Python-Code überhaupt zu ändern.

Wenn Sie viele Zahlen- und Array-Verarbeitung machen, sollten Sie sich Numpy/Scipy und gmpy Module von Drittanbietern ansehen.

Als nächstes ist Cython zu versuchen. Cython ist eine etwas andere Sprache als Python, tatsächlich ist Cython C mit Pythons Syntax.

Für Teile Ihres Codes, die sich in sehr engen Schleifen befinden, die Sie nicht mehr auf andere Weise optimieren können, möchten Sie sie möglicherweise als C-Erweiterung neu schreiben. Python hat eine sehr gute Unterstützung für die Erweiterung mit C.

Answer 2

Eine weitere großartige Option ist boost :: python, mit der Sie problemlos C oder C++ umbrechen können.

Von diesen Möglichkeiten, da Sie Python-Code bereits geschrieben haben, ist Cython wahrscheinlich eine gute Sache, zuerst zu versuchen. Vielleicht müssen Sie keinen Code neu schreiben, um eine Beschleunigung zu erhalten.

Answer 3

Cython ist am schnellsten, wenn Sie Ihren Algorithmus direkt in Cython schreiben oder indem Sie ihn in C schreiben und ihn mit Cython an Python binden.

Mein Rat: lernen Cython.

Answer 4

Versuchen Sie, Ihre Fitness-Funktion zu arbeiten, so dass es Memoisierung unterstützt. Dadurch werden alle Anrufe, die Duplikate früherer Anrufe sind, durch eine schnelle Dict-Suche ersetzt.