От переводчика:
Весь текст набирался вручную если вы встретите опЯчатки, пожалуйста сообщите. Статья также дополнена инструкциями и ссылками на вспомогательные источники.
Приятного чтения!

Если вы программируете на Python, рано или поздно вы столкнётесь с ограничением скорости выполнения кода. Если вам когда-либо доводилось писать сложные вычислительные алгоритмы в Python(вычисление расстояния между строками, матричные операции или криптографическое хэширование), то вы понимаете, о чём я.

Конечно, большей частью работы может справиться библиотека NumPy, но что делать если алгоритм последовательный? Именно с этой проблемой я столкнулся, когда захотел перевести тестирование алгоритма, который определяет количество правок для преобразования одной строки в другую.

Я попробовал Python. Я попробовал NumPy. А затем обратился к C, который я впервые изучал в колледже десятилетия назад, но не использовал лет пятнадцать. И тут началось самое интересное.

Сперва я отвечу на вопрос: "А можно ли вызывать код на C из Python?". Поиска информацию на эту тему я могу сказать, что мы можем это сделать. Более того, оказалось, что это можно сделать несколькими способами, и в этой статья я рассмотрю три наиболее распространённых из них.

В порядке возрастания сложности мы рассмотрим:

1. subprocess (подпроцессы)

2. ctypes

3. Расширения Python на C

Алгоритм, который мы будем использовать для тестирования, называется расстоянием Левенштейна. Расстояние Левенштейна между двумя словами - это минимальное количество операций вставки, удаления или замены одного символа, необходимое для преобразования одного слова в другое. Алгоритм назван в честь советского математика Владимира Левенштейна, который определил эту метрику в 1965 году. Применяется алгоритм в различных инструментах, таких как системы проверки орфографии и оптического распознавания символов.

От переводчика:
Почитать о расстоянии Левенштейна вы можете по вот этой ссылке.

Что бы дать вам более четкое представление о том, о чём мы говорим, вот пара примеров.

Вычислим расстояние Левенштейна между словами "book" и "black".

1. book -> baok (замена 'o' на 'a')

2. baok -> back (замена 'o' на 'c')

3. back -> black (добавление 'l')

Таким образом, расстояние в данном случае равно трём.

Вычислим расстояние Левенштейна между словами "superb" и "super"

superb -> super (удаление буквы 'b')
Расстояние в этом случае равно единице.

Мы реализуем алгоритм Левенштейна на Python и C, затем проведём сравнительный анализ, чтобы оценить время выполнения на чистом Python и при вызове C-кода из Python.

Подготовка

Поскольку я работаю в Операционной системе Windows, мне нужен способ компиляции кода на C. Наиболее простым решением оказалась загрузка инструментов сборки Visual Studio 2022. Это позволит компилировать C-программы из командной строки.

Для установки сначала перейдите на главную страницу загрузки Visual Studio. На второй странице вы увидите поле поиска. Введите "Build Tools" в поле поиска и нажмите на Enter. В результате поиска отобразится страница, которая выглядит следующим образом:

Нажмите кнопку Download и следуйте инструкциям по установке. После завершения установки в терминале DOS, когда вы нажмёте на значок плюса, чтобы открыть новый терминал вы должны увидеть опцию "Developer command prompt for VS 2022"

Большая часть моего Python кода будет выполняться в Jupyter Notebook, поэтому вам нужно создать новое виртуальное окружение и установить Jupyter. Сделайте это сейчас, если хотите повторить процесс. Лично я использую этот инструмент UV, но вы можете выбрать любой другой удобный для вас способ.

c:\> uv init pythonc
c:\> cd pythonc
c:\pythonc> uv venv pythonc
c:\pythonc> source pythonc/bin/activate
(pythonc) c:\pythonc> uv pip install jupyter

C:\> mkdir pythonc
C:\> cd pythonc
C:\pythonc\> python -m venv .venv
C:\pythonc\> .venv\Scripts\activate
(.venv) C:\pythonc\> pip install jupyter numpy

