Обучение ООП на примере реализации класса «Куча» в Python (1 часть)

Всем привет! Меня зовут Задойный Алексей, я ведущий архитектор в Группе «Иннотех» Холдинга Т1.

Алексей Задойный

Главный архитектор в Группе «Иннотех» Холдинга Т1

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

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

Обратный педагогический дизайн

Не будем детально вдаваться в концепцию обратного педагогического дизайна, но сразу определим задачи обучения: что должен уметь учащийся в итоге?

• Создавать классы.
• Создавать экземпляры объектов с использованием классов.
• Создавать методы внутри классов и использовать их в экземплярах.
• Реализовывать наследование классов.

Обратите внимание, что мы ставим ограниченный набор задач, в частности, не рассматриваем вопрос интерфейсов, абстрактных классов (и их методов) и тому подобное.

Это делается сознательно. Во-первых, невозможно охватить все темы единоразово. Во-вторых, конструктивнее будет создать отдельный урок, чтобы охватить какие-то из этих тем и повторить ранее изученные. Это концепция интервального повторения, позволяющая учащемуся на практике закрепить знания и умения.

После определения целей, определимся и с методами проверки полученных навыков. Наиболее распространённый современный метод: тестирование. Но оно не позволяет полноценно определить полноту владения навыком, только знания (да и то, учащийся может случайно угадать ответ). Более продуктивным будет использование практической задачи. Но как её проверить? Не станешь же вручную смотреть задачу каждого ученика в онлайн-курсе, где их могут быть сотни и тысячи. Очевидно, этот процесс можно автоматизировать, мы рассмотрим это во второй части материала.

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

И наконец, мы определяем, как и какие знания мы дадим учащемуся, чтобы он справился с этапом освоения навыка. Это могут быть текстовые или видеолекции. Важнее иное. Не следует загружать учащегося информацией, которая ему не пригодится. На каждом этапе мы даём ему ровно тот объём, который необходим для освоения следующего, чтобы он не утонул в потоке информации.

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

Обратите внимание, что этапы проектирования урока для учащегося идут в обратном порядке:

1. Определение результатов обучения (навыков, которые освоит учащийся).
2. Определение методов проверки освоения результатов.
3. Определение метода выработки навыков.
4. Определение, какой материал необходимо дать, чтобы сформировать необходимые знания.

Поэтому метод и называется обратным дизайном.

Предположим, все шаги пройдены. Но на чём мы будем вырабатывать навыки?

Классический подход обучения ООП — аналогии с объектами реального мира, в частности, примеры с животными. Не будем повторяться и выберем что-то более интересное и экзотичное. Это не значит, что на практике животных из ООП следует исключить, скорее лучше рассмотреть несколько разных примеров в зависимости от уровня подготовки учащихся.

Всё-таки, животные могут жить и в переменных… Попробуем задать нечто, где без классов и объектов будет тяжело.

Для этого рассмотрим структуру данных «куча», как наиболее показательную и достаточно простую в реализации.

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

1. Введение

В большинстве задач урока не требуется считывать данные или выводить что-то на печать самостоятельно, так как это должна делать проверяющая система. Учащийся лишь должен корректно реализовать все классы с их методами и атрибутами, согласно условиям задачи.

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

2. Задача на реализацию Heap

Примерами уроков, знакомящих с синтаксисом ООП, можно считать любой из следующих:

• Stepik,
• Codecademy.

Первая задача подготовительная на закрепление и разминку.

Необходимо реализовать класс Heap, поддерживающий всего 1 метод — __init__. Он в свою очередь должен поддерживать необязательный аргумент data.

При вызове метода у экземпляра класса должен появляться атрибут data.

• Если метод был вызван без атрибута, то с пустым списком внутри.
• Если в метод был передан список, то этот список должен быть передан в атрибут data.

Класс должен иметь оформленную документацию (docstring). Для реализации функционала нужно обратиться к стандарту PEP 257.

Мы даём это в примечании, а не раскрываем теорию отдельным шагом. Это нужно, чтобы студент изучил стандарт PEP самостоятельно, и чтобы побудить их читать и писать помогающие учиться комментарии (если это предусмотрено платформой).

Также задача проверяет, когда учащийся не задал в качестве значения атрибута data по умолчанию пустой список.

3. Теория — что такое «куча»

Понятие «кучи» демонстрируется на массиве из тестовых данных предыдущей задачи, который образует троичную «кучу».

