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

Обоснование актуальности

При изучении алгоритмов лучше всего ознакомиться не только с их описанием и возможными реализациями в общем виде, но и то, как они работают на конкретных данных. Частично эту потребность покрывает отладчик (debugger), но значительно удобнее смотреть на gif картинку, на которой отображается только полезная информация, запрашиваемая пользователем. Визуализация алгоритмов часто оказывается более полезной, чем традиционный отладчик в определенных контекстах, благодаря своей способности обеспечивать высокоуровневое интуитивное представление всего алгоритмического процесса. Хотя отладчики превосходно справляются с выявлением и решением конкретных проблем в коде, им может не удаться понять общий ход и логику сложных алгоритмов. Визуализация алгоритма предлагает целостное представление, позволяя разработчикам наблюдать последовательное выполнение каждого шага и наблюдать за преобразованиями данных в графическом формате. Такая визуальная ясность особенно полезна для понимания сложных алгоритмов с многочисленными точками принятия решений и сложными ветвлениями. В отличие от отладчиков, которые сосредоточены на изоляции ошибок, визуализация алгоритма позволяет разработчикам понять поведение алгоритма в целом, помогая как выявлять неэффективности, так и оптимизировать общую структуру алгоритма. Эта более широкая перспектива может сыграть важную роль в создании более надежных и эффективных алгоритмов в различных вычислительных приложениях.

Поставленные цели и задачи

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

1. Разобраться с ООП в python, освоить работу с классами и “магическими методами”;

2. Разобраться с библиотекой Pillow, понять, как создавать отдельные изображения и gif анимации;

3. Анимировать перестановку и присвоение элементов одномерного массива;

4. Проверить работу библиотеки на простых алгоритмах.

Дорожная карта

Чтобы наиболее точно разобраться в материале и не потеряться, я составил дорожную карту. Ее можно разделить на 3 части:

1. Магические методы (init, setitem, getitem)

Магические методы — это специальные методы Python, которые начинаются и заканчиваются двойным подчеркиванием. Эти методы позволяют определить, как объекты ведут себя в различных обстоятельствах. Метод init — это важнейший магический метод Python, служащий конструктором класса. Он автоматически вызывается при создании объекта из класса и используется для инициализации его атрибутов.
Методы setitem и getitem — это магические методы, связанные с индексацией и подпиской в Python. Они используются, когда экземпляры класса рассматриваются как контейнеры или сопоставления. Метод setitem вызывается, когда элементу присваивается определенный индекс, а метод getitem вызывается, когда доступ к элементу осуществляется с использованием индекса.

2. Библиотека Pillow

Прототип библиотеки разрабатывается с применением библиотеки Pillow [4]. В данном случае использовалась часть функций и методов для решения трех конкретных задач:

1. Создание нового изображения;

2. Рисование поверх изображения (в том числе – текста);

3. Сохранения массива изображений в виде .gif анимации. Ниже представлен пример скрипта, который создает новое изображение:

self.data[index] = value

width = (cellSize + space + 2) * len(self.data)
height = cellSize * 6

dx = cellSize
dy = cellSize / 2

img = Image.new('RGB', (width, height), (255, 255, 255))
draw = ImageDraw.Draw(img)

font = ImageFont.truetype("arial.ttf", 15)

for i, n in enumerate(self.data):
    draw.rectangle([i * cellSize - cellSize / 2 + i * space + dx,
                    50 - cellSize / 2 + dy,
                    i * cellSize + cellSize / 2 + i * space + dx,
                    50 + cellSize / 2 + dy],
                    fill = None, outline = (0, 0, 0))

    if n != None:
        draw.text([i * cellSize - cellSize / 2 + i * space + dx,
                    50 - cellSize / 2 + dy],
                    text = str(n), fill = (0, 0, 0), font = font)

3. Анимация: текстовое описание, вывод формул

На рисунке ниже представлена схема, согласно которой формируется изображение массива. space - это расстояние между квадратами справа и слева, cellSize - сторона квадрата. Высота gif картинки равна cellSize*5, а длина уже зависит от количества квадратов, то есть от количества чисел в массиве.

