@python__lounge

14 Python-пакетов, про которые вы скорее всего не знали

2021-05-27T18:25:39.373Z

Язык Python предоставляет всем пользователям возможность создавать свои пакеты и делиться ими со всем сообществом. Так появлялись очень популярные библиотеки для работы с данными (Pandas, Numpy, Matplotlib), для машинного обучения (TensorFlow, PyTorch), для веб разработки. Но есть много смешных, полезных или интересных пакетов, про которые вы вероятно никогда не слышали. Именно про них и пойдёт речь дальше.

Модули, которые не являются частью стандартной библиотеки Python, можно установить с помощью pip install <название пакета>.

tqdm

built-in: False

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

Для создания прогресс-бара необходим лишь один вызов функции:

from tqdm import tqdm
from tqdm.notebook import tqdm # для использования в Jupyter Notebook

for i in tqdm(range(10000)):
    ...

Пример прогресс-бара:

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

prettytable

built-in: False

Пакет для красивого оформления и вывода таблиц. Есть поддержка заголовков столбцов, импорт из CSV и SQL. Синтаксис опять же очень простой:

from prettytable import PrettyTable

x = PrettyTable()
x.field_names = ["Country", "Capital", "is_russia"]
x.add_row(["Russia", "Moscow", True])
x.add_rows([["Argentina", "Buenos Aires", False], ["Jamaica", "Kingston", False]])
x.add_column("Starts with A", [False, True, False])

print(x)

Вывод:

+-----------+--------------+-----------+---------------+
|  Country  |   Capital    | is_russia | Starts with A |
+-----------+--------------+-----------+---------------+
|   Russia  |    Moscow    |    True   |     False     |
| Argentina | Buenos Aires |   False   |      True     |
|  Jamaica  |   Kingston   |   False   |     False     |
+-----------+--------------+-----------+---------------+

Подробнее можно почитать на странице проекта.

emoji

built-in: False

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

Есть поддержка нескольких языков и синонимов (алиасов).

import emoji

print(emoji.emojize('Habr is :thumbsup:', use_aliases=True))  # Habr is 
print(emoji.demojize('Habr is '))  # Habr is :thumbsup:
print(emoji.demojize('Habr es ', language='es'))  # Habr es :pulgar_hacia_arriba:

Шпаргалку по названиям эмодзи можно посмотреть здесь

uuid

built-in: True

Пакет для генерации случайных id, поддерживает разные модели генерации. Например, uuid4 генерирует рандомный id, а uuid3 на основе md5 от названия объекта, для которого генерируется id. Как всегда, подробности можно найти в документации.

import uuid

print(uuid.uuid4())  # example: 2d8959d3-a5b3-42ef-8723-b4f4532f6d14
print(uuid.uuid3(uuid.NAMESPACE_URL, "https://habr.com/ru/users/otter18/"))  # e521cf18-5147-3137-9ca5-51bcbebe1b74

freegames

built-in: False

Хотите поиграть на рабочем месте, но игры слишком много весят? Или вы боитесь, что босс увидит, чем вы занимаетесь? Выход есть!

python -m pip install freegames

Теперь вы можете запустить любую игру из списка:

ant
bagels
bounce
cannon
connect
crypto
fidget
flappy
guess
life
maze
memory
minesweeper
pacman
paint
pong
simonsays
snake
tictactoe
tiles
tron

Для запуска игры snake используйте команду

python -m freegames.snake

Крестики-нолики:

Игра на запоминание чисел:

Все игры сделаны с помощью черепашки-рисовальщика.

howdoi

built-in: False

Ещё один прекрасный модуль, который улучшит вашу жизнь. Теперь вам не надо открывать несколько вопросов на StackOverflow, на которые нет понятного ответа с кодом. Вместо этого для вас решение найдёт howdoi:

$ howdoi install all python modules in project
pip install -r requirements.txt

Также есть поддержка подсветки, определённых сайтов и поисковых систем.

pyjokes

built-in: False

Если в вашей крови течёт PEP, а дома вас ждёт домашняя змея в клетке, то и шутки вам нужны соответствующие. Вы всегда можете получить их с помощью модуля pyjokes.

import pyjokes

print(pyjokes.get_joke())

Также есть отдельная категория с шутками Чака Норриса. Don't worry about tests, Chuck Norris's test cases cover your code too.

Fabulous

built-in: False

Вам не достаточно красивого вывода таблиц в консоль? А как насчёт вывода текста с тенями или даже картинок? Теперь это возможно! (Использовать только в небольших количествах во избежание перелома чувства прекрасного)

from fabulous import text, image
print(text.Text("Барсук!", color='#ff8c00', shadow=True, skew=5))
print(image.Image("барсук.png"))

art

built-in: False

Всё, что вам может понадобится для вывода красивых надписей или артов в терминал.

import art

print(art.randart())  # \m/(-_-)\m/
art.tprint("Habr", "mix")  # надпись Habr буквами из разных языков и шрифтов, которые могут не читаться вашими устройствами

Мне особенно нравится вывод больших букв:

import art

print(art.text2art("Habr", font='block'))

 .----------------.  .----------------.  .----------------.  .----------------.
| .--------------. || .--------------. || .--------------. || .--------------. |
| |  ____  ____  | || |      __      | || |   ______     | || |  _______     | |
| | |_   ||   _| | || |     /  \     | || |  |_   _ \    | || | |_   __ \    | |
| |   | |__| |   | || |    / /\ \    | || |    | |_) |   | || |   | |__) |   | |
| |   |  __  |   | || |   / ____ \   | || |    |  __'.   | || |   |  __ /    | |
| |  _| |  | |_  | || | _/ /    \ \_ | || |   _| |__) |  | || |  _| |  \ \_  | |
| | |____||____| | || ||____|  |____|| || |  |_______/   | || | |____| |___| | |
| |              | || |              | || |              | || |              | |
| '--------------' || '--------------' || '--------------' || '--------------' |
 '----------------'  '----------------'  '----------------'  '----------------'

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

pyperclip

built-in: False

Модуль для работы с буфером обмена. Подобные возможности также есть в модуле Tkinter (и я пользовался этим способом, потому что он выдавался в Гугле первым):

from tkinter import Tk

tk = Tk()
tk.withdraw()
tk.clipboard_clear()
tk.clipboard_append('New clipboard comtent')
tk.update()
tk.destroy()

Но pyperclip делает жизнь проще:

import pyperclip
pyperclip.copy('Habr is the best!')
pyperclip.paste()

Под капотом стоит обработка версии системы и поиск соответствующего способа работы с буфером обмена. Например, с помощью командной строки.

moviepy

built-in: False

Пакет для редактирования видео. Имеет такие полезные функции как: обрезка, добавления текста поверх ихображения, поворот видео, создания GIF, коррекция цвета и много другое.

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

Пример из официальной документации: наложение двух видеофайлов и движущегося текста

from moviepy.editor import *

# импорт основного видеоряда
ukulele = VideoFileClip("ukulele.MOV", audio=False).subclip(60+33, 60+50).crop(486, 180, 1196, 570)
w,h = moviesize = ukulele.size