Выводим количество элементов полностью заполненной троичной «кучи» с k уровнями через сумму членов геометрической прогрессии.

Если ввести понятие «кучи» с d детьми у каждого родителя, то для неё также будет выполнено это свойство, и можно найти число элементов в полностью заполненной d-«куче».

На основе этой формулы вводится формула высоты d-«кучи» с n-элементами.

В конце урока повторяем ряд выводов и полезных формул, включая формулу для определения количества элементов на определённом уровне.

4. Задача на визуализацию «кучи»

Для закрепления материала (и чтобы учащийся в дальнейшем мог упростить процесс отладки своего кода) введём промежуточную задачу, где необходимо представить объект «кучи» в виде псевдографики:

Необходимо:

1. Модифицировать метод __init__, добавив ещё один необязательный атрибут — child_count.
2. Создать служебный метод определения глубины дерева __get_depth__.
3. Создать метод __str__ (его назначение покажем на примере использования функции print для экземпляров класса).

После решения задачи учащийся получает доступ к форуму решений, где есть код, позволяющий построить более сложную и красивую псевдографику:

Следует учитывать особенности платформы, ведь поток вывода может отображаться не моноширинным шрифтом в отличие от Jupyter Notebook или консоли, поэтому ширина символов «┬», «┐», «├», «─» и «│» может отличаться от ширины пробела или цифры, что не позволит использовать данное решение на выбранной платформе обучения.

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

5. Мин-«куча», макс-«куча»

Уточняем определение «кучи» из предыдущего теоретического раздела. Если до сих пор «куча» была макс-«кучей», то теперь вводится понятие мин-«кучи».

Ссылки на видеолекции о кучах из курсов по алгоритмам:

• Очереди с приоритетами.
• Алгоритмы: теория и практика. Структуры данных.

Вводим понятие просеивания вверх и просеивания вниз.

Для иллюстрации процессов используем пошаговые иллюстрации, на каждой из которых меняемые местами элементы «кучи» выделяются цветом:

Предлагаем использовать просеивание вверх для пошагового наполнения «кучи» из пустого состояния, чтобы гарантировать её свойства.

А также использовать получение вершины «кучи», замену этого элемента на заведомо «тонущий» (например, на float(“-inf”) для макс-кучи или float(“inf”) для мин-«кучи») и последующее просеивание вниз, если необходимо извлечь элемент из «кучи».

Удаление такого элемента после просеивания может быть опасно, так как может нарушить свойства «кучи».

В конце урока вводятся формулы для определения индекса родителя по индексу ребёнка и наоборот.

6. Задача — просеивание вверх

Познакомимся с двумя служебными атрибутами:

• __name__,
• __class__.

Рекомендуется использовать эти служебные атрибуты, чтобы модифицировать метод __str__ класса Heap. Это позволит при наследовании классов HeapMax и HeapMin не переписывать этот метод.

Суть задачи — реализовать два класса HeapMax и HeapMin, наследовав их от Heap. И каждому добавить по два метода: sift_up(i) и insert(n).

Начиная с этой задачи грейдер блокирует использование модуля heapq, чтобы учащийся самостоятельно реализовывал методы кучи.

7. Задача — просеивание вниз

В задаче необходимо реализовать ещё два метода: sift_down(i) и pop().

При использовании метода pop вершина заменяется на «бесконечность», просеивается вниз не удаляется (даже если это можно сделать безопасно).

8. Очередь с приоритетами

Классическая задача на реализацию очереди с приоритетами.

Задача не проверяет наличие ООП-классов, наоборот для разнообразия следует потребовать работать с потоками ввода и вывода.

Вероятно, что учащийся, только что реализовавший «кучу», воспользуется своей реализацией, просто добавив вызовы конструктора класса, а также методов.

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

9. и 10. Сортировка «кучей»

Даём краткую иллюстрацию практического применения «кучи» для объединения и сортировки нескольких предварительно отсортированных массивов, а после этого отрабатываем этот навык.

11. и 12. Починка дерева

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

13. Изменение приоритета

Задача на изменение элемента и последующее его просеивание для восстановления свойств «кучи». Фактически задача на закрепление материала.

Что дальше?

А дальше самое интересное — необходимо взять учебную онлайн платформу и реализовать на ней проверку всех задач. =)

Но этим мы займёмся уже во 2 части…