Idiomatische Art, Liste / Diktat in Cython zu machen?

Mein Problem: Ich habe festgestellt, dass die Verarbeitung großer Datensätze mit rohem C++ unter Verwendung der STL-Karte und des Vektors oft erheblich schneller (und mit geringerem Speicherbedarf) sein kann als die Verwendung von Cython.

Ich nehme an, dass ein Teil dieser Geschwindigkeitsstrafe auf die Verwendung von Python-Listen und -Dikten zurückzuführen ist und dass es einige Tricks geben könnte, um weniger belastete Datenstrukturen in Cython zu verwenden. Zum Beispiel diese Seite (http://wiki.cython.org/tutorials/numpy) zeigt, wie man in Cython sehr schnell numpy-Arrays erstellt, indem man die Größe und Typen des ND-Arrays vordefiniert.

Frage: Gibt es eine Möglichkeit, etwas Ähnliches mit Listen/Diktaten zu machen, zB indem man ungefähr angibt, wie viele Elemente oder (Schlüssel-Wert-)Paare Sie in ihnen erwarten? Das heißt, gibt es eine idiomatische Möglichkeit, Listen/Diktate in (schnelle) Datenstrukturen in Cython zu konvertieren?

Wenn nicht, muss ich es wohl einfach in C++ schreiben und in einen Cython-Import einbinden.

Cython unterstützt jetzt Vorlagen und enthält Deklarationen für einige der STL-Container.

Sehen http://docs.cython.org/src/userguide/wrapping_CPlusPlus.html#standard-library

Hier ist das Beispiel, das sie geben:

from libcpp.vector cimport vector

cdef vector[int] vect
cdef int i
for i in range(10):
    vect.push_back(i)
for i in range(10):
    print vect[i]

Ähnliche Operationen in Python wie in C++ können oft langsamer sein. list und dict sind eigentlich sehr gut implementiert, aber Sie gewinnen viel Overhead, wenn Sie Python-Objekte verwenden, die abstrakter sind als C++-Objekte und viel mehr Lookup zur Laufzeit erfordern.

Übrigens, std::vector wird auf ziemlich ähnliche Weise implementiert wie list. std::mapist jedoch tatsächlich so implementiert, dass viele Operationen langsamer sind als dict wie seine Größe groß wird. Für ausreichend große Beispiele von jedem, dict überwindet den konstanten Faktor, um den es langsamer ist als std::map und führt Vorgänge wie Suchen, Einfügen usw. tatsächlich schneller aus.

Wenn Sie verwenden möchten std::map und std::vector, nichts hält dich auf. Sie müssen sie selbst umschließen, wenn Sie sie Python aussetzen möchten. Seien Sie nicht schockiert, wenn diese Verpackung die ganze oder einen Großteil der Zeit in Anspruch nimmt, die Sie zu sparen hofften. Mir sind keine Tools bekannt, die dies für Sie automatisch machen.

Es gibt C-API-Aufrufe zum Steuern der Erstellung von Objekten mit einigen Details. Sie können sagen “Erstellen Sie eine Liste mit mindestens so vielen Elementen”, aber dies verbessert nicht die Gesamtkomplexität Ihrer Listenerstellungs- und -fülloperation. Es ändert sich sicherlich nicht viel später, wenn Sie versuchen, Ihre Liste zu ändern.

Mein allgemeiner Rat ist

• Wenn Sie ein Array mit fester Größe möchten (Sie sprechen davon, die Größe einer Liste anzugeben), möchten Sie möglicherweise so etwas wie ein numpy-Array.

• Ich bezweifle, dass Sie durch die Verwendung die gewünschte Beschleunigung erzielen werden std::vector Über list Für ein Allgemeines Ersatz in Ihrem Code. Wenn Sie es hinter den Kulissen verwenden möchten, kann es Ihnen eine zufriedenstellende Größen- und Platzverbesserung bringen (ich weiß es natürlich nicht, ohne zu messen, und Sie auch nicht. 😉 ).

• dict macht seinen Job eigentlich sehr gut. Ich würde definitiv nicht versuchen, einen neuen Allzwecktyp für die Verwendung in Python basierend auf einzuführen std::mapdas für viele wichtige Operationen eine schlechtere algorithmische Komplexität aufweist und – zumindest in einigen Implementierungen – dem Benutzer einige Optimierungen überlässt dict hat schon.

  Wenn ich etwas wollte, das ein bisschen mehr funktionierte std::map, würde ich wahrscheinlich eine Datenbank verwenden. Dies ist im Allgemeinen das, was ich mache, wenn ich Dinge in einem aufbewahren möchte dict (oder was das betrifft, Dinge, die ich in a list) wird zu groß für mich, um mich wohl zu fühlen, es im Speicher zu speichern. Python hat sqlite3 in der stdlib und treiber für alle anderen gängigen datenbanken vorhanden.

C++ ist schnell, nicht nur wegen der statischen Deklarationen des Vektors und der Elemente, die darin enthalten sind, sondern vor allem, weil man durch die Verwendung von Vorlagen/Generika angibt, dass der Vektor es tun wird nur enthalten Elemente eines bestimmten Typs, zB Vektor mit Tupeln aus drei Elementen. Cython kann das letzte Ding nicht und es klingt nicht trivial – es müsste irgendwie zur Kompilierzeit erzwungen werden (Typprüfung zur Laufzeit ist das, was Python bereits tut). Wenn Sie also jetzt etwas aus einer Liste in Cython entfernen, gibt es keine Möglichkeit, im Voraus zu wissen, um welchen Typ es sich handelt, und das Einfügen in eine typisierte Variable fügt nur eine Typprüfung hinzu, keine Geschwindigkeit. Dies bedeutet, dass der Python-Interpreter in dieser Hinsicht nicht umgangen werden kann, und dies scheint mir das entscheidende Manko von Cython für nicht-numerische Aufgaben zu sein.

Der manuelle Weg, dies zu lösen, besteht darin, die Python-Liste/das Diktat (oder vielleicht std::vector) mit einer cdef-Klasse für einen bestimmten Elementtyp oder eine Schlüssel-Wert-Kombination zu unterteilen. Dies würde auf dasselbe hinauslaufen wie der Code, den Vorlagen generieren. Solange Sie die resultierende Klasse in Cython-Code verwenden, sollte dies eine Verbesserung bieten.

Die Verwendung von Datenbanken oder Arrays löst nur ein anderes Problem, da es darum geht, beliebige Objekte (aber mit einem bestimmten Typ und vorzugsweise einer cdef-Klasse) in Container zu packen.

Und std::map sollte nicht mit dict verglichen werden; std::map verwaltet Schlüssel in sortierter Reihenfolge, da es sich um einen ausgeglichenen Baum handelt, dict löst ein anderes Problem. Ein besserer Vergleich wäre dict und Googles Hashtable.

Sie können sich die Norm ansehen array Modul für Python, wenn dies für Ihre Cython-Einstellung geeignet ist. Ich bin mir nicht sicher, da ich Cython noch nie benutzt habe.

Es gibt keine Möglichkeit, native Python-Listen/Diktate auf die Geschwindigkeit einer C++-Karte/eines C++-Vektors oder auch nur annähernd zu bringen. Es hat nichts mit Zuweisung oder Typdeklaration zu tun, sondern zahlt den Overhead des Interpreters. Das von Ihnen erwähnte Beispiel (numpy) ist eine C-Erweiterung und genau aus diesem Grund in C geschrieben.

Nur weil es hier nicht erwähnt wurde: Man kann zum Beispiel einen C++-Vektor einfach in einen Custom verpacken Erweiterungstyp.

from libcpp.vector cimport vector

cdef class pyvector:
    """Extension type wrapping a vector"""
    cdef vector[long] _data

    cpdef void push_back(self, long x):
        self._data.push_back(x)

    @property
    def data(self):
        return self._data

Auf diese Weise können Sie Ihre Daten in einem Vektor speichern, der schnelle Cython-Operationen ermöglicht, während Sie dennoch (mit etwas Overhead) von der Python-Seite aus auf die Daten zugreifen können.