Впервые я познакомился с расширениями 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]
в качестве проверки работоспособности нашего маленького бинарного дерева.