früher oder später werden Sie auf eine Blockade stoßen, wenn es um die Geschwindigkeit Ihrer Codeausführung geht. Wenn Sie jemals einen rechenintensiven Algorithmus in Python geschrieben haben, wie zum Beispiel String-Distanz, Matrix-Mathematik oder kryptografisches Hashing, wissen Sie, was ich meine.
Sicher, es gibt Zeiten, in denen externe Bibliotheken wie NumPy Ihnen zu Hilfe kommen können, aber was passiert, wenn der Algorithmus dies tut? von Natur aus sequentiell? Das battle genau mein Downside, als ich einen bestimmten Algorithmus vergleichen wollte, der die Anzahl der Bearbeitungen bestimmt, die erforderlich sind, um einen String in einen anderen umzuwandeln.
Ich habe Python ausprobiert. Ich habe NumPy ausprobiert. Und dann wandte ich mich C zu, einer Sprache, die ich vor Jahrzehnten zum ersten Mal auf dem Faculty gelernt, aber seit etwa 15 Jahren nicht mehr verwendet hatte. Da wurde es interessant.
Ich musste zuerst die Frage beantworten: „Kann man C aus Python aufrufen?“. Nach einiger Recherche wurde schnell klar, dass die Antwort tatsächlich lautete Ja. Es stellt sich tatsächlich heraus, dass Sie dies auf verschiedene Arten tun können, und in diesem Artikel werde ich mir drei der gängigsten Methoden ansehen.
Vom einfachsten bis zum komplexesten betrachten wir die Verwendung von:
- ein Unterprozess
- ctypes
- Python C-Erweiterungen
Der Algorithmus, mit dem wir testen werden, heißt Levenshtein-Distanz (LD) Algorithmus. Der Levenshtein-Abstand zwischen zwei Wörtern ist die Mindestanzahl der Einzelzeichenbearbeitungen (Einfügungen, Löschungen oder Ersetzungen), die erforderlich sind, um ein Wort in ein anderes zu ändern. Sie ist nach dem sowjetischen Mathematiker Wladimir Levenshtein benannt, der die Metrik 1965 definierte. Sie findet Anwendung in verschiedenen Werkzeugen, beispielsweise in Rechtschreibprüfungen und optischen Zeichenerkennungssystemen.
Um Ihnen ein klareres Bild davon zu geben, worüber wir sprechen, finden Sie hier einige Beispiele.
Berechnen Sie den LD zwischen den Wörtern „e book“ und „black“.
- e book → baok (Ersetzung von „a“ für „o“),
- baok → zurück (Ersetzung von „c“ für „o“)
- zurück → schwarz (den Buchstaben „l“ hinzufügen)
In diesem Fall beträgt die LD additionally drei.
Berechnen Sie den LD zwischen den Wörtern „very good“ und „tremendous“.
- very good → tremendous (Buchstabe „b“ entfernen)
Die LD ist in diesem Fall einfach eins.
Wir programmieren den LD-Algorithmus in Python und C und richten dann Benchmarks ein, um zu testen, wie lange es dauert, ihn mit reinem Python-Code auszuführen, im Vergleich zur Zeit, die nötig ist, um ihn in C-Code auszuführen, der von Python aus aufgerufen wird.
Voraussetzungen
Da ich dies unter MS Home windows ausführte, brauchte ich eine Möglichkeit, C-Programme zu kompilieren. Der einfachste Weg, dies zu tun, bestand meiner Meinung nach darin, die Visible Studio Construct-Instruments für 2022 herunterzuladen. Damit können Sie C-Programme auf der Befehlszeile kompilieren.
Gehen Sie zur Set up zunächst zum Hauptmenü Visible Studio-Downloadseite. Auf dem zweiten Bildschirm sehen Sie ein Suchfeld. Typ „Construct-Instruments“ in das Suchfeld ein und klicken Sie auf Suchen. Die Suche sollte einen Bildschirm zurückgeben, der so aussieht:
Klicken Sie auf die Schaltfläche „Herunterladen“ und befolgen Sie die Installationsanweisungen. Sobald es installiert ist, sollten Sie in einem DOS-Terminalfenster, wenn Sie auf die kleine Plus-Schaltfläche klicken, um ein neues Terminal zu öffnen, eine Choice zum Öffnen einer „Entwickler-Eingabeaufforderung für VS 2022“ sehen.
Der Großteil meines Python-Codes wird auf einem Jupyter-Pocket book ausgeführt, daher sollten Sie eine neue Entwicklungsumgebung einrichten und Jupyter installieren. Tun Sie das jetzt, wenn Sie mitmachen möchten. Für diesen Teil verwende ich das UV-Werkzeug, Sie können aber auch die Methode verwenden, mit der Sie am besten zurechtkommen.
c:> uv init pythonc
c:> cd pythonc
c:> uv venv pythonc
c:> supply pythonc/bin/activate
(pythonc) c:> uv pip set up jupyterDer LD-Algorithmus in C
Wir benötigen leicht unterschiedliche Versionen des LD-Algorithmus in C, abhängig von der Methode, mit der er aufgerufen wird. Dies ist die Model für unser erstes Beispiel, in dem wir die Unterverarbeitung verwenden, um eine ausführbare C-Datei aufzurufen.
1/ Unterverarbeitung: lev_sub.c
#embody <stdio.h>
#embody <stdlib.h>
#embody <string.h>
static int levenshtein(const char* a, const char* b) {
size_t n = strlen(a), m = strlen(b);
if (n == 0) return (int)m;
if (m == 0) return (int)n;
int* prev = (int*)malloc((m + 1) * sizeof(int));
int* curr = (int*)malloc((m + 1) * sizeof(int));
if (!prev || !curr) { free(prev); free(curr); return -1; }
for (size_t j = 0; j <= m; ++j) prev(j) = (int)j;
for (size_t i = 1; i <= n; ++i) {
curr(0) = (int)i; char ca = a(i - 1);
for (size_t j = 1; j <= m; ++j) {
int price = (ca == b(j - 1)) ? 0 : 1;
int del = prev(j) + 1, ins = curr(j - 1) + 1, sub = prev(j - 1) + price;
int d = del < ins ? del : ins; curr(j) = d < sub ? d : sub;
}
int* tmp = prev; prev = curr; curr = tmp;
}
int ans = prev(m); free(prev); free(curr); return ans;
}
int fundamental(int argc, char** argv) {
if (argc != 3) { fprintf(stderr, "utilization: %s <s1> <s2>n", argv(0)); return 2; }
int d = levenshtein(argv(1), argv(2));
if (d < 0) return 1;
printf("%dn", d);
return 0;
}Um dies zu kompilieren, starten Sie eine neue Entwickler-Eingabeaufforderung für VS Code 2022 und geben Sie Folgendes ein, um sicherzustellen, dass wir die Kompilierung für die 64-Bit-Architektur optimieren.
(pythonc) c:> "%VSINSTALLDIRpercentVCAuxiliaryBuildvcvarsall.bat" x64Als nächstes können wir unseren C-Code mit diesem Befehl kompilieren.
(pythonc) c:> cl /O2 /Fe:lev_sub.exe lev_sub.cDadurch wird eine ausführbare Datei erstellt.
Benchmarking des Unterverarbeitungscodes
Geben Sie in einem Jupyter-Pocket book den folgenden Code ein, der für alle unsere Benchmarking-Exams gleich ist. Es generiert zufällige Kleinbuchstaben-Strings der Länge N und berechnet die Anzahl der Bearbeitungen, die erforderlich sind, um string1 in string2 umzuwandeln.
# Sub-process benchmark
import time, random, string, subprocess
import numpy as np
EXE = r"lev_sub.exe"
def rnd_ascii(n):
return ''.be part of(random.selection(string.ascii_lowercase) for _ in vary(n))
def lev_py(a: str, b: str) -> int:
n, m = len(a), len(b)
if n == 0: return m
if m == 0: return n
prev = listing(vary(m+1))
curr = (0)*(m+1)
for i, ca in enumerate(a, 1):
curr(0) = i
for j, cb in enumerate(b, 1):
price = 0 if ca == cb else 1
curr(j) = min(prev(j) + 1, curr(j-1) + 1, prev(j-1) + price)
prev, curr = curr, prev
return prev(m)Als nächstes folgt der eigentliche Benchmarking-Code und die Laufergebnisse. Um den C-Teil des Codes auszuführen, erzeugen wir einen Unterprozess, der die zuvor erstellte kompilierte C-Codedatei ausführt, die für die Ausführung benötigte Zeit misst und sie mit der reinen Python-Methode vergleicht. Wir führen jede Methode dreimal gegen einen 2000er- und einen 4000er-Satz zufälliger Wörter durch und nehmen die schnellste dieser Zeiten.
def lev_subprocess(a: str, b: str) -> int:
out = subprocess.check_output((EXE, a, b), textual content=True)
return int(out.strip())
def bench(fn, *args, repeat=3, warmup=1):
for _ in vary(warmup): fn(*args)
greatest = float("inf"); out_best = None
for _ in vary(repeat):
t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
if dt < greatest: greatest, out_best = dt, out
return out_best, greatest
if __name__ == "__main__":
instances = ((2000,2000),(4000, 4000))
print("Benchmark: Pythonvs C (subprocess)n")
for n, m in instances:
a, b = rnd_ascii(n), rnd_ascii(m)
py_out, py_t = bench(lev_py, a, b, repeat=3)
sp_out, sp_t = bench(lev_subprocess, a, b, repeat=3)
print(f"n={n} m={m}")
print(f" Python : {py_t:.3f}s -> {py_out}")
print(f" Subproc : {sp_t:.3f}s -> {sp_out}n")Hier sind die Ergebnisse.
Benchmark: Python vs C (subprocess)
n=2000 m=2000
Python : 1.276s -> 1768
Subproc : 0.024s -> 1768
n=4000 m=4000
Python : 5.015s -> 3519
Subproc : 0.050s -> 3519Das ist eine ziemlich deutliche Verbesserung der Laufzeit von C gegenüber Python.
2. cTypen: lev.c
ctypes ist ein Fremdfunktionsschnittstelle (FFI) Bibliothek, die direkt in die Standardbibliothek von Python integriert ist. Sie können damit Funktionen aus gemeinsam genutzten Bibliotheken laden und aufrufen, die in C geschrieben sind (DLLs unter Home windows, .so Dateien unter Linux, .dylib auf macOS) direkt aus Pythonohne dass ein komplettes Erweiterungsmodul in C geschrieben werden muss.
Hier ist zunächst unsere C-Model des LD-Algorithmus, die ctypes verwendet. Es ist quick identisch mit unserer Unterprozess-C-Funktion, mit der Hinzufügung einer Zeile, die es uns ermöglicht, Python zum Aufrufen der DLL zu verwenden, nachdem sie kompiliert wurde.
/*
* lev.c
*/
#embody <stdlib.h>
#embody <string.h>
/* under line contains this operate within the
* DLL's export desk so different applications can use it.
*/
__declspec(dllexport)
int levenshtein(const char* a, const char* b) {
size_t n = strlen(a), m = strlen(b);
if (n == 0) return (int)m;
if (m == 0) return (int)n;
int* prev = (int*)malloc((m + 1) * sizeof(int));
int* curr = (int*)malloc((m + 1) * sizeof(int));
if (!prev || !curr) { free(prev); free(curr); return -1; }
for (size_t j = 0; j <= m; ++j) prev(j) = (int)j;
for (size_t i = 1; i <= n; ++i) {
curr(0) = (int)i;
char ca = a(i - 1);
for (size_t j = 1; j <= m; ++j) {
int price = (ca == b(j - 1)) ? 0 : 1;
int del = prev(j) + 1;
int ins = curr(j - 1) + 1;
int sub = prev(j - 1) + price;
int d = del < ins ? del : ins;
curr(j) = d < sub ? d : sub;
}
int* tmp = prev; prev = curr; curr = tmp;
}
int ans = prev(m);
free(prev); free(curr);
return ans;
}Wenn wir ctypes verwenden, um C in Python aufzurufen, müssen wir unseren C-Code in eine Dynamic Hyperlink Library (DLL) und nicht in eine ausführbare Datei konvertieren. Hier ist der Construct-Befehl, den Sie dafür benötigen.
(pythonc) c:> cl /O2 /LD lev.c /Fe:lev.dllBenchmarking des Ctypes-Codes
Ich lasse das weg lev_py Und rnd_ascii Python-Funktionen in diesem Codeausschnitt sind identisch mit denen im vorherigen Beispiel. Geben Sie dies in Ihr Notizbuch ein.
#ctypes benchmark
import time, random, string, ctypes
import numpy as np
DLL = r"lev.dll"
levdll = ctypes.CDLL(DLL)
levdll.levenshtein.argtypes = (ctypes.c_char_p, ctypes.c_char_p)
levdll.levenshtein.restype = ctypes.c_int
def lev_ctypes(a: str, b: str) -> int:
return int(levdll.levenshtein(a.encode('utf-8'), b.encode('utf-8')))
def bench(fn, *args, repeat=3, warmup=1):
for _ in vary(warmup): fn(*args)
greatest = float("inf"); out_best = None
for _ in vary(repeat):
t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
if dt < greatest: greatest, out_best = dt, out
return out_best, greatest
if __name__ == "__main__":
instances = ((2000,2000),(4000, 4000))
print("Benchmark: Python vs NumPy vs C (ctypes)n")
for n, m in instances:
a, b = rnd_ascii(n), rnd_ascii(m)
py_out, py_t = bench(lev_py, a, b, repeat=3)
ct_out, ct_t = bench(lev_ctypes, a, b, repeat=3)
print(f"n={n} m={m}")
print(f" Python : {py_t:.3f}s -> {py_out}")
print(f" ctypes : {ct_t:.3f}s -> {ct_out}n")Und die Ergebnisse?
Benchmark: Python vs C (ctypes)
n=2000 m=2000
Python : 1.258s -> 1769
ctypes : 0.019s -> 1769
n=4000 m=4000
Python : 5.138s -> 3521
ctypes : 0.035s -> 3521Wir haben sehr ähnliche Ergebnisse wie beim ersten Beispiel.
3/ Python C-Erweiterungen: lev_cext.c
Bei der Verwendung von Python-C-Erweiterungen ist etwas mehr Arbeit erforderlich. Schauen wir uns zunächst den C-Code an. Der Grundalgorithmus bleibt unverändert. Wir müssen lediglich etwas mehr Gerüst hinzufügen, damit der Code aus Python aufgerufen werden kann. Es verwendet die API von CPython (Python.h), um Python-Argumente zu analysieren, den C-Code auszuführen und das Ergebnis als Python-Ganzzahl zurückzugeben.
Die Funktion levext_lev fungiert als Hülle. Es analysiert zwei String-Argumente aus Python (PyArg_ParseTuple) und ruft die C-Funktion auf lev_impl zur Berechnung der Entfernung, behandelt Speicherfehler und gibt das Ergebnis als Python-Ganzzahl (PyLong_FromLong) zurück. Die Methodentabelle registriert diese Funktion unter dem Namen „levenshtein“, sodass sie vom Python-Code aus aufgerufen werden kann. Schließlich definiert und initialisiert PyInit_levext das Modul levextwodurch es mit dem Befehl import levext in Python importierbar wird.
#embody <Python.h>
#embody <string.h>
#embody <stdlib.h>
static int lev_impl(const char* a, const char* b) {
size_t n = strlen(a), m = strlen(b);
if (n == 0) return (int)m;
if (m == 0) return (int)n;
int* prev = (int*)malloc((m + 1) * sizeof(int));
int* curr = (int*)malloc((m + 1) * sizeof(int));
if (!prev || !curr) { free(prev); free(curr); return -1; }
for (size_t j = 0; j <= m; ++j) prev(j) = (int)j;
for (size_t i = 1; i <= n; ++i) {
curr(0) = (int)i; char ca = a(i - 1);
for (size_t j = 1; j <= m; ++j) {
int price = (ca == b(j - 1)) ? 0 : 1;
int del = prev(j) + 1, ins = curr(j - 1) + 1, sub = prev(j - 1) + price;
int d = del < ins ? del : ins; curr(j) = d < sub ? d : sub;
}
int* tmp = prev; prev = curr; curr = tmp;
}
int ans = prev(m); free(prev); free(curr); return ans;
}
static PyObject* levext_lev(PyObject* self, PyObject* args) {
const char *a, *b;
if (!PyArg_ParseTuple(args, "ss", &a, &b)) return NULL;
int d = lev_impl(a, b);
if (d < 0) { PyErr_SetString(PyExc_MemoryError, "alloc failed"); return NULL; }
return PyLong_FromLong(d);
}
static PyMethodDef Strategies() = {
{"levenshtein", levext_lev, METH_VARARGS, "Levenshtein distance"},
{NULL, NULL, 0, NULL}
};
static struct PyModuleDef mod = { PyModuleDef_HEAD_INIT, "levext", NULL, -1, Strategies };
PyMODINIT_FUNC PyInit_levext(void) { return PyModule_Create(&mod); }Da wir dieses Mal nicht nur eine ausführbare Datei, sondern ein natives Python-Erweiterungsmodul erstellen, müssen wir den C-Code anders erstellen.
Dieser Modultyp muss mit den Headern von Python kompiliert und entsprechend mit der Python-Laufzeit verknüpft werden, damit er sich wie ein integriertes Python-Modul verhält.
Um dies zu erreichen, erstellen wir ein Python-Modul namens setup.py, das die setuptools-Bibliothek importiert, um diesen Prozess zu erleichtern. Es automatisiert:
- Finden der richtigen Embrace-Pfade für Python.h
- Übergabe der richtigen Compiler- und Linker-Flags
- Erstellen einer .pyd-Datei mit der richtigen Namenskonvention für Ihre Python-Model und Plattform
Tun Sie dies von Hand mit dem cl Der Compiler-Befehl wäre mühsam und fehleranfällig, da Sie alle diese Pfade und Flags manuell angeben müssten.
Hier ist der Code, den wir brauchen.
from setuptools import setup, Extension
setup(
identify="levext",
model="0.1.0",
ext_modules=(Extension("levext", ("lev_cext.c"), extra_compile_args=("/O2"))),
)Wir führen es mit normalem Python in der Befehlszeile aus, wie hier gezeigt.
(pythonc) c:> python setup.py build_ext --inplace
#output
operating build_ext
copying buildlib.win-amd64-cpython-312levext.cp312-win_amd64.pyd ->Benchmarking des Python-C-Erweiterungscodes
Hier ist nun der Python-Code zum Aufrufen unseres C. Auch hier habe ich die beiden Python-Hilfsfunktionen weggelassen, die gegenüber den vorherigen Beispielen unverändert geblieben sind.
# c-ext benchmark
import time, random, string
import numpy as np
import levext # ensure that levext.cp312-win_amd64.pyd is constructed & importable
def lev_extension(a: str, b: str) -> int:
return levext.levenshtein(a, b)
def bench(fn, *args, repeat=3, warmup=1):
for _ in vary(warmup): fn(*args)
greatest = float("inf"); out_best = None
for _ in vary(repeat):
t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
if dt < greatest: greatest, out_best = dt, out
return out_best, greatest
if __name__ == "__main__":
instances = ((2000, 2000), (4000, 4000))
print("Benchmark: Python vs NumPy vs C (C extension)n")
for n, m in instances:
a, b = rnd_ascii(n), rnd_ascii(m)
py_out, py_t = bench(lev_py, a, b, repeat=3)
ex_out, ex_t = bench(lev_extension, a, b, repeat=3)
print(f"n={n} m={m} ")
print(f" Python : {py_t:.3f}s -> {py_out}")
print(f" C ext : {ex_t:.3f}s -> {ex_out}n")Hier ist die Ausgabe.
Benchmark: Python vs C (C extension)
n=2000 m=2000
Python : 1.204s -> 1768
C ext : 0.010s -> 1768
n=4000 m=4000
Python : 5.039s -> 3526
C ext : 0.033s -> 3526Dies führte additionally zu den schnellsten Ergebnissen. Im zweiten Testfall oben erweist sich die C-Model als über 150-mal schneller als reines Python.
Nicht zu schäbig.
Aber was ist mit NumPy?
Einige von Ihnen fragen sich vielleicht, warum NumPy nicht verwendet wurde. Nun, NumPy eignet sich hervorragend für vektorisierte numerische Array-Operationen, wie z. B. Skalarprodukte, aber nicht alle Algorithmen lassen sich sauber auf die Vektorisierung abbilden. Die Berechnung von Levenshtein-Abständen ist ein von Natur aus sequenzieller Prozess, daher bietet NumPy keine große Hilfe. In diesen Fällen können Sie in C über einsteigen Unterprozess, ctypesoder ein native C-Erweiterung Bietet echte Laufzeitbeschleunigungen und ist dennoch von Python aus aufrufbar.
PS. Ich habe einige zusätzliche Exams mit Code durchgeführt, der für die Verwendung von NumPy geeignet battle, und es battle keine Überraschung, dass NumPy genauso schnell battle wie der aufgerufene C-Code. Das ist zu erwarten, da NumPy unter der Haube C verwendet und viele Jahre der Entwicklung und Optimierung hinter sich hat.
Zusammenfassung
In dem Artikel wird untersucht, wie Python-Entwickler Leistungsengpässe bei rechenintensiven Aufgaben wie der Berechnung überwinden können Levenshtein-Distanz– ein String-Ähnlichkeitsalgorithmus – durch Integration von C-Code in Python. Während Bibliotheken wie NumPy vektorisierte Operationen beschleunigen, bleiben sequentielle Algorithmen wie Levenshtein oft unempfindlich gegenüber den Optimierungen von NumPy.
Um dieses Downside anzugehen, habe ich demonstriert drei Integrationsmuster von einfach bis hochentwickelt, mit denen Sie schnellen C-Code aus Python aufrufen können.
Unterprozess. Kompilieren Sie den C-Code in eine ausführbare Datei (z. B. mit gcc oder Visible Studio Construct Instruments) und führen Sie ihn mithilfe des Unterprozessmoduls in Python aus. Dies ist einfach einzurichten und zeigt im Vergleich zu reinem Python bereits eine enorme Beschleunigung.
ctypes.Durch die Verwendung von ctypes kann Python Funktionen aus gemeinsam genutzten C-Bibliotheken direkt laden und aufrufen, ohne dass ein vollständiges Python-Erweiterungsmodul geschrieben werden muss. Dies macht es viel einfacher und schneller, leistungskritischen C-Code in Python zu integrieren, wodurch der Mehraufwand für die Ausführung externer Prozesse vermieden wird und Ihr Code größtenteils in Python verbleibt.
Python C-Erweiterungen . Schreiben Sie mithilfe der CPython-API (python.h) eine vollständige Python-Erweiterung in C. Dies erfordert mehr Setup, bietet aber die schnellste Leistung und reibungsloseste Integration, sodass Sie C-Funktionen so aufrufen können, als wären es native Python-Funktionen.
Die Benchmarks zeigen, dass C-Implementierungen des Levenshtein-Algorithmus ausgeführt werden über 100x schneller als reines Python. Während eine externe Bibliothek wie z NumPyzeichnet sich durch vektorisierte numerische Operationen aus, verbessert die Leistung für inhärent sequentielle Algorithmen wie Levenshtein jedoch nicht wesentlich, sodass die C-Integration in solchen Fällen die bessere Wahl ist.
Wenn Sie in Python an Leistungsgrenzen stoßen, kann die Auslagerung umfangreicher Berechnungen nach C zu enormen Geschwindigkeitsverbesserungen führen und ist eine Überlegung wert. Sie können einfach mit einem Unterprozess beginnen und dann für eine engere Integration und bessere Leistung zu CTypes oder vollständigen C-Erweiterungen wechseln.
Ich habe nur drei der beliebtesten Möglichkeiten zur Integration von C-Code in Python beschrieben, aber es gibt noch ein paar andere Methoden, über die ich Ihnen empfehle, sich darüber zu informieren, wenn Sie an diesem Thema interessiert sind.