Алгоритм Левенштейна на C

1) subprocess: lev_sub.c

Для разных способов вызова нам понадобятся отличающиеся версии алгоритма Левенштейна на C. Ниже представлена версия для первого примера, где мы используем subprocess для вызова исполняемого файла на C.

#include <stdio.h>
#include <stdlib.h>
#include <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 cost = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1, ins = curr[j - 1] + 1, sub = prev[j - 1] + cost;
            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 main(int argc, char** argv) {
    if (argc != 3) { fprintf(stderr, "usage: %s <s1> <s2>\n", argv[0]); return 2; }
    int d = levenshtein(argv[1], argv[2]);
    if (d < 0) return 1;
    printf("%d\n", d);
    return 0;
}

Скомпилируем этот код с помощью Develop Command Prompt for VS 2022 и введём команду, чтобы убедиться, что мы оптимизируем компиляцию для 64-битной архитектуры.

c:\pythonc> "%VSINSTALLDIR%VC\Auxiliary\Build\vcvarsall.bat" x64

Теперь, мы можем скомпилировать C код используя команду:

c:\pythonc> cl /O2 /Fe:lev_sub.exe lev_sub.c

После выполнения этой команды мы получим исполняемый файл.

Бенчмарки с subprocess

В Jupyter notebook, введём следующий код, который будет общим для всех наших текстов. Он генерирует случайные строки в нижнем регистре длиной N и вычисляет количество правок, необходимых для преобразования string1 в string2

# Sub-process benchmark
import time, random, string, subprocess
import numpy as np

EXE = r"lev_sub.exe"  