Этот макет позволяет составить следующие формулы:

draw.rectangle([i * cellSize - cellSize / 2 + i * space + dx,
                50 - cellSize / 2 + dy,
                i * cellSize + cellSize / 2 + i * space + dx,
                50 + cellSize / 2 + dy],
                fill = None, outline = (0, 0, 0))
draw.text([i * cellSize - cellSize / 2 + i * space + dx,
            50 - cellSize / 2 + dy],
            text = str(n), fill = (0, 0, 0), font = font)

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

На языке Python это можно описать следующим образом:

left_x = left * cellSize + space * left
right_x = right * cellSize + space * right

left_y = 50
right_y = 50

main_frame = 0

width = (cellSize + space + 2) * len(self.data)
height = cellSize * 6

dx = cellSize
dy = cellSize / 2

font = ImageFont.truetype("arial.ttf", 15)

for main_frame in range(30):
    img = Image.new('RGB', (width, height), (255, 255, 255))
    draw = ImageDraw.Draw(img)

    for i, n in enumerate(self.data):
        if i not in [left, right]:
            draw.rectangle([i * cellSize - cellSize / 2 + i * space + dx,
                            50 - cellSize / 2 + dy,
                            i * cellSize + cellSize / 2 + i * space + dx,
                            50 + cellSize / 2 + dy],
                            fill = None, outline = (0, 0, 0))

            draw.text([i * cellSize - cellSize / 2 + i * space + dx,
                        50 - cellSize / 2 + dy],
                        text = str(n), fill = (0, 0, 0), font = font)

    draw.rectangle([left_x - cellSize / 2 + dx,
                    left_y - cellSize / 2 + dy,
                    left_x + cellSize / 2 + dx,
                    left_y + cellSize / 2 + dy], fill = None, outline = (0, 0, 0))

    draw.text([left_x - cellSize / 2 + dx,
                left_y - cellSize / 2 + dy],
                text = str(self.data[left]),
                fill = (0, 0, 0),
                font = font)

    draw.rectangle([right_x - cellSize / 2 + dx,
                    right_y - cellSize / 2 + dy,
                    right_x + cellSize / 2 + dx,
                    right_y + cellSize / 2 + dy], fill = None, outline = (0, 0, 0))

    draw.text([right_x - cellSize / 2 + dx,
                right_y - cellSize / 2 + dy],
                text = str(self.data[right]),
                fill = (0, 0, 0),
                font = font)

    main_frame += 1

    if main_frame < 10:
        left_y += 5
        right_y -= 5

    elif main_frame < 20:
        left_x -= (left - right) * (cellSize + space) / 10
        right_x += (left - right) * (cellSize + space) / 10

    elif main_frame < 29:
        left_y -= 5
        right_y += 5

    self.frames.append(img)

self.data[left], self.data[right] = self.data[right], self.data[left]

Мой результат

В рамках разработки была применена сортировка пузырьком:

arr = AnimatedList(size = 10)

for i in range(10):
    arr[i] = randint(-10, 10)

for i in range(10):
    for j in range(9):
        if arr.data[j] > arr.data[j + 1]:
            arr.swap(j, j + 1)
arr.save_animation('animation.gif')

Данный тип сортировки формирует gif анимацию. Gif анимация представляет собой перемещение элементов массива, который схематически показан на рисунке ниже.

Так как анимация выполняется без ошибок, то библиотека написана корректно. Следовательно, цель, поставленная в проекте, достигнута! Уррра!

Полный код

from random import randint
from PIL import Image, ImageDraw, ImageFont


