Впервые я познакомился с расширениями C при чтении исходного кода PyTorch. Немного погуглив, я решил написать что-то чуть более полезное, чем примеры, приведенные в Документации Python.

У меня есть привычка изучать новый язык, реализуя в нем несколько часто используемых структур данных. И бинарное дерево — мой выбор для этого.

Мое бинарное дерево сможет:

  • Вставьте элемент.
  • Перечислите себя с обходом по порядку.
  • Перестроить себя из списка.

После реализации всех трех методов у нас будет алгоритм сортировки со сложностью O(NlogN) :)

По сути, я определяю новый класс BinTree, содержащийся в модуле bintree. Пустое дерево определяется как None.

Исходный код доступен в моем репозитории на GitHub.

Определение типа

Наша структура BinTree содержит свои данные, ее левый дочерний элемент и его правый дочерний элемент, все они имеют тип PyObject*, который в основном является диким «любым». Кроме того, у него есть PyObject_HEAD вверху, что делает его «расширенным PyObject». Для регистрации элемента необходимо знать его имя, тип и смещение в структуре C.

Аналогичным образом регистрируются методы класса. Чтобы зарегистрировать метод, необходимо указать его имя и базовую функцию C. Кроме того, способ приема аргументов будет указан с помощью флагов METH_. Например, METH_VARARGS заставляет базовую функцию C принимать «кортеж аргументов», который содержит все переданные позиционные аргументы.

В определении члена и метода используется терминатор NULL.

Ничего особенного здесь, на самом деле.

конструкторы/деструкторы

Обычно для объекта Python требуются три функции.

  • функция, которая выделяет память для объекта.
  • функция, которая инициализирует поля для объекта (__init__!)
  • функция, которая освобождает память для объекта.

Python управляет объектами путем подсчета ссылок: функция получает доступ к объекту, захватывая ссылку на объект. Когда количество ссылок на объект достигнет нуля, объект будет «уничтожен», и его память может быть безопасно освобождена ОС (например, путем вызова нескольких free).

При написании расширений C нам нужно вручную управлять подсчетом ссылок, явно вызывая Py_INCREF и Py_DECREF (два макроса, предоставляемые Python C API).

Возможно, вы заметили, что Py_INCREF нужно вызывать и на Py_None. Это потому, что None — это просто еще один объект. Невыполнение этого требования приведет к освобождению None, что является фатальной ошибкой, поскольку None даже не живет в куче памяти.

Что касается кода, BinTreeDealloc освобождает память, используемую обходом в обратном порядке. BinTreeNew вызывает низкоуровневые функции tp_alloc (которые, как я полагаю, представляют собой несколько malloc), чтобы получить достаточно памяти для типа (длина которого уже хранится в PyTypeObject, подробнее об этом позже). Затем мы заполняем все None и возвращаемся. BinTreeInit соответствует функции __init__ в классах Python. Важно использовать INCREF для объекта перед его сохранением (например, в self->data).

Затем определяется Type Object. Он содержит всю информацию о типе/классе с заполненными его членами, методами, конструктором/деструктором. Этот объект типа должен быть добавлен PyModule_AddObject, чтобы разрешить создание объекта BinTree.

Методы бинарного дерева

Вставлять

Метод вставки принимает два аргумента. Первый — это новый объект для вставки. Вторая функция сравнения. Поскольку наше бинарное дерево может принимать произвольный тип данных для своего поля data, эта функция сравнения принимает два объекта и возвращает целое число: 1 для большего, 0 для равного и -1 для меньшего. Как видите, Python C API для вызова функции Python довольно прост.

DECREF немного раздражает каждый раз, когда вы «создаете» объект Python (например, с помощью Py_BuildValue). Поскольку эти функции передают право собственности на возвращаемый объект вызывающей стороне (т. е. вашей функции), вы несете ответственность за его удаление: сохраните его где-нибудь, чтобы обработать позже, DECREF или передайте дальше.

Чтобы предотвратить утечку памяти, нам также нужно DECREF старый указатель после присваивания, как вы можете видеть из строк 28-30.

Перед возвратом важно вызвать INCREF, поскольку согласно правилу владения Python вы можете вернуть только тот объект, которым владеете.

Список

Этот действительно простой. И вы могли видеть, что Python C API любезно предоставляет методы для управления объектом Python List.

Из списка

Теперь это легко сделать, когда у нас есть метод вставки.

Просто запустите цикл for по переданному списку и продолжайте вставлять.

Попробуйте!

Тебе следует увидеть,

Обход двоичного дерева по порядку дает нам отсортированный список. Как мы могли видеть:

[-111, 999, 444, -222, 1] -> [-222, -111, 1, 444, 999]

в качестве проверки работоспособности нашего маленького бинарного дерева.