# импорт пианино
piano = (VideoFileClip("piano.mp4",audio=False).subclip(30,50).resize((w/3,h/3)).margin( 6,color=(255,255,255).margin( bottom=20, right=20, opacity=0).set_pos(('right','bottom')) )

# создание текста
txt = TextClip("V. Zulkoninov - Ukulele Sonata", font='Amiri-regular', color='white',fontsize=24)
txt_col = txt.on_color(size=(ukulele.w + txt.w,txt.h-10), color=(0,0,0), pos=(6,'center'), col_opacity=0.6)

# создание траектории движения текста: зависимость координаты от времени
txt_mov = txt_col.set_pos(lambda t: (max(w/30,int(w-0.5*w*t)), max(5*h/6,int(100*t))))

# генерация финального результата
final = CompositeVideoClip([ukulele,txt_mov,piano])
final.subclip(0,5).write_videofile(".avi",fps=24,codec='libx264')

Результат: https://youtu.be/AqGZ4JFkQTU

Antigravity

built-in: True

При подключении модуля antigravity в браузере открывается комикс с сайта xkcd.com (xkcd.ru — версия на русском). В нём рассказывается про то, насколько язык Python простой. Перевод с английского языка:

I wrote 20 short programs in Python yesterday. It was wonderful. Perl, I'm leaving you.

Приписка автора комикса: I wrote 20 short programs in Python yesterday. It was wonderful. Perl, I'm leaving you.

hello

built-in: True

Все же помнят свой первый вывод Hello World!? Теперь это сделать ещё легче, надо просто написать в консоли import __hello__.

please-debug-my-code

built-in: False

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

import please_debug_my_code

print(please_debug_my_code.please_help("code", "..."))

Только он иногда не в настроении, и его надо хорошо попросить (или прочитать исходный код и понять, что он любит).

Заключение

Библиотека pypi содежит более 307 тысяч проектов, среди которых вы можете найти подходящий пакет в любой жизненной ситуации. А если такого пакета нет, то почему бы не создать его и не поделиться им со всеми?

Разукрашиваем вывод в консоли: теория и практика

2021-05-24T16:07:42.920Z

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

Управляющие последовательности ANSI

ANSI escape sequences или Управляющие последовательности ANSI — это стандарт, дающий возможность управлять курсором, цветами, начертание в текстовых консолях. Такие последовательности воспринимаются отрисовщиком терминала, как команды отображать последующий текст в определенном формате. Есть также последовательность, которая сбрасывает предыдущие команды, и отображение текста становиться обычным. Существует несколько форматов управляющих последовательностей, различающихся возможностями и появившимися в разных версиях кодировок. Поговорим об этих форматах подробнее.

8 основных цветов и стили

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

Чтобы изменить текущий цвет шрифта или фона можно использовать следущий синтаксис:

Начинается управляющая последовательность с любого из этих трёх представлений: \x1b[ (hex) или \u001b[ (Unicode) или \033[ (oct)
Далее следуют аргументы, разделённые между собой ;(можно указывать в любом порядке)
В конце ставится буква m

Возможные аргументы

Изменения стиля

Изменения цвета шрифта

Изменения цвета фона

Бонус: другие интересные модификаторы, которые могут поддерживаться не всеми платформами

Модификатор Код 38 RGB цвет (см. раздел "Совсем много цветов") 21 Двойное подчёркивание 51 Обрамлённый 52 Окружённый 53 Надчёркнутый

Пример корректного синтаксиса: \033[3;36;44m. После вывода этой конструкции стиль будет изменён для всего последующего текста. Чтобы вернуться к изначальному состоянию можно использовать \033[0m, тогда весь текст с этого места вернётся к изначальному форматированию.

Давайте поэкспементируем. Для примеров я буду использовать Python.

Важно заметить, что форматирование повлияло и на консоль питона, а не только на ее вывод. Именно поэтому очень важно закрывать все "тэги" изменения форматирования.

Часто используемые сочетания (copy-paste-able)

Больше цветов: аж целых 256

Некоторые терминалы поддерживают вывод целых 256 цветов. Если команда echo $TERM выводит xterm-256color, то ваш терминал всё корректно обработает.

В этом формате синтаксис немного другой:

Для генерации кодов цветов можно использовать генератор.

А палитру доступных цветов можно увидеть на картинке ниже.

Палитра цветов

Совсем много цветов

Этот формат не всегда поддерживается стандартными консолями.

Некотрые будут негодовать: "256 цветов и нет моего любимого терракотового, какой ужас!". Для таких ценителей существует формат, который уже поддерживает 24 битные цвета (3 канала RGB по 256 градаций).

Для не ценителей поясню, что терракотовый кодируется как — (201, 100, 59) или #c9643b.

Синтаксис в этом формате выглядит вот так:

\033[38;2;⟨r⟩;⟨g⟩;⟨b⟩m — цвет текста
\033[48;2;⟨r⟩;⟨g⟩;⟨b⟩m — цвет фона

Python: Использование библиотеки Colorama

Библиотека Colorama позволяет форматировать текст, не запоминая коды цветов. Рассмотрим её использование на примере:

from colorama import init, Fore, Back, Style

init()

print(Fore.RED + 'some red text\n' + Back.YELLOW + 'and with a yellow background')
print(Style.DIM + 'and in dim text\n' + Style.RESET_ALL + 'back to normal now')

Вывод программы:

Style позволяет изменить стиль, Fore — цвет шрифта, Back — цвет фона. Использовать переменные из colorama нужно также, как и коды изменения стиля. Но плюс использования библиотеки в том, что Fore.RED более читаем, чем \033[0;31m

Если в colorama.init() указать параметр autoreset=True, то стиль будет автоматически сбрасываться (в конец каждого print будут добавлены сбрасывающие стили последовательности), поэтому вам не придётся об этом каждый раз вспоминать.

А что не так с Windows?

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

Но colorama.init() сделает всё за вас в большинстве версий Windows. Однако если вы используете другую операционную систему, то функцию init() вызывать в начале программы не обязательно. Также некоторые IDE на Windows (например, PyCharm) тоже поддерживают цвета без каких-либо махинаций.

А еще Windows не поддерживает многие модификаторы, такие как жирный текст. Подробнее можно почитать на странице Colorama

Termcolor

Ещё одна библиотека для вывода цветного текста с более удачным, на мой взлгяд, синтаксисом.

from termcolor import colored, cprint

text = colored('Hello, Habr!', 'red', attrs=['blink'])
print(text)
cprint('Hello, Habr!', 'green', 'on_red')

Кстати, проблему с Windows всё ещё можно починить с помощью colorama.init()

Выводы

Стандартные 8 цветов позволяют разнообразить вывод в консоль и расставить акценты. 256 цветов намного расширяют возможности, хотя и поддерживаются не всеми консолями. Windows, к сожалению, не поддерживает многие основные модификаторы, например, курсив. Также есть некоторые цвета, которые не прописаны в стандартах, но могут поддерживаться вашей операционной системой. Если вы хотите больше цветов, то вы можете поискать их в Гугле.

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

Источники

Картинки с синтаксисом из статьи
Генератор из статьи на Хабре
ANSI escape code

Распознавание некоторых современных CAPTCHA

2021-05-22T17:11:07.095Z

Именно так называлась работа, представленная мной на Балтийском научно-инженерном конкурсе, и принёсшая мне очаровательную бумажку с римской единичкой, а также новенький ноутбук.

Работа заключалась в распознавании CAPTCHA, используемых крупными операторами сотовой связи в формах отправки SMS, и демонстрации недостаточной эффективности применяемого ими подхода. Чтобы не задевать ничью гордость, будем называть этих операторов иносказательно: красный, жёлтый, зелёный и синий.

Проект получил официальное название Captchure и неофициальное Breaking Defective Security Measures. Любые совпадения случайны.

Как ни странно, все (ну, почти все) эти CAPTCHA оказались довольно слабенькими. Наименьший результат — 20% — принадлежит жёлтому оператору, наибольший — 86% — синему. Таким образом, я считаю, что задача «демонстрации неэффективности» была успешно решена.

Причины выбора именно сотовых операторов тривиальны. Уважаемому Научному Жюри я рассказывал байку о том, что «сотовые операторы имеют достаточно денег, чтобы нанять программиста любой квалификации, и, в то же время, им необходимо минимизировать количество спама; таким образом, их CAPTCHA должны быть довольно мощными, что, как показывает моё исследование, совсем не так». На самом же деле всё было гораздо проще. Я хотел набраться опыта, ~~взломав~~ распознав какую-нибудь простую CAPTCHA, и выбрал жертвой CAPTCHA красного оператора. А уже после этого, задним числом родилась вышеупомянутая история.

Итак, ближе к телу. Никакого мегапродвинутого алгоритма для распознавания всех четырёх видов CAPTCHA у меня нет; вместо него я написал 4 различных алгоритма для каждого вида CAPTCHA по отдельности. Однако, несмотря на то, что алгоритмы в деталях различны, в целом они оказались очень похожими.

Как и многие авторы до меня, я разбил задачу распознавания CAPTCHA на 3 подзадачи: предварительную обработку (препроцесс), сегментацию и распознавание. На этапе препроцесса из исходного изображения удаляются различные шумы, искажения и пр. В сегментации из исходного изображения выделяются отдельные символы и производится из постобработка (например, обратный поворот). При распознавании символы по одному обрабатываются предварительно обученной нейросетью.

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

Код написан на Python с применением библиотек OpenCV и FANN, которые не ставятся без напильника приличных размеров и бубна впридачу. Поэтому мои результаты будет воспроизвести непросто — по крайней мере, до тех пор, пока авторы вышеупомянутых библиотек не сделают нормальные привязки для Python.

RedКак я уже сказал, первым кроликом я выбрал именно эту CAPTCHA. Думаю, несколько примеров прояснят ситуацию:

Вот-вот, и мне тоже сначала показалось, что она очень простая… Однако, это впечатление возникло не на пустом месте. Итак:

Цвета исчерпываются градациями серого, причём символы — светлые, фон — тёмный
Отсутствует дополнительный шум
Постоянные искажения (то есть не изменяющиеся от картинки к картинке)
Символов всегда ровно пять
Размеры символов приблизительно одинаковы
Символы почти всегда связны

Казалось, всё это сводит на нет достоинства этой CAPTCHA:

Слипающиеся буквы
Мерзкий дырявый шрифт
Очень маленький размер (83x23 px)

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

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

Далее я применяю пороговое преобразование (в народе Threshold) с t=200 и инвертирую изображение:

Наконец, белым закрашиваются мелкие (меньше 10px) чёрные связные области:

Далее следует сегментация. Как я уже сказал, здесь применяется поиск компонентов связности:

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

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

Для объяснения принципа работы такого алгоритма придётся немного углубиться в матчасть. Обозначим количество найденных сегментов за n, а массив ширин (правильно сказал, да?) всех сегментов за widths[n]. Будем считать, что если после вышеупомянутых этапов n > 5, изображение распознать не удалось. Рассмотрим все возможные разложения числа 5 на целые положительные слагаемые. Их немного — всего 16. Каждое такое разложение соответствует некоторой возможной расстановке символов по найденным компонентам связности. Логично предположить, что чем шире получившийся сегмент, тем больше символов он содержит. Из всех разложений пятёрки выберем только те, в которых количество слагаемых равно n. Поделим каждый элемент из widths на widths[0] — как бы нормализуем их. То же самое проделаем со всеми оставшимися разложениями — поделим каждое число в них на первое слагаемое. А теперь (внимание, кульминация!) заметим, что получившиеся упорядоченные n-ки можно мыслить как точки в n-мерном пространстве. С учётом этого, найдём ближайшее по Евклиду разложение пятёрки к нормализованному widths. Это и есть искомый результат.

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

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

Наконец, распознавание. Как я уже говорил, для него я применяю нейросеть. Для её обучения сначала я прогоняю две сотни изображений под общим заголовком trainset через уже написанные и отлаженные первые два этапа, в результате чего получаю папку с большим количеством аккуратно нарезанных сегментов. Затем руками вычищаю мусор (результаты неправильной сегментации, например), после чего результат привожу к одному размеру и отдаю на растерзание FANN. На выходе получаю обученную нейросеть, которая и используется для распознавания. Эта схема дала сбой только один раз — но об этом позже.

Новые фичи в Python 3.10

2021-05-14T19:23:15.963Z

Если вам хочется попробовать все фичи великолепной последний версии Python, нужно установить альфа или бета-версию. Однако учитывая, что эти версии не стабильны, мы не хотим перезаписывать дефолтную установку языка. Будем устанавливать альфу Python 3.10 рядом с текущим интерпретатором. И в преддверии старта нового потока курса Fullstack-разработчик на Python — обозревать все новшества новой версии языка.

Сделать это можно выполнив эти команды:

wget https://www.python.org/ftp/python/3.10.0/Python-3.10.0a6.tgz
tar xzvf Python-3.10.0a6.tgz
cd Python-3.10.0a6
./configure --prefix=$HOME/python-3.10.0a6
make
make install
$HOME/python-3.10.0a6/bin/python3.10

После запуска кода выше вы увидите приветствие от среды разработки IDLE:

Python 3.10.0a6 (default, Mar 27 2021, 11:50:33) [GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>

А теперь, с установленным Python, мы можем посмотреть на все новые фичи и изменения.

Улучшения в проверке типов

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

# Function that accepts either `int` or `float`
# Old:
def func(value: Union[int, float]) -> Union[int, float]:
    return value

# New:
def func(value: int | float) -> int | float:
    return value

Кроме того, это простое улучшение не ограничивается только аннотациями типа, оно может применяться с функциями isinstance() и issubclass():

isinstance("hello", int | str)
# True

Изменения синтаксиса псевдонима типа

В более ранних версиях Python добавлены псевдонимы типов, позволяющие создавать синонимы пользовательских классов. В Python 3.9 и более ранних версиях псевдонимы записывались так:

FileName = str

def parse(file: FileName) -> None:
    ...

Здесь FileName - псевдоним базового типа строки Python. Однако, начиная с Python 3.10, синтаксис определения псевдонимов типов будет изменён:

FileName: TypeAlias = str

def parse(file: FileName) -> None:
    ...

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

Кроме этих 2 изменений появилось другое улучшение модуля typing - в предложениях по улучшению номер 612 оно называется Parameter Specification Variables. Однако это не то, что вы найдете в основной массе кода на Python, поскольку эта функциональность используется для пересылки параметра типов от одного вызываемого типа к другому вызываемому типу, например, в декораторах. Если вам есть где применить эту функциональность, посмотрите её PEP.

bit_count()

Начиная с Python 3.10, чтобы посчитать количество битов в двоичном представлении целого числа, можно вызвать int.bit_count(). Функция известна как Population Count (popcount):

value = 42
print(bin(value))
# '0b101010'
print(value.bit_count())
# 3

Это, безусловно, хорошо, но давайте будем реалистами: реализация этой функции не так уж сложна, на самом деле это всего лишь одна строка:

def bit_count(value):
    return bin(value).count("1")

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

Модуль distutils устарел

В новой версии функции не только добавляются, но также удаляются или объявляются устаревшими. Это касается пакета distutils, который объявлен устаревшим в 3.10 и будет удален в 3.12. На какое-то время его заменили пакетами setuptools и packaging, поэтому если вы работаете с каким-то из этих пакетов, у вас все будет хорошо. При этом вы, вероятно, должны проверить, не используется ли distutils в вашем коде, и начать готовиться к тому, чтобы в ближайшее время избавиться от этого модуля.

Синтаксис менеджера контекста

Контекстные менеджеры отлично подходят, чтобы открывать и закрывать файлы, работать с соединениями баз данных и делать многое другое, а в Python 3.10 они станут немного удобнее. Изменение позволяет в скобках указывать несколько контекстных менеджеров, что удобно, если вы хотите создать в одном операторе with несколько менеджеров:

with (
    open("somefile.txt") as some_file,
    open("otherfile.txt") as other_file,
):
    ...

from contextlib import redirect_stdout

with (open("somefile.txt", "w") as some_file,
      redirect_stdout(some_file)):
    ...

В коде выше видно, что мы даже можем ссылаться на переменную, созданную одним контекстным менеджером (... as some_file) в следующем за ним менеджере!

Это всего лишь два из многих новых форматов в Python 3.10. Улучшенный синтаксис довольно гибок, поэтому я не буду утруждать себя и показать все возможные варианты; я почти уверен, что новый Python обработает всё, что вы ему скормите.

Улучшения в производительности

Как и во всех последних релизах Python, с Python 3.10 придут улучшения производительности. Первое — оптимизация конструкторов str(), bytes() и bytearray(), которые должны стать примерно на 30% быстрее (фрагмент, адаптированный из примера в баг-трекере Python):

~ $ ./python3.10 -m pyperf timeit -q --compare-to=python "str()"
Mean +- std dev: [python] 81.9 ns +- 4.5 ns -> [python3.10] 60.0 ns +- 1.9 ns: 1.36x faster (-27%)
~ $ ./python3.10 -m pyperf timeit -q --compare-to=python "bytes()"
Mean +- std dev: [python] 85.1 ns +- 2.2 ns -> [python3.10] 60.2 ns +- 2.3 ns: 1.41x faster (-29%)
~ $ ./python3.10 -m pyperf timeit -q --compare-to=python "bytearray()"
Mean +- std dev: [python] 93.5 ns +- 2.1 ns -> [python3.10] 73.1 ns +- 1.8 ns: 1.28x faster (-22%)

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

Кроме того, есть еще несколько оптимизаций в разных частях ядра языка. Подробности о них вы можете найти в этих записях баг-трекера Python: bpo-41718, bpo-42927 и bpo-43452.

Сопоставление шаблонов

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

Простое сопоставление шаблонов состоит из ключевого слова match, за которым следует выражение, а его результат проверяется на соответствие шаблонам, указанным в последовательных операторах case:

def func(day):
    match day:
        case "Monday":
            return "Here we go again..."
        case "Friday":
            return "Happy Friday!"
        case "Saturday" | "Sunday":  # Multiple literals can be combined with `|`
            return "Yay, weekend!"
        case _:
            return "Just another day..."

В этом простом примере мы воспользовались переменной day как выражением, которое затем сравнивается с конкретными строками в case. Кроме строк, вы также можете заметить case с маской _ — это эквивалент ключевого слова default в других языках. Хотя этот оператор можно опустить, в этом случае может произойти no-op, по существу это означает, что вернётся None.

Еще один момент, на который стоит обратить внимание в коде выше, это оператор |, позволяющий комбинировать несколько литералов | (другой его вариант — or).

Как я уже упоминал, новое сопоставление шаблонов не заканчивается на базовом синтаксисе, напротив — оно привносит дополнительные возможности, например сопоставление сложных шаблонов:

def func(person):  # person = (name, age, gender)
    match person:
        case (name, _, "male"):
            print(f"{name} is man.")
        case (name, _, "female"):
            print(f"{name} is woman.")
        case (name, age, gender):
            print(f"{name} is {age} old.")
        
func(("John", 25, "male"))
# John is man.

Во фрагменте выше мы воспользовались кортежем как выражением сопоставления. Однако мы не ограничены кортежами: работать будет любой итерируемый тип. Также выше видно, что маска (wildcard) _ может применяться внутри сложных шаблонов и не только сама по себе, как в предыдущих примерах. Простые кортежи или списки — не всегда лучший подход, поэтому, если вы предпочитаете классы, код можно переписать так:

from dataclasses import dataclass

@dataclass
class Person:
    name: str
    age: int
    gender: str
    
def func(person):  # person is instance of `Person` class
    match person:
        # This is not a constructor
        case Person(name, age, gender) if age < 18:  # guard for extra filtering
            print(f"{name} is a child.")
        case Person(name=name, age=_, gender="male"):  # Wildcard ("throwaway" variable) can be used
            print(f"{name} is man.")
        case Person(name=name, age=_, gender="female"):
            print(f"{name} is woman.")
        case Person(name, age, gender):  # Positional arguments work
            print(f"{name} is {age} years old.")

func(Person("Lucy", 30, "female"))
# Lucy is woman.
func(Person("Ben", 15, "male"))
# Ben is a child.

Здесь видно, что с шаблонами, написанными в стиле конструкторов, можно сопоставить атрибуты класса. При использовании этого подхода отдельные атрибуты также попадают в переменные (как и в показанные ранее кортежи), с которыми затем можно работать в соответствующем операторе case.

Выше мы можем увидеть другие особенности сопоставления шаблонов: во-первых выражение в case — это гард, который также является условием в if. Это полезно, когда сопоставления по значению не достаточно и вам нужны дополнительные проверки. Посмотрите на оставшееся выражение case: видно, что и ключевые слова, (name-name) и позиционные аргументы работают с синтаксисом, похожим на синтаксис конструкторов; то же самое верно для маски _ (или отбрасываемой переменной).

Сопоставление шаблонов также позволяет работать с вложенными шаблонами. Вложенные шаблоны могут использовать любой итерируемый тип: и конструируемый объект, и несколько таких объектов, которые возможно итерировать:

match users:
    case [Person(...)]:
        print("One user provided...")
    case [Person(...), Person(...) as second]:  # `as var` can be used to capture subpattern
        print(f"There's another user: {second}")
    case [Person(...), Person(...), *rest]:  # `*var` can be used as unpacking
        print(...)

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

Наконец, оператор * может использоваться для "распаковки" переменных в шаблоне, это работает и с маской _ в шаблоне *_. Если вы хотите увидеть больше примеров и законченный туториал, пройдите по ссылке на PEP 636.

Игра Тетрис на PyQt5

2021-04-20T19:59:51.180Z

@python_lounge

Игра Тетрис – одна из самых популярных компьютерных игр. Оригинальная игра была разработана и запрограммирована русским программистом Алексеем Пажитновым в 1985 году. С тех пор Тетрис доступен на почти каждой компьютерной платформе в множестве вариаций.

Создание простой компьютерной игры на PyQt5 – отличный способ повышения навыков программирования.

Тетрисом называется игра-головоломка с падающими блоками. В этой игре, мы имеем 7 разных фигур, называемых так: S-фигура, Z-фигура, T-фигура, L-фигура, фигура-линия, фигура "Г", и квадрат. Каждая из этих фигур формируется с помощью четырёх квадратиков. Фигуры падают вниз на доску. Цель игры Тетрис – перемещать и вращать фигуры так, чтобы их приземлилось как можно больше. Если мы сумеем сформировать ряд, ряд разрушается и мы получаем очки. Мы играем в Тетрис до тех пор, пока не достигнем верха.

Разработка

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

Некоторые идеи, применяющиеся в игре:

Мы используем QtCore.QBasicTimer(), чтобы создать игровой цикл.
Тетрамино рисуются.
Фигуры перемещаются по принципу "кубик за кубиком" (не "пиксель за пикселем").
Математически, доска – это просто список чисел.

Код содержит четыре класса: Tetris, Board, Tetrominoe и Shape. Класс Tetris организовывает игру. Board – это то, где пишется игровая логика. Класс Tetrominoe содержит имена всех частей тетриса и класс Shape содержит код для частей тетриса.

Код игры Тетрис:

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys, random
from PyQt5.QtWidgets import QMainWindow, QFrame, QDesktopWidget, QApplication
from PyQt5.QtCore import Qt, QBasicTimer, pyqtSignal
from PyQt5.QtGui import QPainter, QColor


class Tetris(QMainWindow):

    def __init__(self):
        super().__init__()

        self.initUI()


    def initUI(self):

        self.tboard = Board(self)
        self.setCentralWidget(self.tboard)

        self.statusbar = self.statusBar()
        self.tboard.msg2Statusbar[str].connect(self.statusbar.showMessage)

        self.tboard.start()

        self.resize(180, 380)
        self.center()
        self.setWindowTitle('Tetris')
        self.show()


    def center(self):

        screen = QDesktopWidget().screenGeometry()
        size = self.geometry()
        self.move((screen.width()-size.width())/2,
            (screen.height()-size.height())/2)


class Board(QFrame):

    msg2Statusbar = pyqtSignal(str)

    BoardWidth = 10
    BoardHeight = 22
    Speed = 300

    def __init__(self, parent):
        super().__init__(parent)

        self.initBoard()


    def initBoard(self):

        self.timer = QBasicTimer()
        self.isWaitingAfterLine = False

        self.curX = 0
        self.curY = 0
        self.numLinesRemoved = 0
        self.board = []

        self.setFocusPolicy(Qt.StrongFocus)
        self.isStarted = False
        self.isPaused = False
        self.clearBoard()


    def shapeAt(self, x, y):
        return self.board[(y * Board.BoardWidth) + x]


    def setShapeAt(self, x, y, shape):
        self.board[(y * Board.BoardWidth) + x] = shape


    def squareWidth(self):
        return self.contentsRect().width() // Board.BoardWidth


    def squareHeight(self):
        return self.contentsRect().height() // Board.BoardHeight


    def start(self):

        if self.isPaused:
            return

        self.isStarted = True
        self.isWaitingAfterLine = False
        self.numLinesRemoved = 0
        self.clearBoard()

        self.msg2Statusbar.emit(str(self.numLinesRemoved))

        self.newPiece()
        self.timer.start(Board.Speed, self)


    def pause(self):

        if not self.isStarted:
            return

        self.isPaused = not self.isPaused

        if self.isPaused:
            self.timer.stop()
            self.msg2Statusbar.emit("paused")

        else:
            self.timer.start(Board.Speed, self)
            self.msg2Statusbar.emit(str(self.numLinesRemoved))

        self.update()


    def paintEvent(self, event):

        painter = QPainter(self)
        rect = self.contentsRect()

        boardTop = rect.bottom() - Board.BoardHeight * self.squareHeight()

        for i in range(Board.BoardHeight):
            for j in range(Board.BoardWidth):
                shape = self.shapeAt(j, Board.BoardHeight - i - 1)

                if shape != Tetrominoe.NoShape:
                    self.drawSquare(painter,
                        rect.left() + j * self.squareWidth(),
                        boardTop + i * self.squareHeight(), shape)

        if self.curPiece.shape() != Tetrominoe.NoShape:

            for i in range(4):

                x = self.curX + self.curPiece.x(i)
                y = self.curY - self.curPiece.y(i)
                self.drawSquare(painter, rect.left() + x * self.squareWidth(),
                    boardTop + (Board.BoardHeight - y - 1) * self.squareHeight(),
                    self.curPiece.shape())


    def keyPressEvent(self, event):

        if not self.isStarted or self.curPiece.shape() == Tetrominoe.NoShape:
            super(Board, self).keyPressEvent(event)
            return

        key = event.key()

        if key == Qt.Key_P:
            self.pause()
            return

        if self.isPaused:
            return

        elif key == Qt.Key_Left:
            self.tryMove(self.curPiece, self.curX - 1, self.curY)

        elif key == Qt.Key_Right:
            self.tryMove(self.curPiece, self.curX + 1, self.curY)

        elif key == Qt.Key_Down:
            self.tryMove(self.curPiece.rotateRight(), self.curX, self.curY)

        elif key == Qt.Key_Up:
            self.tryMove(self.curPiece.rotateLeft(), self.curX, self.curY)

        elif key == Qt.Key_Space:
            self.dropDown()

        elif key == Qt.Key_D:
            self.oneLineDown()

        else:
            super(Board, self).keyPressEvent(event)


    def timerEvent(self, event):

        if event.timerId() == self.timer.timerId():

            if self.isWaitingAfterLine:
                self.isWaitingAfterLine = False
                self.newPiece()
            else:
                self.oneLineDown()

        else:
            super(Board, self).timerEvent(event)


    def clearBoard(self):

        for i in range(Board.BoardHeight * Board.BoardWidth):
            self.board.append(Tetrominoe.NoShape)


    def dropDown(self):

        newY = self.curY

        while newY > 0:

            if not self.tryMove(self.curPiece, self.curX, newY - 1):
                break

            newY -= 1

        self.pieceDropped()


    def oneLineDown(self):

        if not self.tryMove(self.curPiece, self.curX, self.curY - 1):
            self.pieceDropped()


    def pieceDropped(self):

        for i in range(4):

            x = self.curX + self.curPiece.x(i)
            y = self.curY - self.curPiece.y(i)
            self.setShapeAt(x, y, self.curPiece.shape())

        self.removeFullLines()

        if not self.isWaitingAfterLine:
            self.newPiece()


    def removeFullLines(self):

        numFullLines = 0
        rowsToRemove = []

        for i in range(Board.BoardHeight):

            n = 0
            for j in range(Board.BoardWidth):
                if not self.shapeAt(j, i) == Tetrominoe.NoShape:
                    n = n + 1

            if n == 10:
                rowsToRemove.append(i)

        rowsToRemove.reverse()


        for m in rowsToRemove:

            for k in range(m, Board.BoardHeight):
                for l in range(Board.BoardWidth):
                        self.setShapeAt(l, k, self.shapeAt(l, k + 1))

        numFullLines = numFullLines + len(rowsToRemove)

        if numFullLines > 0:

            self.numLinesRemoved = self.numLinesRemoved + numFullLines
            self.msg2Statusbar.emit(str(self.numLinesRemoved))

            self.isWaitingAfterLine = True
            self.curPiece.setShape(Tetrominoe.NoShape)
            self.update()


    def newPiece(self):

        self.curPiece = Shape()
        self.curPiece.setRandomShape()
        self.curX = Board.BoardWidth // 2 + 1
        self.curY = Board.BoardHeight - 1 + self.curPiece.minY()

        if not self.tryMove(self.curPiece, self.curX, self.curY):

            self.curPiece.setShape(Tetrominoe.NoShape)
            self.timer.stop()
            self.isStarted = False
            self.msg2Statusbar.emit("Game over")



    def tryMove(self, newPiece, newX, newY):

        for i in range(4):

            x = newX + newPiece.x(i)
            y = newY - newPiece.y(i)

            if x < 0 or x >= Board.BoardWidth or y < 0 or y >= Board.BoardHeight:
                return False

            if self.shapeAt(x, y) != Tetrominoe.NoShape:
                return False

        self.curPiece = newPiece
        self.curX = newX
        self.curY = newY
        self.update()

        return True


    def drawSquare(self, painter, x, y, shape):

        colorTable = [0x000000, 0xCC6666, 0x66CC66, 0x6666CC,
                      0xCCCC66, 0xCC66CC, 0x66CCCC, 0xDAAA00]

        color = QColor(colorTable[shape])
        painter.fillRect(x + 1, y + 1, self.squareWidth() - 2,
            self.squareHeight() - 2, color)

        painter.setPen(color.lighter())
        painter.drawLine(x, y + self.squareHeight() - 1, x, y)
        painter.drawLine(x, y, x + self.squareWidth() - 1, y)

        painter.setPen(color.darker())
        painter.drawLine(x + 1, y + self.squareHeight() - 1,
            x + self.squareWidth() - 1, y + self.squareHeight() - 1)
        painter.drawLine(x + self.squareWidth() - 1,
            y + self.squareHeight() - 1, x + self.squareWidth() - 1, y + 1)


class Tetrominoe(object):

    NoShape = 0
    ZShape = 1
    SShape = 2
    LineShape = 3
    TShape = 4
    SquareShape = 5
    LShape = 6
    MirroredLShape = 7


class Shape(object):

    coordsTable = (
        ((0, 0),     (0, 0),     (0, 0),     (0, 0)),
        ((0, -1),    (0, 0),     (-1, 0),    (-1, 1)),
        ((0, -1),    (0, 0),     (1, 0),     (1, 1)),
        ((0, -1),    (0, 0),     (0, 1),     (0, 2)),
        ((-1, 0),    (0, 0),     (1, 0),     (0, 1)),
        ((0, 0),     (1, 0),     (0, 1),     (1, 1)),
        ((-1, -1),   (0, -1),    (0, 0),     (0, 1)),
        ((1, -1),    (0, -1),    (0, 0),     (0, 1))
    )

    def __init__(self):

        self.coords = [[0,0] for i in range(4)]
        self.pieceShape = Tetrominoe.NoShape

        self.setShape(Tetrominoe.NoShape)


    def shape(self):
        return self.pieceShape


    def setShape(self, shape):

        table = Shape.coordsTable[shape]

        for i in range(4):
            for j in range(2):
                self.coords[i][j] = table[i][j]

        self.pieceShape = shape


    def setRandomShape(self):
        self.setShape(random.randint(1, 7))


    def x(self, index):
        return self.coords[index][0]


    def y(self, index):
        return self.coords[index][1]


    def setX(self, index, x):
        self.coords[index][0] = x


    def setY(self, index, y):
        self.coords[index][1] = y


    def minX(self):

        m = self.coords[0][0]
        for i in range(4):
            m = min(m, self.coords[i][0])

        return m


    def maxX(self):

        m = self.coords[0][0]
        for i in range(4):
            m = max(m, self.coords[i][0])

        return m


    def minY(self):

        m = self.coords[0][1]
        for i in range(4):
            m = min(m, self.coords[i][1])

        return m


    def maxY(self):

        m = self.coords[0][1]
        for i in range(4):
            m = max(m, self.coords[i][1])

        return m


    def rotateLeft(self):

        if self.pieceShape == Tetrominoe.SquareShape:
            return self

        result = Shape()
        result.pieceShape = self.pieceShape

        for i in range(4):

            result.setX(i, self.y(i))
            result.setY(i, -self.x(i))

        return result


    def rotateRight(self):

        if self.pieceShape == Tetrominoe.SquareShape:
            return self

        result = Shape()
        result.pieceShape = self.pieceShape

        for i in range(4):

            result.setX(i, -self.y(i))
            result.setY(i, self.x(i))

        return result


if __name__ == '__main__':

    app = QApplication([])
    tetris = Tetris()
    sys.exit(app.exec_())

Игра немного упрощена для более легкого понимания. Игра начинается сразу же после её запуска. Мы можем приостановить игру, нажав клавишу p. Клавиша Space будет немедленно бросать блок тетриса вниз. Игра идёт на постоянной скорости, ускорение не реализуется. Очки – это число линий, который мы удалили.

self.tboard = Board(self)
self.setCentralWidget(self.tboard)

Экземпляр класса Board создаётся и устанавливается центральным виджетом приложения.

self.statusbar = self.statusBar()
self.tboard.msg2Statusbar[str].connect(self.statusbar.showMessage)

Мы создаём строку состояния, где мы будем отображать сообщения. Мы будем отображать три возможных сообщения: количество уже удалённых линий, сообщение паузы, или сообщение «Игра окончена». msgStatusbar – это пользовательский сигнал, который реализуется в классе Board. showMessage() – это встроенный метод, который отображает сообщение в строке состояния.

self.tboard.start()

Эта строка инициирует игру.

class Board(QFrame):

    msg2Statusbar = pyqtSignal(str)
    ...

Создаётся пользовательский сигнал. msgStatusbar – это сигнал, который срабатывает, когда мы хотим написать сообщение или количество очков в строку состояния.

BoardWidth = 10
BoardHeight = 22
Speed = 300

Это переменные класса Board. BoardWidth и BoardHeight определяют размер доски в блоках. Speed определяет скорость игры. Каждые 300 мс будет начинаться цикл новой игры.

...
self.curX = 0
self.curY = 0
self.numLinesRemoved = 0
self.board = []
...

В методе initBoard() мы инициализируем несколько важных переменных. Переменная self.board – это список чисел от 0 до 7. Она представляет местоположение различных фигур и оставляет фигуры на доске.

def shapeAt(self, x, y):
    return self.board[(y * Board.BoardWidth) + x]

Метод shapeAt() определяет тип фигуры в данном блоке.

def squareWidth(self):
    return self.contentsRect().width() // Board.BoardWidth

Доска может динамически менять размер (например, при изменении размера окна). Как следствие, размер блока может меняться. squareWidth() вычисляет ширину простого квадратика в пикселях и возвращает её. Board.BoardWidth – это размер доски в блоках.

for i in range(Board.BoardHeight):
    for j in range(Board.BoardWidth):
        shape = self.shapeAt(j, Board.BoardHeight - i - 1)

        if shape != Tetrominoe.NoShape:
            self.drawSquare(painter,
                rect.left() + j * self.squareWidth(),
                boardTop + i * self.squareHeight(), shape)

Рисование игры разделяется на два шага. Первым шагом, мы рисуем все фигуры, или оставляем фигуры, которые были сброшены вниз доски. Все квадратики запоминаются в списке переменных self.board. Доступ к переменной получают, используя метод shapeAt().

if self.curPiece.shape() != Tetrominoe.NoShape:

    for i in range(4):

        x = self.curX + self.curPiece.x(i)
        y = self.curY - self.curPiece.y(i)
        self.drawSquare(painter, rect.left() + x * self.squareWidth(),
            boardTop + (Board.BoardHeight - y - 1) * self.squareHeight(),
            self.curPiece.shape())

Следующий шаг – это рисование упавших вниз частей.

elif key == Qt.Key_Right:
    self.tryMove(self.curPiece, self.curX + 1, self.curY)

В методе keyPressEvent(), мы проверяем нажатые клавиши. Если мы нажали клавишу правой стрелки, мы пробуем передвинуть часть вправо. Мы говорим "пробуем", поскольку часть может быть на правом крае.

elif key == Qt.Key_Up:
    self.tryMove(self.curPiece.rotateLeft(), self.curX, self.curY)

Клавиша стрелки вверх будет поворачивать падающую часть влево.

elif key == Qt.Key_Space:
    self.dropDown()

Клавиша «Пробел» будет немедленно бросать падающую часть.

elif key == Qt.Key_D:
    self.oneLineDown()

Нажимая клавишу «d», часть спустится вниз на один блок. Это может быть использовано, чтобы слегка ускорить падение части.

def tryMove(self, newPiece, newX, newY):

    for i in range(4):

        x = newX + newPiece.x(i)
        y = newY - newPiece.y(i)

        if x < 0 or x >= Board.BoardWidth or y < 0 or y >= Board.BoardHeight:
            return False

        if self.shapeAt(x, y) != Tetrominoe.NoShape:
            return False

    self.curPiece = newPiece
    self.curX = newX
    self.curY = newY
    self.update()
    return True

В методе tryMove(), мы пробуем переместить наши фигуры. Если фигура находится на краю доски или примыкает к некоторой другой части, мы возвращаем значение "Ложь". В противном случае, мы перемещаем текущую падающую часть в новую позицию.

def timerEvent(self, event):

    if event.timerId() == self.timer.timerId():

        if self.isWaitingAfterLine:
            self.isWaitingAfterLine = False
            self.newPiece()
        else:
            self.oneLineDown()

    else:
        super(Board, self).timerEvent(event)

В timerEvent (событии таймера), мы либо создаём новую фигуру после предыдущей, которая упала, либо мы передвигаем падающую часть на одну линию вниз.

def clearBoard(self):

    for i in range(Board.BoardHeight * Board.BoardWidth):
        self.board.append(Tetrominoe.NoShape)

Метод clearBoard() очищает доску путём установки Tetrominoe.Noshape на каждый блок доски.

def removeFullLines(self):

    numFullLines = 0
    rowsToRemove = []

    for i in range(Board.BoardHeight):

        n = 0
        for j in range(Board.BoardWidth):
            if not self.shapeAt(j, i) == Tetrominoe.NoShape:
                n = n + 1

        if n == 10:
            rowsToRemove.append(i)

    rowsToRemove.reverse()


    for m in rowsToRemove:

        for k in range(m, Board.BoardHeight):
            for l in range(Board.BoardWidth):
                    self.setShapeAt(l, k, self.shapeAt(l, k + 1))

    numFullLines = numFullLines + len(rowsToRemove)
    ...

Когда фигура падает, мы вызываем метод removeFullLines(). Мы обнаруживаем все полные линии и удаляем их. Обратите внимание, что мы развернули порядок удаляемых линий. В противном случае, это не будет работать правильно. В нашем случае, мы используем "никакую" гравитацию. Это означает, что части могут парить над пустыми промежутками.

def newPiece(self):

    self.curPiece = Shape()
    self.curPiece.setRandomShape()
    self.curX = Board.BoardWidth // 2 + 1
    self.curY = Board.BoardHeight - 1 + self.curPiece.minY()

    if not self.tryMove(self.curPiece, self.curX, self.curY):

        self.curPiece.setShape(Tetrominoe.NoShape)
        self.timer.stop()
        self.isStarted = False
        self.msg2Statusbar.emit("Game over")

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

class Tetrominoe(object):
    NoShape = 0
    ZShape = 1
    SShape = 2
    LineShape = 3
    TShape = 4
    SquareShape = 5
    LShape = 6
    MirroredLShape = 7

Класс Tetrominoe содержит в себе имена всех возможных фигур. Мы также имеем NoShape для пустого пространства.

class Shape(object):

    coordsTable = (
        ((0, 0),     (0, 0),     (0, 0),     (0, 0)),
        ((0, -1),    (0, 0),     (-1, 0),    (-1, 1)),
        ...
    )
    ...

Класс Shape хранит информацию о частях тетриса.

Набор coordsTable содержит в себе всевозможные значения координат наших частей тетриса. Это шаблон, из которого все части берут свои значения координат.

self.coords = [[0,0] for i in range(4)]

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

Изображение выше поможет понять значения координат. Для примера, набор (0, -1), (0, 0), (-1, 0), (-1, -1) представляет S-фигуру. Схема иллюстрирует фигуру.

def rotateLeft(self):

    if self.pieceShape == Tetrominoe.SquareShape:
        return self

    result = Shape()
    result.pieceShape = self.pieceShape

    for i in range(4):

        result.setX(i, self.y(i))
        result.setY(i, -self.x(i))

    return result

Метод rotateLeft() поворачивает часть влево. Квадрат не должен поворачиваться. Вот почему мы просто возвращаем ссылку на текущий объект. Новая часть создаётся и её координаты устанавливаются в одну из повернутых частей.

Учебный проект на Python: алгоритм Дейкстры, OpenCV и UI

2021-04-12T18:24:33.518Z

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

Вспоминаем алгоритм Дейкстры

Алгоритм Дейкстры — один из наиболее популярных алгоритмов теории графов. Он используется для поиска кратчайшего пути между узлами на ориентированном графе. Мы начнем с исходного узла и известных длин ребер между узлами.

Сначала мы присваиваем значение расстояния от источника всем узлам. Узел s получает значение 0, потому что это источник; остальные получают значения ∞ для начала.

Наш интересующий узел — это необработанный узел с наименьшим значением (показан серым), то есть s. Сначала мы «ослабляем» каждую смежную вершину до нашего интересующего узла, обновляя их значения до минимума их текущего значения или значения узла интереса плюс длину соединительного ребра…

Узел s теперь завершен (черный), а его соседи a и b приняли новые значения. Новый интересующий узел — b, поэтому мы повторяем процесс «ослабления» соседних узлов b и финализации значения кратчайшего пути для b.

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

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

Концептуализация изображений лабиринта

Мы можем представить себе изображение как матрицу пикселей. Каждый пиксель (для простоты) имеет значение RGB 0,0,0 (черный) или 255,255,255 (белый). Наша цель — создать кратчайший путь, который начинается на белом и не переходит на чёрные границы. Чтобы представить эту цель, мы можем рассматривать каждый пиксель как узел и рисовать ребра между соседними пикселями с длиной ребер, основанной на разнице значений RGB. Мы будем использовать формулу евклидова квадратного расстояния и добавим 0,1, чтобы гарантировать отсутствие длины пути 0 — (требование для алгоритма Дейкстры):

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

Реализация

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

import cv2
import matplotlib.pyplot as plt
import numpy as np
img = cv2.imread('maze.png') # read an image from a file using
cv2.circle(img,(5,220), 3, (255,0,0), -1) # add a circle at (5, 220)
cv2.circle(img, (25,5), 3, (0,0,255), -1) # add a circle at (5,5)
plt.figure(figsize=(7,7))
plt.imshow(img) # show the image
plt.show()

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

class Vertex:
    def __init__(self,x_coord,y_coord):
        self.x=x_coord
        self.y=y_coord
        self.d=float('inf') #current distance from source node
        self.parent_x=None
        self.parent_y=None
        self.processed=False
        self.index_in_queue=None

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

def find_shortest_path(img,src,dst):
    pq=[] #min-heap priority queue
    imagerows,imagecols=img.shape[0],img.shape[1]
    matrix = np.full((imagerows, imagecols), None) 
    #access matrix elements by matrix[row][col]
    #fill matrix with vertices
    for r in range(imagerows):
        for c in range(imagecols):
            matrix[r][c]=Vertex(c,r)
            matrix[r][c].index_in_queue=len(pq)
            pq.append(matrix[r][c])
    #set source distance value to 0
    matrix[source_y][source_x].d=0
    #maintain min-heap invariant (minimum d Vertex at list index 0)
    pq = bubble_up(pq, matrix[source_y][source_x].index_in_queue)

Нам нужно несколько вспомогательных функций, чтобы помочь найти ребра и длину ребер между вершинами:

#Implement euclidean squared distance formula
def get_distance(img,u,v):
    return 0.1 + (float(img[v][0])-float(img[u][0]))**2+(float(img[v][1])-float(img[u][1]))**2+(float(img[v][2])-float(img[u][2]))**2
#Return neighbor directly above, below, right, and left
def get_neighbors(mat,r,c):
    shape=mat.shape
    neighbors=[]
    #ensure neighbors are within image boundaries
    if r > 0 and not mat[r-1][c].processed:
         neighbors.append(mat[r-1][c])
    if r < shape[0] - 1 and not mat[r+1][c].processed:
            neighbors.append(mat[r+1][c])
    if c > 0 and not mat[r][c-1].processed:
        neighbors.append(mat[r][c-1])
    if c < shape[1] - 1 and not mat[r][c+1].processed:
            neighbors.append(mat[r][c+1])
    return neighbors

Теперь мы можем реализовать алгоритм Дейкстры и присвоить значения расстояния (d) всем вершинам пикселей в изображении лабиринта:

while len(pq) > 0:
    u=pq[0] #smallest-value unprocessed node
    #remove node of interest from the queue
    pq[0]=pq[-1] 
    pq[0].index_in_queue=0
    pq.pop()
    pq=bubble_down(pq,0) #min-heap function, see source code 
    
    u.processed=True
    neighbors = get_neighbors(matrix,u.y,u.x)
    for v in neighbors:
        dist=get_distance(img,(u.y,u.x),(v.y,v.x))
        if u.d + dist < v.d:
            v.d = u.d+dist
            v.parent_x=u.x #keep track of the shortest path
            v.parent_y=u.y
            idx=v.index_in_queue
            pq=bubble_down(pq,idx) 
            pq=bubble_up(pq,idx)

Теперь мы можем вызвать функцию кратчайшего пути и нарисовать решение в нашем лабиринте:

img = cv2.imread('maze.png') # read an image from a file using opencv (cv2) library
p = find_shortest_path(img, (25,5), (5,220))
drawPath(img,p)
plt.figure(figsize=(7,7))
plt.imshow(img) # show the image on the screen 
plt.show()

Давайте попробуем другие лабиринты со всего Интернета.

Полный исходный код доступен на GitHub здесь.

Алгоритм Дейкстры для поиска кратчайшего пути в Python

2021-04-11T15:34:54.194Z

@python_lounge

Создание графа для алгоритмы Дейкстры

Важно понимать, граф представляет собой множество узлов (nodes), соединенных ребрами (edges).

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

Как узлы, так и ребра могут быть носителями информации. К примеру, граф выше представляет собой систему зданий, которые соединены между собой туннелями. В узлах может находиться информация о названии здания (например, строка «Библиотека»), в то время, как ребро может содержать информацию о длине туннеля.

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

Реализация графов в Python

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

Ниже представлена матрица смежности для предыдущего графа. Каждый ряд представляет один узел графа, как и каждый столбец. В данном случае ряд 0 и столбец 0 представляют узел «А»; ряд 1 и столбец 1 — узел «B», ряд 2 и столбец 2 — узел «C» и так далее, принцип понятен. Каждый локальный элемент {ряд, столбец} представляет ребро. Таким образом, каждый ряд показывает связь между одним узлом и всеми прочими узлами. Элемент «0» указывает на отсутствие ребра, в то время как «1» указывает на присутствие ребра, связывающего row_node и column_node в направлении row_node → column_node. Поскольку граф в примере является неориентированным, данная матрица равна его транспонированию (то есть матрица симметричная), поскольку каждая связь двунаправленная. Вы могли заметить, что главная диагональ матрицы представлена только нулями, а все оттого, что ни один узел не связан сам с собой. Таким образом, пространственная сложность данного представления нерасчетлива.

Теперь разберемся с кодом. Обратите внимание, что здесь задействовано немного экстра-данных — так как нам было нужно, чтобы реальные объекты узлов содержали определенную информацию, в классе Graph был реализован массив объектов узлов, индексы которых соответствуют номеру их ряда (столбца) в матрице смежности. В Graph также был добавлен вспомогательный метод, который позволяет использовать либо номера индекса узла, либо объект узда в качестве аргументов для методов класса Graph. Данные классы нельзя считать примерами элегантности, однако они хорошо выполняют свою работу, излишне не усложняя процесс:class Node: 
    def __init__(self, data, indexloc = None):
        self.data = data
        self.index = indexloc
        
      
class Graph:
 
    @classmethod
    def create_from_nodes(self, nodes):
        return Graph(len(nodes), len(nodes), nodes)
 
  
    def __init__(self, row, col, nodes = None):
        # установка матрица смежности
        self.adj_mat = [[0] * col for _ in range(row)]
        self.nodes = nodes
        for i in range(len(self.nodes)):
            self.nodes[i].index = i
 
    # Связывает node1 с node2
    # Обратите внимание, что ряд - источник, а столбец - назначение 
    # Обновлен для поддержки взвешенных ребер (поддержка алгоритма Дейкстры)
    def connect_dir(self, node1, node2, weight = 1):
        node1, node2 = self.get_index_from_node(node1), self.get_index_from_node(node2)
        self.adj_mat[node1][node2] = weight
  
    # Опциональный весовой аргумент для поддержки алгоритма Дейкстры
    def connect(self, node1, node2, weight = 1):
        self.connect_dir(node1, node2, weight)
        self.connect_dir(node2, node1, weight)
 
    # Получает ряд узла, отметить ненулевые объекты с их узлами в массиве self.nodes
    # Выбирает любые ненулевые элементы, оставляя массив узлов
    # которые являются connections_to (для ориентированного графа)
    # Возвращает значение: массив кортежей (узел, вес)
    def connections_from(self, node):
        node = self.get_index_from_node(node)
        return [(self.nodes[col_num], self.adj_mat[node][col_num]) for col_num in range(len(self.adj_mat[node])) if self.adj_mat[node][col_num] != 0]
 
    # Проводит матрицу к столбцу узлов
    # Проводит любые ненулевые элементы узлу данного индекса ряда
    # Выбирает только ненулевые элементы
    # Обратите внимание, что для неориентированного графа
    # используется connections_to ИЛИ connections_from
    # Возвращает значение: массив кортежей (узел, вес)
    def connections_to(self, node):
      node = self.get_index_from_node(node)
      column = [row[node] for row in self.adj_mat]
      return [(self.nodes[row_num], column[row_num]) for row_num in range(len(column)) if column[row_num] != 0]
    
  
    def print_adj_mat(self):
      for row in self.adj_mat:
          print(row)
  
    def node(self, index):
      return self.nodes[index]
    
  
    def remove_conn(self, node1, node2):
      self.remove_conn_dir(node1, node2)
      self.remove_conn_dir(node2, node1)
  
    # Убирает связь в направленной манере (nod1 к node2)
    # Может принять номер индекса ИЛИ объект узла
    def remove_conn_dir(self, node1, node2):
      node1, node2 = self.get_index_from_node(node1), self.get_index_from_node(node2)
      self.adj_mat[node1][node2] = 0  
  
    # Может пройти от node1 к node2
    def can_traverse_dir(self, node1, node2):
      node1, node2 = self.get_index_from_node(node1), self.get_index_from_node(node2)
      return self.adj_mat[node1][node2] != 0  
  
    def has_conn(self, node1, node2):
      return self.can_traverse_dir(node1, node2) or self.can_traverse_dir(node2, node1)
  
    def add_node(self,node):
      self.nodes.append(node)
      node.index = len(self.nodes) - 1
      for row in self.adj_mat:
        row.append(0)    
      self.adj_mat.append([0] * (len(self.adj_mat) + 1))
 
    # Получает вес, представленный перемещением от n1
    # к n2. Принимает номера индексов ИЛИ объекты узлов
    def get_weight(self, n1, n2):
        node1, node2 = self.get_index_from_node(n1), self.get_index_from_node(n2)
        return self.adj_mat[node1][node2]
  
    # Разрешает проводить узлы ИЛИ индексы узлов  
    def get_index_from_node(self, node):
        if not isinstance(node, Node) and not isinstance(node, int):
            raise ValueError("node must be an integer or a Node object")
        if isinstance(node, int):
            return node
        else:
            return node.index

Здесь классы Node и Graph будут использованы для описания данного примера графа. Поместим вышеуказанный граф в код и посмотрим, получится ли в итоге верная матрица смежности:

a = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")
e = Node("E")
f = Node("F")
 
graph = Graph.create_from_nodes([a,b,c,d,e,f])
 
graph.connect(a, b)
graph.connect(a, c)
graph.connect(a, e)
graph.connect(b, c)
graph.connect(b, d)
graph.connect(c, d)
graph.connect(c, f)
graph.connect(d, e)
 
graph.print_adj_mat()

Матрицы смежности, полученная в выводе (из graph.print_adj_mat()) после запуска кода, такая же, как и та, что была рассчитана ранее:

[0, 1, 1, 0, 1, 0]
[1, 0, 1, 1, 0, 0]
[1, 1, 0, 1, 0, 1]
[0, 1, 1, 0, 1, 0]
[1, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 0]

При желании добавить расстояние ребрам графа нужно просто заменить единицы в данной матрице смежности на значения нужного расстояния. На данный момент класс Graph поддерживает данную функциональность, доказательством чему является код ниже. Для ясности демонстрации были добавлены произвольные значения длины:

w_graph = Graph.create_from_nodes([a,b,c,d,e,f])
 
w_graph.connect(a, b, 5)
w_graph.connect(a, c, 10)
w_graph.connect(a, e, 2)
w_graph.connect(b, c, 2)
w_graph.connect(b, d, 4)
w_graph.connect(c, d, 7)
w_graph.connect(c, f, 10)
w_graph.connect(d, e, 3)
 
w_graph.print_adj_mat()

В результате выводится следующая матрица смежности:

[0 , 5 , 10, 0, 2, 0]
[5 , 0 , 2 , 4 , 0 , 0]
[10, 2, 0, 7, 0, 10]
[0 , 4 , 7 , 0 , 3 , 0]
[2 , 0 , 0 , 3 , 0 , 0]
[0, 0 , 10, 0 , 0 , 0]

Визуально данный граф будет представлен следующим образом:

Для того чтобы ребра содержали больше информации, нужно чтобы матрица содержала объекты ребер вместо простых целых чисел.

Алгоритм Дейкстры

Перед непосредственным составлением кода, осветим ключевые моменты темы:

Главное условие: отрицательных длин ребер не бывает.
Алгоритм Дейкстры изначально создавался для поиска кратчайшего пути между двумя конкретными узлами. Однако сегодня он также широко используется для поиска кратчайших путей между узлом источника и всеми остальными узлами. В статье будет рассмотрен второй вариант. Для осуществления первого случая понадобится просто остановить алгоритм сразу после того, как узел назначения будет добавлен в набор seen. По ходу дела все станет намного понятнее.

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

Итак, что мы понимаем под жадным алгоритмом? По сути, это значит, что принятые решения будут обусловлены самым оптимальным выбором на данный конкретный момент времени. Метод подойдет далеко не для каждого случая. К примеру, при реализации шахматного бота фокус точно не пройдет — зачем брать враждебного ферзя, если через ход это обернется шахом со стороны противника. Для таких ситуаций больше подойдет minimax. В рассматриваемом сейчас случае жадный алгоритм действительно является наилучшим вариантом, который значительно сокращает число проверок, что нужно совершить без потери точности. Как?

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

Теперь задумаемся, где мы сейчас находимся в плане логики, так как это важно для реализации. Узел, что сейчас оценивается (ближайший к источнику) больше НИКОГДА не будет оцениваться вновь в плане кратчайшего пути от исходного узла. Его предварительное расстояние теперь стало точным расстоянием. Хотя вполне возможно, что пути от исходного узла к данному узлу могут проходить через иные маршруты, можно с уверенностью сказать, что они будут затратнее, нежели текущий путь. Он был выбран ввиду того, что был кратчайшим по сравнению с любым другим узлом, связанным с источником. Следовательно, любой другой путь будет длиннее, чем текущее расстояние от исходного узла до рассматриваемого узла.

При использовании графика из примера в случае установки исходного узла как А, мы бы назначили предварительные расстояния для узлов B, C и E. Поскольку у E было кратчайшее расстояние от A, после этого был посещен узел E. И теперь, хотя наверняка есть несколько других способов добраться из А до Е, они будут затратнее, нежели текущее расстояние А → Е. Другие маршруты должны проходить через B или С, а в результате проверки стало ясно, что они дальше от A, чем E. Жадный выбор был сделан, а это ограничивает общее количество проверок, которые нам нужно сделать, и при этом точность не теряется. Неплохо.

Продолжим логическую цепочку с использованием графа из примера. Просто повторим для E действия, сделанные для A. Обновляются все ближайшие соседние элементы к E с предварительным расстоянием, равным length(A у E) + edge_length(E к соседнему элементу). Это верно в том случае, ЕСЛИ данное расстояние меньше, чем текущее предварительное расстояние, или же предварительное расстояние еще не было установлено.

Обратите внимание: Для достижения данной функциональности здесь просто инициализируются все предварительные расстояния до бесконечности.

Далее делается жадный выбор касательно того, какой узел должен оцениваться следующим. Выбирается один узел из графа с наименьшим предварительным расстоянием, и добавляется E к набору seen nodes. Теперь он повторно оцениваться не будет. У данного нового узла та же гарантия, что что и E — его предварительное расстояние от A является определенным минимальным расстоянием от A. Чтобы понять это, давайте оценим возможности (хотя они могут не соответствовать графу примера, для ясности используем те же названия). Если следующий узел является соседом E, но не A, то он будет выбран, потому что его временное расстояние все еще короче, чем любого другого прямого соседа A. По этой причине нет другого возможного кратчайшего пути, только через E. Если следующий выбранный узел будет непосредственным соседом A, то есть вероятность, что этот узел обеспечит более короткий путь к некоторым из соседей E, чем сам E.

Обзор кода алгоритма Дейкстры на Python

Давайте более четко и формально рассмотрим процесс реализации алгоритма Дейкстры.

ИНИЦИАЛИЗАЦИЯ

Установите provisional_distance для всех узлов от исходного узла до бесконечности.
Определите пустой набор seen_nodes. Данный набор гарантирует, что узел, у которого уже есть кратчайший путь, не будет повторно рассмотрен, а также то, что не будут рассматриваться пути через узел, у которого более короткий путь к источнику, чем текущий путь. Помните, что узлы входят в seen_nodes только после доказательства того, что в наличии есть абсолютное кратчайшее расстояние (а не только предварительное расстояние). Набор используется для получения времени поиска O(1) вместо многократного выполнения поиска через массив O(n).
Установите provisional_distance для исходного узла со значением 0, и массив, представляющий перескоки для простого включения самого исходного кода. Это будет полезно позже, когда мы проследим выбранный для графа путь для расчета минимального расстояния.

ПРОЦЕДУРА ИТЕРАЦИИ

Пока (while) все узлы увидеть (seen) не удалось. Или, в случае поиска одного узла назначения, пока не удалось увидеть (seen) данный узел назначения.
Установите current_node для узла c самым малым предварительным расстоянием provisional_distance во всем графе. Обратите внимание, что для первой итерации это будет исходный узел source_node, так как предварительное расстояние provisional_distance установлено на 0.
Добавьте текущий узел current_node к набору просмотренных узлов seen_nodes.
Обновите provisional_distance каждого соседнего элемента current_node до (абсолютного) расстояния от current_node до source_node вдобавок к длине ребра от current_node к данному соседнему элементу, ЕСЛИ данное значение меньше, чем текущее значение соседнего provisional_distance. Если у соседнего элемента еще не было набора предварительного расстояния, помните, что он инициализирован до бесконечности, и по этой причине должен быть больше, чем данная сумма. При обновлении provisional_distance также обновляются «перескоки», которые были сделаны для получения расстояния, задействуя конкатенацию перескоков current_node к исходному узлу с самим current_node.
Завершение цикла while.

Алгоритм Дейкстры через схемы и изображения

Обратите внимание, что в дальнейшем можно посетить либо D, либо B. Сейчас мы посетим B.

Здесь программа завершается. В результате мы получаем кратчайшие пути для каждого узла графа.

Python код для алгоритма Дейкстры

Посмотрим, как будет выглядеть реализация алгоритма Дейстры в Python. Это экземпляр метода внутри раннее используемого класса Graph, который задействует преимущества других методов и структуры:

 def dijkstra(self, node):        # Получает индекс узла (или поддерживает передачу int)
        nodenum = self.get_index_from_node(node)
        # Заставляет массив отслеживать расстояние от одного до любого узла
        # в self.nodes. Инициализирует до бесконечности для всех узлов, кроме 
        # начального узла, сохраняет "путь", связанный с расстоянием. 
        # Индекс 0 = расстояние, индекс 1 = перескоки узла
        dist = [None] * len(self.nodes)
        for i in range(len(dist)):
            dist[i] = [float("inf")]
            dist[i].append([self.nodes[nodenum]])
        
        dist[nodenum][0] = 0
        # Добавляет в очередь все узлы графа
        # Отмечает целые числа в очереди, соответствующие индексам узла
        # локаций в массиве self.nodes 
        queue = [i for i in range(len(self.nodes))]
        # Набор увиденных на данный момент номеров 
        seen = set()
        while len(queue) > 0:
            # Получает узел в очереди, который еще не был рассмотрен
            # и который находится на кратчайшем расстоянии от источника
            min_dist = float("inf")
            min_node = None
            for n in queue: 
                if dist[n][0] < min_dist and n not in seen:
                    min_dist = dist[n][0]
                    min_node = n
            
            # Добавляет мин. расстояние узла до увиденного, убирает очередь
            queue.remove(min_node)
            seen.add(min_node)
            # Получает все следующие перескоки
            connections = self.connections_from(min_node)
            # Для каждой связи обновляет путь и полное расстояние от  
            # исходного узла, если полное расстояние меньше
            # чем текущее расстояние в массиве dist
            for (node, weight) in connections: 
                tot_dist = weight + min_dist
                if tot_dist < dist[node.index][0]:
                    dist[node.index][0] = tot_dist
                    dist[node.index][1] = list(dist[min_node][1])
                    dist[node.index][1].append(node)
        return dist

При использовании данного метода можно протестировать нашу картинку:

a = Node("A")

b = Node("B")

c = Node("C")
d = Node("D")
e = Node("E")
f = Node("F")
 
w_graph = Graph.create_from_nodes([a,b,c,d,e,f])
 
w_graph.connect(a,b,5)
w_graph.connect(a,c,10)
w_graph.connect(a,e,2)
w_graph.connect(b,c,2)
w_graph.connect(b,d,4)
w_graph.connect(c,d,7)
w_graph.connect(c,f,10)
w_graph.connect(d,e,3)
 
print([(weight, [n.data for n in node]) for (weight, node) in w_graph.dijkstra(a)])

Для получения читабельного для людей вывода нужно отметить объекты узла в их data. Результат станет следующим:

[(0, [‘A’]), (5, [‘A’, ‘B’]), (7, [‘A’, ‘B’, ‘C’]), (5, [‘A’, ‘E’, ‘D’]), (2, [‘A’, ‘E’]), (17, [‘A’, ‘B’, ‘C’, ‘F’])]

Здесь каждый кортеж — (total_distance, [hop_path]). Это совпадает с рассматриваемой картинкой.

Быстрый способ реализации алгоритма Дейкстры в Python

На данный момент тем, кто заинтересован только в функциональности, хватит предоставленного материала. Однако, тем, кому важна скорость стоит продолжить чтение.

Остановимся на одном довольно важном моменте. В каждой итерации нам нужно найти узел с кратчайшим предварительным расстоянием, что требуется для следующего жадного решения. Сейчас осматривается list, вызывая queue (используя данные значения в dist) с целью получения желаемого. У данного queue может быть максимальная длина n, что является числом узлов. Итерация по этому списку является операцией O(n), которую мы выполняем в каждой итерации цикла while. Так как цикл while продолжается до тех пор, пока не будет просмотрен (seen) каждый узел, сейчас операция O(n) совершается n раз. Наш алгоритм — O(n2). Это не очень хорошо, но и это не все.

Если взглянуть на реализацию матрицы смежности в Graph, можно заметить, что для нахождения связи нам пришлось осмотреть весь ряд (размера n). Это еще одна операция O(n) в цикле while. Как это исправить? Во-первых, можно использовать кучу для получения минимального предварительного расстояния в O(lg(n)) времени вместо O(n) времени (при бинарной куче — отметьте, что куча Фибоначчи способна на это в O(1)). Во-вторых, можно реализовать граф при помощи списка смежности, где у каждого узла есть список связанных узлов. Получается, что осматривать все узлы на наличие существующей связи не потребуется. Это показывает, почему важно понимать то, как мы представляем структуры данных. В случае реализаци кучи при помощи представления матрицы смежности асимптомическое время выполнения запуска алгоритма изменено не будет. (На заметку: Если вам не знакома нотация big-O, можете просмотреть данную статью).

Кучи в Python

Такая структура данных, как куча, обычно используется для реализации очереди с приоритетом. По сути, они эффективны во время ситуаций, когда нужно быстро получить элемент с наивысшим приоритетом. В нашем случае элемент с высоким приоритетом — это наименьшее предварительное расстояние (provisional distance) от оставшихся нерассмотренных узлов. Вместо того, чтобы каждый раз осматривать весь массив в поисках наименьшего предварительного расстояния (provisional distance), можно использовать находящуюся там кучу, что готова передать узел с наименьшим предварительным расстоянием (provisional distance). Как только расстояние будет извлечено из кучи, она быстро перестоится, будучи готовой к передаче нового значения в тот момент, когда оно будет нужно. Довольно неплохо! Для практики можете попробовать реализовать очень быструю Фибоначчиеву кучу. А далее мы попробуем реализовать Binary MinHeap, что поможет разрешить наши задачи.

По сути бинарная куча является полным бинарным деревом, что обладает свойством кучи. Что это значит?

Полное бинарное дерево — это структура в виде дерева данных, где у КАЖДОГО родителя узла есть ровно два дочерних узла. Если дочерних узлов недостаточно, чтобы в последнем ряду родительских узлов было по 2 дочерних узла, дочерние узлы будут заполняться слева направо.

Как это будет выглядеть?

Свойство кучи (для минимальной кучи) Каждый родитель ДОЛЖЕН быть меньше или равен обоим дочерним элементам.

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

Здесь представлен базовый массив [2, 5, 4, 7, 9, 13, 18]. Как видите, сортировка сделана наполовину, но в данном случае нам и не нужна полная сортировка. Через минуту данный базовый массив станет намного понятнее.

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

Так как бинарная куча является специальной реализацией бинарного дерева, начнем с создания класса BinaryTree, у которого будет наследовать рассматриваемая куча. Для реализации бинарного дерева нужно создать базовую структуру данных в виде массива, после чего структура дерева будет рассчитана через индексы узлов внутри массива. К примеру, у начального бинарного дерева (первое изображение полного бинарного дерева) базовый массив будет [5, 7, 18, 2, 9, 13, 4]. Мы обозначим связи между узлами при определении индекса узла в базовом массиве. Известно, что у каждого родителя ровно два дочерних элемента. Нулевой индекс является корнем в основе, индекс 1 — левый ребенок, а индекс 2 — правый ребенок. Если обобщить, левый ребенок индекса i будет обладать индексом 2*i + 1, а правый — 2*i + 2. У узла индекса i родительский индекс — floor((i-1) / 2).

Итак, класс BinaryTree будет выглядеть следующим образом:

class BinaryTree:
 
    def __init__(self, nodes = []):
        self.nodes = nodes
 
    def root(self):
        return self.nodes[0]
    
    def iparent(self, i):
        return (i - 1) // 2
    
    def ileft(self, i):
        return 2*i + 1
 
    def iright(self, i):
        return 2*i + 2
 
    def left(self, i):
        return self.node_at_index(self.ileft(i))
    
    def right(self, i):
        return self.node_at_index(self.iright(i))
 
    def parent(self, i):
        return self.node_at_index(self.iparent(i))
 
    def node_at_index(self, i):
        return self.nodes[i]
 
    def size(self):
        return len(self.nodes)

Теперь MinHeap может наследовать BinaryTree и задействовать требуемую функциональность. Теперь BinaryTree можно будет вновь использовать в иных контекстах.

Окей, мы практически у финала. Сейчас нужно будет идентифицировать способности класса, который должны быть у класса MinHeap, а затем реализовать их. Необходимо, чтобы куча могла:

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

Для осуществления данных условий начнем с создания блока, который сыграет важную роль при реализации первых двух функций. Напишем метод под названием min_heapify_subtree. Данный метод будет рассматривать всю кучу как heapified (то есть при этом поддерживая свойство кучи), кроме единственного узла 3-го поддерева. Мы будем рекурсивно накапливать это поддерево, идентифицируя его индекс родительского узла в точке i и давая возможность правильно размещенному узлу найти верную позицию в куче. Для этого проверяем, меньше ли дочерние узлы, чем родительский. Если да, заменяем наименьший дочерний узел с родительским. Затем рекурсивно вызываем метод по индексу замененного родителя (который теперь является дочерним), чтобы убедиться, что он помещен в позицию для поддержки свойства кучи. Вот псевдокод:

FUNCTION min_heapify_subtree(i)
  index_of_min = i
  IF left_child exists AND left_child < node[index_of_min]
    index_of_min = left_child_index
  ENDIF
  IF right_child exists AND right_child < node[index_of_min]
    index_of_min = right_child_index
  ENDIF 
  IF index_of_min != i
    swap(nodes[i], nodes[index_of_min])
    min_heapify_subtree(index_of_min)
  ENDIF
END

В худшем случае метод начинается с индекса 0 и рекурсивно распространит корневой узел вплоть до нижнего листа. Поскольку здесь куча является бинарным деревом, у нас есть уровни lg(n), где n — общее количество узлов. Поскольку каждая рекурсия метода выполняет фиксированное количество операций, то есть O(1), классификация времени выполнения min_heapify_subtree — O(lg (n)).

Для превращения совершенно случайного массива в правильную кучу, просто нужно вызвать min_heapify_subtree на каждом узле, начиная с нижних листьев. Задействуем метод min_heapify:

FUNCTION min_heapify
  FOR index from last_index to first_index
    min_heapify_subtree(index)
  ENDFOR
END

Данный метод выполняет метод O(lg(n)) n раз, поэтому его время выполнения будет O(n*lg(n)).

Нам нужно извлечь минимальное значение из кучи. Значение можно принять время за O(1), потому что оно всегда будет корневым узлом минимальной кучи (т.е. индекс 0 базового массива), но просто прочитать недостаточно. Требуется удаление, А ТАКЖЕ подтверждение того, что куча остается нагроможденной. Для этого удаляем корневой узел и заменяем его последним листом, а затем min_heapify_subtree индексом 0, чтобы обеспечить сохранение свойства кучи:

FUNCTION pop
  min_node = nodes[0]
  IF heap_size > 1 
    nodes[0] = nodes[nodes.length - 1]
    nodes.pop() // remove the last element from our nodes array
    min_heapify_subtree(0)
  ELSE IF heap_size == 1
    nodes.pop()
  ELSE
    return NIL // the heap is empty, so return NIL value
  ENDIF
  return min_node
END

Метод выполняется за постоянное время, за исключением min_heapify_subtree. Можно сказать, что этот метод также O(lg (n)).

Отлично! На последнем этапе нужно будет добиться получения возможности обновления значний кучи (уменьшать их, поскольку обновляются предварительные расстояния (provisional distance) до более низких значений), сохраняя свойство кучи.

Итак, создадим метод под названием decrease_key, который принимает значение индекса обновляемого узла и новое значение. Мы хотим обновить значение этого узла, а затем добавить его туда, где он должен будет находиться, если станет меньше родителя. Таким образом, пока он не станет меньше родительского узла, поменяем его на родительский узел:

FUNCTION decrease_key(index, value)
  nodes[index] = value
  parent_node_index = parent_index(index)
  WHILE index != 0 AND nodes[parent_node_index] > nodes[index]
    swap(nodes[i], nodes[parent_node_index])
    index = parent_node_index
    parent_node_index = parent_index(index)
  ENDWHILE
END

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

class MinHeap(BinaryTree):
 
    def __init__(self, nodes):
        BinaryTree.__init__(self, nodes)
        self.min_heapify()
 
    # Преобразует в кучу узлы, рассматривая, что все поддеревья уже кучи
    def min_heapify_subtree(self, i):
        size = self.size()
        ileft = self.ileft(i)
        iright = self.iright(i)
        imin = i
        if( ileft < size and self.nodes[ileft] < self.nodes[imin]):
            imin = ileft
        if( iright < size and self.nodes[iright] < self.nodes[imin]):
            imin = iright
        if( imin != i):
            self.nodes[i], self.nodes[imin] = self.nodes[imin], self.nodes[i]
            self.min_heapify_subtree(imin)
 
 
    # Преобразует в кучу массив, который ей не является
    def min_heapify(self):
        for i in range(len(self.nodes), -1, -1):
            self.min_heapify_subtree(i)
 
    def min(self):
        return self.nodes[0]
 
    def pop(self):
        min = self.nodes[0]
        if self.size() > 1:
            self.nodes[0] = self.nodes[-1]
            self.nodes.pop()
            self.min_heapify_subtree(0)
        elif self.size() == 1: 
            self.nodes.pop()
        else:
            return None
        return min
 
    # Обновляет значение узла, изменяя его для сохранения свойства кучи
    def decrease_key(self, i, val):
        self.nodes[i] = val
        iparent = self.iparent(i)
        while( i != 0 and self.nodes[iparent] > self.nodes[i]):
            self.nodes[iparent], self.nodes[i] = self.nodes[i], self.nodes[iparent]
            i = iparent
            iparent = self.iparent(i) if i > 0 else None

Хорошо, время для последнего шага. Теперь уже точно! Нам просто нужно выяснить, как внедрить структуру данных MinHeap в метод dijsktra в Graph, который теперь должен быть реализован с помощью списка смежности. Нужно реализовать его, полностью используя преимущества среды выполнения кучи, при этом поддерживая класс MinHeap настолько гибким, насколько это возможно. Это нужно для повторного использования в будущем.

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

Уже знакомый нам граф:

Список смежности графа будет выглядеть приблизительно следующим образом:

[ 
  [ NodeA, [(NodeB, 5), (NodeC, 10), (NodeE, 2)] ],
  [ NodeB, [(NodeA, 5), (NodeC, 2), (NodeD, 4)] ],
  [ NodeC, [(NodeA, 10), (NodeB, 2), (NodeD, 7), (NodeF, 10)] ],
  [ NodeD, [(NodeB, 4), (NodeC, 7), (NodeE, 3)] ],
  [ NodeE, [(NodeA, 2), (NodeD, 3)] ],
  [ NodeF, [(NodeC, 10)]
]
Как видите, для получения определенной связи узлов нам больше не нужно проверять ВСЕ прочие узлы. Оставим API относительно простым, ради ясности оставим класс простым:
class Graph: 
 
    def __init__(self, nodes):
        self.adj_list = [ [node, []] for node in nodes ]
        for i in range(len(nodes)):
            nodes[i].index = i
 
 
    def connect_dir(self, node1, node2, weight = 1):
        node1, node2 = self.get_index_from_node(node1), self.get_index_from_node(node2)
        # Обратите внимание, что указанное ниже не защищает от добавления связи дважды
        self.adj_list[node1][1].append((node2, weight))
 
    def connect(self, node1, node2, weight = 1):
        self.connect_dir(node1, node2, weight)
        self.connect_dir(node2, node1, weight)
 
    
    def connections(self, node):
        node = self.get_index_from_node(node)
        return self.adj_list[node][1]
    
    def get_index_from_node(self, node):
        if not isinstance(node, Node) and not isinstance(node, int):
            raise ValueError("node must be an integer or a Node object")
        if isinstance(node, int):
            return node
        else:
            return node.index

Далее сосредоточимся на реализации кучи для достижения лучшего алгоритма, чем текущий алгоритм O(n²). Если вспомним метод dijsktra, в классе Graph матрицы смежности, то увидим, что мы перебираем всю очередь, чтобы найти минимальное предварительное расстояние provisional distance (время выполнения O(n)), используя узел с минимальным значением для установки текущего посещаемого узла. Затем перебираем все соединения узла и при необходимости сбрасываем их предварительное расстояние provisional distance (проверьте метод connections_to или connections_from; вы увидите, что его время выполнения O(n)). Эти два алгоритма O(n) сводятся к времени выполнения O(n), потому что O(2n) = O (n). Делаем это для каждого узла графа, поэтому выполняем O(n) алгоритм n раз, тем самым получая время выполнения O(n²). Вместо этого сокращаем время выполнения до O((n + e) lg (n)), где n — количество узлов, а e — количество ребер.

В реализации списка смежности внешнему циклу while все еще нужно выполнять итерацию по всем узлам (n итераций), но чтобы получить ребра для текущего узла внутренний цикл просто должен итерировать ТОЛЬКО по ребрам для данного конкретного узла. Таким образом, внутренний цикл, повторяющийся по краям узла, будет выполняться только O(n + e) раз. Внутри данного внутреннего цикла нужно обновить предварительное расстояние для каждого из связанных узлов. Для этого будет использован метод decrease_key кучи, который мы уже рассматривали, как O(lg (n)). Таким образом, общее время выполнения будет равно O((n + e) lg (n)).

Новый алгоритм:

ИНИЦИАЛИЗАЦИЯ

Установите provisional_distance всех узлов от источника до бесконечности, за исключением нашего исходного узла, значением которого будет 0. Добавьте данные к минимальной куче.
Вместо сохранения набора seen_nodes определите, есть ли у вас осмотренные узлы. Это будет зависеть от того, что осталось в куче. Помните, что при использовании pop() для узла, он удаляется из кучи. Следовательно, в соответствии с логикой он будет рассматриваться, как «увиденный».

ПРОЦЕДУРА ИТЕРАЦИИ

Цикл while выполняется до тех пор, пока куча > 0: (выполняется n раз)
Установите current_node для возвращения значения heap.pop().
Для n в current_node.connections используйте heap.decrease_key, если данная связь все еще в куче (то есть не была рассмотрена), А ТАКЖЕ если текущее значение provisional distance больше, чем предварительное расстояние current_node вместе с весом соседнего элемента. Данный цикл for в общем будет выполняться n + e раз, а его временную сложность можно представить, как O(lg(n)).
Конец цикла while.

Есть две задачи, которые нужно решить при данной реализации:

Задача 1: Код написан таким образом, что куча работает с массивом чисел. Однако нам нужна инкапсуляция предварительного расстояния provisional distance (метрики, которая использовалась при преобразовании в кучу), перескоков И узла, которому соответствует расстояние.

Задача 2: Нужно проверить, находится ли узел внутри кучи, А ТАКЖЕ обновить его provisional distance, используя метод decrease_key, для которого требуется индекс данного узла в куче. Для сохранения своих свойств куча постоянно меняет индексы. Нужно убедиться, что данная задача не будет решена простым анализом кучи в поисках точного места узла. Данная операция O(n) будет выполняться (n + e) раз, следовательно, создание кучи и реализация списка смежности ни к чему не приведут, ведь нам нужно со всем управиться за O(1) раз.

Решение 1: Нам нужно сохранить реализацию кучи максимально гибкой. Чтобы принимать любой тип данных в качестве элементов в базовом массиве, можно просто принять необязательные анонимные функции (например, лямбда-выражения) при создании экземпляра, которые предоставляются пользователем, чтобы указать, как он должен обращаться с элементами внутри массива, если эти элементы не являются простым целым числом. Значением по умолчанию для лямбд может быть функция, которая работает, если элементы массива являются просто числами. Таким образом, если требуется простая куча с числами, пользователю не нужно вставлять лямбды. Данные настраиваемые процедуры потребуются для сравнения элементов, а также для возможности уменьшить значение элемента. Можно назвать лямбду сравнения is_less_than, и ее значение по умолчанию должно быть: a, b: a < b. Лямбда-функция для возврата обновленного узла с новым значением может называться update_node, и ее значение по умолчанию должно быть просто lambda node, newval: newval. При передаче узла и нового значения пользователю дается возможность определить лямбду, которая обновляет существующий объект ИЛИ заменяет значение, которое там находится. В контексте реализации старого Graph, поскольку узлы имели бы значения [ provisional_distance, [nodes, in, hop, path]] лямбда is_less_than могла бы выглядеть следующим образом: lambda a,b: a[0] < b[0]. Здесь можно было бы оставить значение второй лямбды по умолчанию и передать вложенный массив в decrease_key.

Тем не менее, вскоре станет ясно, что существует довольно простое решение вопроса, при котором создаются настраиваемые объекты узлы node и передаются в MinHeap. Гибкость, которая недавно упоминалась, позволит легко воплотить это элегантное решение. В частности, в приведенном ниже коде вы увидите, что лямбда is_less_than превратиться в: lambda a, b: a.prov_dist < b.prov_dist, а лямбда update_node станет: lambda node, data: node.update_data (data), что намного аккуратнее использования вложенных массивы.

Решение 2: Есть несколько способов решить данную задачу, но давайте попробуем выбрать тот, который идет рука об руку с Решением 1. Учитывая гибкость, которой мы добились в Решении 1, мы можем продолжать использовать эту стратегию для реализации дополняющего решения и здесь. Можно реализовать дополнительный массив внутри класса MinHeap, который отображает исходный порядок вставленных узлов в их текущий порядок внутри массива узлов. Назовем этот список order_mapping. Поддерживая этот список, мы можем получить любой узел из кучи за время O(1), учитывая, что мы знаем исходный порядок, в котором узел был вставлен в кучу. Таким образом, если порядок узлов, в котором создаётся куча, совпадает с номером индекса узлов Graph, теперь у нас есть отображение узла Graph до относительного местоположения этого узла в MinHeap в постоянном времени! Чтобы иметь возможность поддерживать это отображение в актуальном состоянии за время O(1), все элементы, передаваемые в MinHeap как узлы, должны каким-то образом «знать» свой исходный индекс, а MinHeap необходимо знать, как считывать исходный индекс с этих узлов. Это требуется для того чтобы он мог обновить значение order_mapping по номеру индекса свойства индекса узла index до значения текущей позиции этого узла в списке узлов MinHeap. Поскольку нам нужно разрешить использование MinHeap, тем, кто не нуждается в этом отображении, А ТАКЖЕ нам нужно, чтобы любые типы данных были узлами кучи, мы можем снова разрешить добавление лямбда-выражения пользователем. Оно сообщит MinHeap, как получить номер индекса из любого типа данных, что добавляются в кучу — его названием будет get_index.

Например, если бы данные для каждого элемента в куче были списком структуры [data, index], лямбда get_index была бы: lambda el: el [1]. Кроме того, мы можем установить для get_index значение по умолчанию None, и доверить ему принятие решений, поддерживается или нет массив order_mapping. Таким образом, если пользователь не вводит лямбду, чтобы сообщить куче, как получить индекс из элемента, куча не будет отслеживать order_mapping, что позволяет пользователю использовать кучу без этой функциональности только с базовыми типами данных, такими как целые числа. Лямбда get_index, что будет в итоге использоваться, так как будет задействован пользовательский объект узла, будет очень простой: lambda node: node.index ().

Результатом совмещения решений 1 и 2 является одно чистое решение. Создается класс DijkstraNodeDecorator для декорирования всех узлов, составляющих граф. Этот декоратор предоставит дополнительные данные о provisional distance (инициализированном в бесконечность) и hoop list (инициализированном в пустой массив). Кроме того, он будет реализован с помощью метода, который позволит объекту обновляться самому. Потом это можно использовать в лямбда-выражении для decrease_key. DijkstraNodeDecorator сможет получить доступ к индексу декорируемого узла, и мы воспользуемся этим фактом, указав куче, как получить индекс узла при помощи лямбды get_index из Решения 2.

Финальный код алгоритма Дейкстры Python:

class DijkstraNodeDecorator:
    
    def __init__(self, node):
        self.node = node
        self.prov_dist = float('inf')
        self.hops = []
 
    def index(self):
        return self.node.index
 
    def data(self):
        return self.node.data
    
    def update_data(self, data):
        self.prov_dist = data['prov_dist']
        self.hops = data['hops']
        return self

Использоваля для декорирования узлов в реализации Graph ниже.

class MinHeap(BinaryTree):
 
    def __init__(self, nodes, is_less_than = lambda a,b: a < b, get_index = None, update_node = lambda node, newval: newval):
        BinaryTree.__init__(self, nodes)
        self.order_mapping = list(range(len(nodes)))
        self.is_less_than, self.get_index, self.update_node = is_less_than, get_index, update_node
        self.min_heapify()
 
    # Изменение в кучу узлов, предполагается, что все поддеревья уже кучи
    def min_heapify_subtree(self, i):
 
        size = self.size()
        ileft = self.ileft(i)
        iright = self.iright(i)
        imin = i
        if( ileft < size and self.is_less_than(self.nodes[ileft], self.nodes[imin])):
            imin = ileft
        if( iright < size and self.is_less_than(self.nodes[iright], self.nodes[imin])):
            imin = iright
        if( imin != i):
            self.nodes[i], self.nodes[imin] = self.nodes[imin], self.nodes[i]
            # Если есть лямбда для получения абсолютного индекса узла
            # обновляет массив order_mapping для указания, где находится индекс
            # в массиве узлов (осмотр для этого индекса будет 0(1))
            if self.get_index is not None:
                self.order_mapping[self.get_index(self.nodes[imin])] = imin
                self.order_mapping[self.get_index(self.nodes[i])] = i
            self.min_heapify_subtree(imin)
 
 
    # Превращает в кучу массив, который еще ей не является
    def min_heapify(self):
        for i in range(len(self.nodes), -1, -1):
            self.min_heapify_subtree(i)
 
    def min(self):
        return self.nodes[0]
 
    def pop(self):
        min = self.nodes[0]
        if self.size() > 1:
            self.nodes[0] = self.nodes[-1]
            self.nodes.pop()
            # Обновляет order_mapping, если можно
            if self.get_index is not None:
                self.order_mapping[self.get_index(self.nodes[0])] = 0
            self.min_heapify_subtree(0)
        elif self.size() == 1: 
            self.nodes.pop()
        else:
            return None
        # Если self.get_index существует, обновляет self.order_mapping для указания, что
        # узел индекса больше не в куче
        if self.get_index is not None:
            # Устанавливает значение None для self.order_mapping для обозначения непринадлежности к куче 
            self.order_mapping[self.get_index(min)] = None
        return min
 
    # Обновляет значение узла и подстраивает его, если нужно, чтобы сохранить свойства кучи
    def decrease_key(self, i, val):
        self.nodes[i] = self.update_node(self.nodes[i], val)
        iparent = self.iparent(i)
        while( i != 0 and not self.is_less_than(self.nodes[iparent], self.nodes[i])):
            self.nodes[iparent], self.nodes[i] = self.nodes[i], self.nodes[iparent]
            # Если есть лямбда для получения индекса узла 
            # обновляет массив order_mapping для указания, где именно находится индекс
            # в массиве узлов (осмотр этого индекса O(1))
            if self.get_index is not None:
                self.order_mapping[self.get_index(self.nodes[iparent])] = iparent
                self.order_mapping[self.get_index(self.nodes[i])] = i
            i = iparent
            iparent = self.iparent(i) if i > 0 else None
 
    def index_of_node_at(self, i):
        return self.get_index(self.nodes[i])

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

class Graph: 
 
 
    def __init__(self, nodes):
        self.adj_list = [ [node, []] for node in nodes ]
        for i in range(len(nodes)):
            nodes[i].index = i
 
 
    def connect_dir(self, node1, node2, weight = 1):
        node1, node2 = self.get_index_from_node(node1), self.get_index_from_node(node2)
        # Отмечает, что нижеуказанное не предотвращает от добавления связи дважды
        self.adj_list[node1][1].append((node2, weight))
 
    def connect(self, node1, node2, weight = 1):
        self.connect_dir(node1, node2, weight)
        self.connect_dir(node2, node1, weight)
 
    
    def connections(self, node):
        node = self.get_index_from_node(node)
        return self.adj_list[node][1]
    
    def get_index_from_node(self, node):
        if not isinstance(node, Node) and not isinstance(node, int):
            raise ValueError("node must be an integer or a Node object")
        if isinstance(node, int):
            return node
        else:
            return node.index
 
    def dijkstra(self, src):
        
        src_index = self.get_index_from_node(src)
        # Указывает узлы к DijkstraNodeDecorators
        # Это инициализирует все предварительные расстояния до бесконечности
        dnodes = [ DijkstraNodeDecorator(node_edges[0]) for node_edges in self.adj_list ]
        # Устанавливает предварительное расстояние исходного узла до 0 и его массив перескоков к его узлу
        dnodes[src_index].prov_dist = 0
        dnodes[src_index].hops.append(dnodes[src_index].node)
        # Устанавливает все методы настройки кучи
        is_less_than = lambda a, b: a.prov_dist < b.prov_dist
        get_index = lambda node: node.index()
        update_node = lambda node, data: node.update_data(data)
 
        # Подтверждает работу кучи с DijkstraNodeDecorators с узлами
        heap = MinHeap(dnodes, is_less_than, get_index, update_node)
 
        min_dist_list = []
 
        while heap.size() > 0:
            # Получает узел кучи, что еще не просматривался ('seen')
            # и находится на минимальном расстоянии от исходного узла
            min_decorated_node = heap.pop()
            min_dist = min_decorated_node.prov_dist
            hops = min_decorated_node.hops
            min_dist_list.append([min_dist, hops])
            
            # Получает все следующие перескоки. Это больше не O(n^2) операция
            connections = self.connections(min_decorated_node.node)
            # Для каждой связи обновляет ее путь и полное расстояние от 
            # исходного узла, если общее расстояние меньше, чем текущее расстояние
            # в массиве dist
            for (inode, weight) in connections: 
                node = self.adj_list[inode][0]
                heap_location = heap.order_mapping[inode]
                if(heap_location is not None):
                    tot_dist = weight + min_dist
                    if tot_dist < heap.nodes[heap_location].prov_dist:
                        hops_cpy = list(hops)
                        hops_cpy.append(node)
                        data = {'prov_dist': tot_dist, 'hops': hops_cpy}
                        heap.decrease_key(heap_location, data)
 
        return min_dist_list

a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')
e = Node('e')
f = Node('f')
 
g = Graph([a,b,c,d,e,f])
 
g.connect(a,b,5)
g.connect(a,c,10)
g.connect(a,e,2)
g.connect(b,c,2)
g.connect(b,d,4)
g.connect(c,d,7)
g.connect(c,f,10)
g.connect(d,e,3)
 
print([(weight, [n.data for n in node]) for (weight, node) in g.dijkstra(a)])

Результат вывода финального кода:

Как видите, вывод такой же, как и в прошлом варианте реализации алгоритма. Сам код выглядит теперь намного аккуратнее. Кроме того, сейчас нам удалось добиться реализации алгоритма Дейкстры за время O((n + e)lg(n)).