class AnimatedList:
    def __init__(self, data = [], size = 0):
        self.frames = []

        self.data = [None for i in range(size)]

        if data:
            self.data = data

    def __setitem__(self, index, value):
        self.data[index] = value

        width = (cellSize + space + 2) * len(self.data)
        height = cellSize * 6

        dx = cellSize
        dy = cellSize / 2

        img = Image.new('RGB', (width, height), (255, 255, 255))
        draw = ImageDraw.Draw(img)

        font = ImageFont.truetype("arial.ttf", 15)

        for i, n in enumerate(self.data):
            draw.rectangle([i * cellSize - cellSize / 2 + i * space + dx,
                            50 - cellSize / 2 + dy,
                            i * cellSize + cellSize / 2 + i * space + dx,
                            50 + cellSize / 2 + dy],
                           fill = None, outline = (0, 0, 0))

            if n != None:
                draw.text([i * cellSize - cellSize / 2 + i * space + dx,
                           50 - cellSize / 2 + dy],
                          text = str(n), fill = (0, 0, 0), font = font)

        self.frames.append(img)

    def __getitem__(self, *args):
        pass

    def swap(self, left, right):
        left_x = left * cellSize + space * left
        right_x = right * cellSize + space * right

        left_y = 50
        right_y = 50

        main_frame = 0

        width = (cellSize + space + 2) * len(self.data)
        height = cellSize * 6

        dx = cellSize
        dy = cellSize / 2

        font = ImageFont.truetype("arial.ttf", 15)
        
        for main_frame in range(30):
            img = Image.new('RGB', (width, height), (255, 255, 255))
            draw = ImageDraw.Draw(img)

            for i, n in enumerate(self.data):
                if i not in [left, right]:
                    draw.rectangle([i * cellSize - cellSize / 2 + i * space + dx,
                                    50 - cellSize / 2 + dy,
                                    i * cellSize + cellSize / 2 + i * space + dx,
                                    50 + cellSize / 2 + dy],
                                   fill = None, outline = (0, 0, 0))

                    draw.text([i * cellSize - cellSize / 2 + i * space + dx,
                               50 - cellSize / 2 + dy],
                              text = str(n), fill = (0, 0, 0), font = font)

            draw.rectangle([left_x - cellSize / 2 + dx,
                            left_y - cellSize / 2 + dy,
                            left_x + cellSize / 2 + dx,
                            left_y + cellSize / 2 + dy], fill = None, outline = (0, 0, 0))

            draw.text([left_x - cellSize / 2 + dx,
                       left_y - cellSize / 2 + dy],
                      text = str(self.data[left]),
                      fill = (0, 0, 0),
                      font = font)

            draw.rectangle([right_x - cellSize / 2 + dx,
                            right_y - cellSize / 2 + dy,
                            right_x + cellSize / 2 + dx,
                            right_y + cellSize / 2 + dy], fill = None, outline = (0, 0, 0))

            draw.text([right_x - cellSize / 2 + dx,
                       right_y - cellSize / 2 + dy],
                      text = str(self.data[right]),
                      fill = (0, 0, 0),
                      font = font)

            main_frame += 1

            if main_frame < 10:
                left_y += 5
                right_y -= 5

            elif main_frame < 20:
                left_x -= (left - right) * (cellSize + space) / 10
                right_x += (left - right) * (cellSize + space) / 10

            elif main_frame < 29:
                left_y -= 5
                right_y += 5

            self.frames.append(img)

        self.data[left], self.data[right] = self.data[right], self.data[left]

    def save_animation(self, name):
        self.frames[0].save('/Users/egorkluychikov/Downloads'+name,
                            save_all = True,
                            append_images = self.frames[1:],
                            duration = 100,
                            loop = 0)

cellSize = 20

space = 5

arr = AnimatedList(size = 10)

for i in range(10):
    arr[i] = randint(-10, 10)

for i in range(10):
    for j in range(9):
        if arr.data[j] > arr.data[j + 1]:
            arr.swap(j, j + 1)
arr.save_animation('animation.gif')

Список источников:

1. Что такое объектно-ориентированное программирование (ООП)? - URL: https://itanddigital.ru/oop

2. Какая разница между объектом и классом. - URL: https://uchet-jkh.ru/i/kakaya-raznica-mezdu-obektom-i-klassom - Дата публикации: 19 августа 2023.

3. Что такое Self в Python — подробно на примерах. - URL: https://python-lab.ru/chto-takoe-self-v-python-podrobno-na-primerah

4. Pillow (PIL Fork) 10.2.0 documentation. - URL: https://pillow.readthedocs.io/en/stable/index.html

Буду рад услышать от вас вопросы и предложения, потому что сделан только прототип и его еще нужно доводить до ума.