Контекст

Когда приходит время взглянуть на производительность python, обычно оказывается, что python медленный, очень медленный, если сравнивать с компилируемыми языками и языками более низкого уровня, такими как C или C ++. Один из способов резко увеличить скорость вашего кода - векторизовать его с помощью numpy. Чтобы еще больше увеличить скорость, вы можете посмотреть на numba, который часто является хорошим выбором, чтобы просто превратить медленный алгоритм в действительно быстрый с помощью простого декоратора.

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

Интерфейс Python-C

Когда пришло время связать ваш код Python с некоторой библиотекой C, у вас в основном есть два варианта:

  • использовать сторонний инструмент / библиотеку, которая преобразует ваш код в соответствующий код C с помощью транспилятора.
  • вручную загрузить библиотеку C и упорядочить данные в соответствующую часть C

Транспайлер

Первый подход, который мне не нравится, - это использование промежуточного транспилятора, который преобразует ваш код Python в код C. Я знаю только Cython, но, возможно, существуют и другие. Cython очень близок к python (и поддерживает как собственный python, так и numpy), что является большим преимуществом. Однако я считаю, что он слишком близок к python, и настроить код, чтобы действительно улучшить производительность, может быть сложно. Иногда вам нужно объявить тип ваших переменных, иногда нет. У вас есть своего рода профилировщик, который поможет вам найти узкие места в вашем коде, что очень помогает, но на самом деле мне сложно научиться и трудно достичь максимальной производительности.

Итак, вместо того, чтобы пытаться настроить какой-то код, не похожий на питон-наверняка-не-c, почему бы нам напрямую не использовать код C? Вот где ctypes вступают в действие.

Маршаллинг с помощью ctypes

ctypes - это нативная библиотека на Python, которая, согласно ее документации

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

Что действительно интересно с ctypes, так это то, что вы можете разрабатывать свою библиотеку на чистом языке C, компилировать и отлаживать ее, как и любую другую библиотеку C, и просто использовать ее непосредственно в python! вид магии.

Загрузка библиотеки C действительно проста:

Теперь мы можем вызывать любую функцию библиотеки так же, как вы это делаете с модулем python. Единственная трудность - это осознать, что вы вызываете функцию C, поэтому она ожидает типизированных параметров, поэтому вы должны указать ей правильный тип аргумента.

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

Расстояние Левенштейна

Расстояние Левенштейна - это расстояние (математически говоря), которое измеряет расстояние между двумя струнами. Он измеряет количество символов для вставки, удаления или замены, чтобы соответствовать обеим строкам. Чем больше две струны различаются, тем больше расстояние.

Чтобы вычислить расстояние, мы допускаем три операции редактирования: удаление, вставка или замена символа. Иногда стоимость, связанная с каждой операцией, одинакова и равна 1, иногда мы устанавливаем стоимость операции замены равной 2, поскольку ее можно разложить на удаление с последующей операцией вставки. Алгоритм довольно прост и состоит в построении матрицы ранга MxN, где M - количество символов исходной строки плюс один, а N количество символов в целевой строке плюс один. Расстояние Левенштейна тогда является элементом D[M,N] матрицы.

Инициализация матрицы

Первым шагом к вычислению матрицы D является ее инициализация. Мы создаем пустую матрицу ранга MxN, где M - количество символов исходной строки плюс один, а N количество символов в целевой строке плюс один, чтобы разрешить использование нулевого символа #.

Затем первая строка матрицы вычисляет расстояние от нулевой строки до каждой подстроки целевой строки. Например, возьмем слово levenshtein в качестве исходной строки и levenstein в качестве цели (где буква h опущена). Затем для каждой подстроки цели у нас была стоимость ins_cost в каждом столбце. Действительно, чтобы добраться до строки 'l' из нулевой строки '#', мы должны вставить букву, поэтому расстояние '#' → 'l' равно ins_cost. Мы делаем то же самое, чтобы вычислить расстояние '#' → 'le', которое равно 2 x ins_cost, и так далее для первой строки. Рассуждения те же для первого столбца, но с использованием del_cost вместо ins_cost, поскольку расстояние от 'l' до '#' измеряется стоимостью удаления. При стоимости удаления и вставки, равной 1, результирующая начальная матрица будет

Расчет элементов матрицы

После инициализации матрицы самое время заполнить ее по алгоритму Левенштейна:

Итак, мы начинаем с первой буквы в двух строках, в нашем случае это буквы 'l', т.е. нас интересует ячейка D[1, 1].

  • Первая строка алгоритма говорит нам взять содержимое предыдущей строки текущего столбца (стоимость '#' → ‘l') и добавить к нему стоимость удаления.
  • Вторая начинается с добавления стоимости вставки предыдущего столбца текущей строки (стоимость 'l' → '#'), так что общая стоимость 'l' → '#' → 'l' равна 2
  • В последней строке мы замечаем, что буквы источника и цели совпадают для этой ячейки, поэтому мы просто берем стоимость предыдущей строки и предыдущего столбца, т.е. нам не нужна какая-либо редакция для выполнения этого шага.
  • Наконец, мы сохраняем минимум из трех затрат, который в данном случае будет равен 0.

Затем с помощью этого алгоритма мы перебираем каждую ячейку матрицы

Минимальное расстояние между двумя строками 'levenshtein' и 'levenstein' тогда равно 1, что совершенно логично, поскольку нам нужно удалить только одну букву, чтобы достичь цели из исходной строки.

Реализация алгоритма

Алгоритм Левенштейна довольно прост в реализации (и вы можете найти множество его версий), и использование языка C обычно не вызывает проблем. Идеальное время, чтобы попробовать ctypes! Итак, вот моя наивная реализация алгоритма на C:

Мы выполнили все шаги алгоритма от инициализации до итерации по каждой ячейке. Я решил вернуть всю матрицу, но мы могли бы выбрать вывод только расстояния.

Предыдущую реализацию можно было бы улучшить, если бы мы заметили, что нам нужно только получить доступ к содержимому предыдущей строки (или столбца) при вычислении. Следовательно, мы можем использовать только одну строку и обновлять ее содержимое по мере выполнения вычислений. Усовершенствованная версия реализации выглядит следующим образом (обратите внимание, что теперь мы возвращаем расстояние, а не всю матрицу, поскольку мы не храним ее в памяти)

Вызов функции C из Python

Теперь, когда мы создали нашу библиотеку C, мы можем загрузить ее прямо в код Python и вызвать в ней любую функцию благодаря ctypes.

Загрузить библиотеку с ctypes просто:

Единственная сложность связана с тем, что C - это типизированный язык, а не python, поэтому ctypes необходимо преобразовать переменную python в соответствующий тип C. То, что делается в строках 5 и 11, где мы явно сообщаем функции C, какой тип переменной она ожидает и какой тип результата мы получаем. В нашем случае мы передаем две строки (указатель на char в двоичном формате) плюс три целых числа и ожидаем в результате целого числа.

Все, что нам сейчас нужно, это вызвать функцию:

Заключение

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

Как мы уже упоминали, numba или cython - это альтернативные варианты товаров, но лично я считаю, что их сложнее использовать и оптимизировать. Для меня использование необработанного кода C имеет смысл, и мне очень нравится использовать ctypes с таким простым фрагментом кода.