def rnd_ascii(n):
    return ''.join(random.choice(string.ascii_lowercase) for _ in range(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 = list(range(m+1))
    curr = [0]*(m+1)
    for i, ca in enumerate(a, 1):
        curr[0] = i
        for j, cb in enumerate(b, 1):
            cost = 0 if ca == cb else 1
            curr[j] = min(prev[j] + 1, curr[j-1] + 1, prev[j-1] + cost)
        prev, curr = curr, prev
    return prev[m]

Далее следует код бенчмаркинга и результаты запуска. Для выполнения C-части кода мы запускаем подпроцесс, который выполняет скомпилированный C-файл, созданный нами ранее и измеряет время его выполнения, сравнивая чистым Python методом. Мы запускаем каждый метод на наборах из 2000 и 4000 случайных слов по три раза и берём наилучшее из этих времён.

def lev_subprocess(a: str, b: str) -> int:
    out = subprocess.check_output([EXE, a, b], text=True)
    return int(out.strip())

def bench(fn, *args, repeat=3, warmup=1):
    for _ in range(warmup): fn(*args)
    best = float("inf"); out_best = None
    for _ in range(repeat):
        t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
        if dt < best: best, out_best = dt, out
    return out_best, best

if __name__ == "__main__":
    cases = [(2000,2000),(4000, 4000)]
    print("Benchmark: Pythonvs VS C (subprocess)\n")
    for n, m in cases:
        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")

Вот такой результат получился:

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 -> 3519

Это довольно значительное улучшение во время выполнения C по сравнению с Python.

2) ctypes: lev.c

Ctypes - это библиотека для работы с внешними функциями (foreign function interface, FFI), встроенная прямо в стандартную библиотеку Python. Она позволяет загружать и вызывать функции из разделяемых библиотек, написанных на С (DLLs в Windows, .so файлы в Linux, .dylib в macOS), напрямую из Python, без необходимости писать полноценный модуль расширения на C.

Сначала адаптируем написанную нами версию алгоритма Левенштейна на C для использования с ctypes. Она почти идентичная нашей C функции для subprocess, с добавлением одной строчки, которая позволяет Python вызвать DLL после её компиляции.

/* 
 * lev.c
*/

#include <stdlib.h>
#include <string.h>

/* below line includes this function in the 
 * DLL's export table so other programs 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 cost = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1;
            int ins = curr[j - 1] + 1;
            int sub = prev[j - 1] + cost;
            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;
}

Когда мы используем ctypes для вызова C из Python, нам нужно скомпилировать код на C в динамически подключаемую библиотеку (DLL), а не в исполняемый файла.

Для компиляции кода используйте команду:

c:\pythonc> cl /O2 /LD lev.c /Fe:lev.dll

Бенчмарки с ctypes

Я пропущу ранее реализованные нами функции lev_py и rnd_ascii, так как их функционал не изменяется. Введите в свой notebook.

#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 range(warmup): fn(*args)
    best = float("inf"); out_best = None
    for _ in range(repeat):
        t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
        if dt < best: best, out_best = dt, out
    return out_best, best

if __name__ == "__main__":
    cases = [(2000,2000),(4000, 4000)]
    print("Benchmark: Python vs NumPy vs C (ctypes)\n")
    for n, m in cases:
        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")

И мы получаем вот такие результаты

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 -> 3521

3) Расширение Python на C: lev_cext.c

Когда используешь Python на C расширении, придётся проделать немного больше работы. Сначала давайте рассмотрим код на C. Базовый алгоритм остаётся без изменений. Однако нам нужно добавить некоторую дополнительную "обвязку", чтобы код можно было вызвать из Python. Будет использоваться CPython API (Python.h) для парсинга аргументов Python, выполнения C-кода и возврата результата в виде целого числа Python.

Функция levext_lev служит обёрткой. Она парсит два строковых аргумента из Python с помощью PyArg_ParseTuple, вызывает C-функцию lev_impl для вычисления расстояния, обрабатывает потенциальные ошибки памяти и возвращает результат в виде целого числа Python через PyLong_FromLong. Таблица методов регистрирует эту функцию под именем "levenshtein", что позволяет использовать её в Python коде. Наконец, PyInit_levext определяет и инициализирует модуль levext, позволяя импортировать его в Python с помощью команды import levext.

#include <Python.h>
#include <string.h>
#include <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 cost = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1, ins = curr[j - 1] + 1, sub = prev[j - 1] + cost;
            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 Methods[] = {
    {"levenshtein", levext_lev, METH_VARARGS, "Levenshtein distance"},
    {NULL, NULL, 0, NULL}
};

static struct PyModuleDef mod = { PyModuleDef_HEAD_INIT, "levext", NULL, -1, Methods };
PyMODINIT_FUNC PyInit_levext(void) { return PyModule_Create(&mod); }

Так как на этот раз мы не просто используем файл, а нативное расширение Python, нам нужно компилировать C-код иначе.

Этот тип должен быть скомпилирован с заголовочными файлами Python и правильно связан со средой выполнения Python, чтобы вести себя как встроенный модуль Python.

Для этого мы создаём Python модуль под названием setup.py, который импортирует библиотеку setuptools для упрощения этого процесса. Она автоматизирует:

• поиск правильных путей включения для Python.h;

• передачу правильных флагов компилятора и компоновщика;

• создание .pyd файла с правильным соглашением об именовании для вашей версии Python и платформы.

Выполнять всё это вручную с помощью компилятора cl было бы утомительно и чревато ошибками, поскольку вам пришлось бы указывать все пути и флаги вручную.

Код:

from setuptools import setup, Extension
setup(
    name="levext",
    version="0.1.0",
    ext_modules=[Extension("levext", ["lev_cext.c"], extra_compile_args=["/O2"])],
)

Запускаем этот код с помощью командной строки.

c:\pythonc> python setup.py build_ext --inplace

#output
running build_ext
...
copying build\lib.win-amd64-cpython-312\levext.cp312-win_amd64.pyd ->

Бенчмарки с расширением

Вот Python код для вызова нашей C функции. Ещё раз отмечу, что я опустил две вспомогательные функции, которые не изменились по сравнению с предыдущими примерами.

# c-ext benchmark

import time
import levext  # make sure levext.cp312-win_amd64.pyd is built & importable

def lev_extension(a: str, b: str) -> int:
    return levext.levenshtein(a, b)

def bench(fn, *args, repeat=3, warmup=1):
    for _ in range(warmup): fn(*args)
    best = float("inf"); out_best = None
    for _ in range(repeat):
        t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
        if dt < best: best, out_best = dt, out
    return out_best, best

if __name__ == "__main__":
    cases = [(2000, 2000), (4000, 4000)]
    print("Benchmark: Python vs C (C extension)\n")
    for n, m in cases:
        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")

На выходе мы получаем:

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 -> 3526

Таким образом, этот метод показал наилучшие результаты. Во втором тестовом примере выше C версия оказалась более чем в 150 раз быстрее, чем чистый Python.

Неплохой результат.

Но что на счёт NumPy?

Некоторые из вас, возможно задаются вопросом, почему не была использована NumPy? Что ж, NumPy прекрасно подходит для векторных операций с числовыми массивами, таких как скалярные произведения, но не все алгоритмы можно аккуратно векторизовать. Вычисление расстояний Левенштейна по сути своей является последовательным процессом, поэтому NumPy не может существенно помочь. В таких случаях переход на C через subprocess, ctypes или нативное C расширение обеспечивает реальное ускорение выполнения, сохраняя возможность вызова из Python.

От автора:
P.S я провёл дополнительные тесты с кодом, который можно адаптировать для использования NumPy, и в итоге код с использованием NumPy оказался таким же быстрым, как и вызываемый C код.

Итог

В статье исследуется, как Python-разработчики могут преодолеть узкие места производительности в вычислительно сложных задачах, таких как вычисление расстояния Левенштейна - алгоритма, определения схожести строк путём интеграции С кода в Python. Хотя библиотеки вроде NumPy ускоряют векторные операции, последовательные алгоритмы, такие как разобранный нами, часто остаются невосприимчивыми к оптимизации NumPy.

Чтобы решить эту проблему, я продемонстрировал три подхода, от самых простых до наиболее продвинутых, которые позволяют вызывать быстрый C код из Python.

Subprocess
Скомпилируйте C код в исполняемый файл (например, с помощью gcc или Visual Studio Build Tools) и запускайте его из Python с помощью модуля subprocess. Этот метод прост в настройке и уже показывает огромное ускорение по сравнению с чистым Python.

Сtypes
Использование ctypes позволяет Python напрямую загружать и вызывать функции из общих библиотек C без необходимости написания полноценного модуля расширения Python. Это делает интеграцию критичного к производительности C кода в Python гораздо более простой и быстрой, избегая накладных расходов на запуск внешних процессов, при этом большая часть кода остаётся на Python.

Расширения Python на C
Написание полноценного расширения Python на C с использованием CPython API (python.h). Этот подход требует больше настроек, но предлагает наивысшую производительность и бесшовную интеграцию, позволяя вызывать C функции так, как если бы они были родными функциями Python.

Бенчмарки показывают, что C реализации алгоритма Левенштейна работают более чем в 100 раз быстрее, чем чистый Python. В то время как внешние библиотеки, такие как NumPy, превосходно справляются с векторными числовыми операциями, они не обеспечивают значительного повышения производительности для последовательных алгоритмов, таких как алгоритм Левенштейна, что делает интеграцию с C лучшим выбором в таких случаях.

Если вы столкнулись с ограничениями производительности в Python, вынесение сложных вычислений в C может обеспечить значительное ускорение, и этот подход стоит рассмотреть. Вы можете начать с простого подхода через subprocess, а затем перейти к ctypes или полноценным C расширениям для более тесной интеграции и лучшей производительности.

Я упомянул лишь три самых популярных способа интеграции C кода с Python, но существуют и другие методы, которые я рекомендую изучить, если эта тема вас заинтересовала.