Ich muss alle Partitionen einer bestimmten Ganzzahl generieren.
Ich habe diesen Algorithmus von Jerome Kelleher gefunden, für den es als der effizienteste gilt:
Verweis: Ссылка
Übrigens ist es nicht sehr effizient. Für eine Eingabe wie 40 friert es fast mein gesamtes System für einige Sekunden ein, bevor es seine Ausgabe gibt.
Wenn es ein rekursiver Algorithmus wäre, würde ich versuchen, ihn mit einer Caching-Funktion oder etwas zu dekorieren, um seine Effizienz zu verbessern, aber so zu sein, kann ich nicht herausfinden, was zu tun ist.
Haben Sie Vorschläge, wie Sie diesen Algorithmus beschleunigen können? Oder können Sie mir einen anderen oder einen anderen Ansatz vorschlagen, um einen neuen von Grund auf zu erstellen?
Wenn Sie diese Funktion wiederholt für die gleichen Eingaben verwenden möchten, könnte es immer noch sinnvoll sein, die Rückgabewerte zwischenzuspeichern (wenn Sie sie für einzelne Läufe verwenden möchten, können Sie die Ergebnisse in einer Datei speichern).
Wenn Sie keinen wesentlich schnelleren Algorithmus finden, dann sollte es möglich sein, dies um eine oder zwei Größenordnungen zu beschleunigen, indem Sie den Code in eine C-Erweiterung verschieben (das ist wahrscheinlich am einfachsten mit cython ), oder alternativ mit PyPy anstelle von CPython (PyPy hat seine Nachteile - es unterstützt noch nicht Python 3 oder einige häufig verwendete Bibliotheken wie numpy und scipy).
Der Grund dafür ist, dass der Interpreter, da python dynamisch typisiert wird, wahrscheinlich die meiste Zeit damit verbringt, die Typen der Variablen zu überprüfen - denn der Interpreter weiß, dass eine der Operationen x in eine Zeichenkette verwandeln könnte. In diesem Fall würden Ausdrücke wie x + y plötzlich sehr unterschiedliche Bedeutungen haben. Cython löst dieses Problem, indem es Ihnen erlaubt, die Variablen statisch als Ganzzahlen zu deklarieren, während PyPy einen Just-in-Time-Compiler hat , die redundante Typprüfungen minimiert.
Um Kompositionen direkt zu generieren, können Sie den folgenden Algorithmus verwenden:
%Vor%Dieser Algorithmus ist sehr allgemein und kann Partitionen und Zusammensetzungen vieler verschiedener Typen erzeugen. Für Ihren Fall verwenden Sie
%Vor%um alle unbeschränkten Kompositionen zu erzeugen. Das dritte Argument wird als Einschränkungsfunktion bezeichnet und beschreibt den Typ der gewünschten Zusammensetzung / Partition. Die Methode ist effizient, da der Aufwand für die Erstellung jeder Komposition konstant ist, wenn Sie alle generierten Kompositionen im Durchschnitt darstellen. Wenn Sie es in Python etwas schneller machen möchten, dann ist es leicht, die Funktion sigma durch 1 zu ersetzen.
Es ist auch hier anzumerken, dass für jeden Algorithmus mit konstanter amortisierter Zeit, was Sie tatsächlich mit den generierten Objekten tun, die Kosten für deren Erzeugung bestimmt dominieren werden. Wenn Sie beispielsweise alle Partitionen in einer Liste speichern, ist der Zeitaufwand für die Verwaltung des Speichers für diese große Liste weitaus größer als der Zeitaufwand für die Erstellung der Partitionen.
Sagen Sie, aus irgendeinem Grund möchten Sie das Produkt jeder Partition nehmen. Wenn man sich dem naiv nähert, dann ist die Verarbeitung linear in der Anzahl der Teile, während die Kosten der Erzeugung konstant sind. Es ist ziemlich schwierig, an eine Anwendung eines kombinatorischen Erzeugungsalgorithmus zu denken, bei dem die Verarbeitung die Erzeugungskosten nicht dominiert. In der Praxis gibt es also keinen messbaren Unterschied zwischen der Verwendung der einfacheren und allgemeineren RegelGen mit sigma (x) = x und dem spezialisierten accelAsc.
Testen mit n = 75 Ich bekomme:
PyPy 1.8:
%Vor%CPython 2.6:
%Vor%Cython + mingw + gcc 4.6.2:
%Vor%Ich sah keinen Unterschied mit Psyco (?)
Die Lauffunktion:
%Vor%Wenn ich die Definition von accelAsc für Cython ändere, um mit zu beginnen:
%Vor%Ich habe die Cython-Zeit auf 2,27 Sekunden heruntergesetzt.
Tags und Links python performance combinatorics data-partitioning