Алгоритм Flood fill на Python

Алгоритм Flood fill возвращает замкнутую область внутри массива. Кроме областей связанных с графикой, алгоритм может применяется для поиска замкнутых областей в игре Го и для сходных задач.

Алгоритм основан на рекурсии. Проверяется заданный элемент массива, затем процедура вызывается для всех соседних элементов:

Реализация на Python:

Алгоритм легко модифицируется для случая с трёхмерным массивом или если нужно учитывать соседние элементы по диагоналям.

Примеры использования JSONPath в Python

Перевод статьи Python JSONPath Examples.

Что такое JSONPath?

JSONPath это язык запросов к JSON. Он очень похож на язык запросов XPath для XML. Вы формируете строку запроса и получаете нужное значение. Такое подход экономит память, так как необходимости разбазарить JSON полностью.

Библиотеки Python для JSONPath

Существует много JSONPath-библиотек для Python.

jsonpath: это портированая из Perl и JavaScript версия JSONPath.

jsonpath-rw: полностью Python-реализация JSONPath. Объект выражения JSONPath это объект первого класса, простой для анализа, преобразования, обработки, печати и расширения. Модуль jsonpath-rw-ext расширяет функционал библиотеки.

jsonpath-ng: окончательная реализация JSONPath цель которой соответствие стандарту, включая арифметические и бинарные сравнения. Эта библиотека соединяет модули jsonpath-rw и jsonpath-rw-ext и расширяет их.

Какую библиотеку использовать?

Модуль jsonpath-ng самый развитый и написан на чистом Python. Он поддерживает Python 2 и Python 3. Мы будем использовать этот модуль для примеров.

Установка модуля:

Читать далее Примеры использования JSONPath в Python

Области видимости в Python

Перевод статьи Understanding Python scope.

Рассмотрим функцию Python и модульный тест для неё. Что в ней неверно?

Запустим тест:

Выглядит так как будто функция callback не вызвана. Проверим это: если изменить аргумент для callback передаваемый в method_under_test(), вы увидите что проверка в функции callback срабатывает.

Разберёмся почему так происходит.

Читать далее Области видимости в Python

Поверхностное и глубокое копирование в Python

Перевод статьи Python Shallow Copy and Deep Copy.

Копирование объектов в Python

Оператор присваивания = не создаёт копию объекта. Присваивание создаёт новую переменную которая дублирует ссылку на исходный объект.

Рассмотрим пример

После запуска программа выдаст следующее:

Обе переменные ссылаются на один объект, это подтверждает одинаковый идентификатор объекта 140673303268168. Так что при изменении значений в переменных new_list и old_list, изменение будет видно в обоих переменных.

Иногда нужно оставить исходное значение без изменений и модифицировать только новое. В Python, есть два способа сделать копию: поверхностное копирование и глубокое копирование.

Читать далее Поверхностное и глубокое копирование в Python

Изменяемые и неизменяемые объекты в Python

Перевод статьи Mutable vs Immutable Objects in Python.

Все значения в Python это объекты. Объекты делятся на изменяемые и неизменяемые.

Python, схема объектов

Каждая переменная ссылается на экземпляр объекта. При создании, объекту присваивается уникальный идентификатор (object id) и тип объекта. Тип объекта не меняется после создания, но может изменится состояние объекта. Изменяемые объекты меняют своё состояние после создания, а неизменяемые сохраняются в том виде в котором были созданы.

Встроенные неизменяемые типы: int, float, bool, str, tuple, unicode. Встроенные изменяемые типы list, set, dict. Пользовательские классы обычно изменяемы. Для имитирования неизменяемости переопределите методы изменения и удаления значений чтобы они возвращали исключение.

Python. таблица изменяемых и неизменяемых объектов

Чтобы узнать ссылается ли переменная на изменяемый или неизменяемый рассмотрим подробнее функции id() и type().

Читать далее Изменяемые и неизменяемые объекты в Python

Python. Свойства

Перевод статьи Python @property.

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

Начальный пример

Представим что вы решили сделать класс хранящий температуру в градусах Цельсия. Он также должен реализовывать метод для конвертации температуры в градусы Фаренгейта. Реазуем класс так:

Затем создаём объект этого класса и меняем значение температуры как пожелаем:

Дополнительные десятичные разряды при конвертации в градусы Фаренгейта происходят из-за арифметической ошибки с плавающей запятой (попробуйте сложить 1.1 + 2.2 в интерпретаторе).

Когда мы присваиваем или извлекаем атрибут объекта, такой как temperature, Python ищет его в словаре объекта __dict__.

Внутри интерпретатора man.temperature становится man.__dict__['temperature'].

Читать далее Python. Свойства

Python. Функция property()

Перевод статьи Python | property() function.

Функция property() создаёт новое свойство. Свойство — это атрибут класса с которым связаны функции чтения и записи.

Параметры:

  • fget() – используется для получения значения атрибута
  • fset() – используется для установки значения атрибута
  • fdel() – используется для удаления атрибута
  • doc() – строка с документацией (docstring) для атрибута

Функция property() возвращает свойство с данными геттером, сеттером и deleter.

Вызванная без аргументов функция property() возвращает свойство без геттера, сеттера и deleter.

Читать далее Python. Функция property()

Python. Структуры данных: список, кортеж, множество, словарь

Перевод параграфа 3.6 Data Structures из книги Intermediate Python.

Python содержит встроенные типы данных: списки, кортежи, словари.

Списки

Чтобы создать список используйте квадратные скобки или функцию list():

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

Первый элемент списка находится под индексом 0, последний — на единицу меньше длины списка.

Метод append() добавляет элемент в список.

Читать далее Python. Структуры данных: список, кортеж, множество, словарь

Задача Pythagorean Triplet

Условие

Дано число \(N\). Найти все пифагоровы тройки такие что \(a + b + c = N\). Пифагоровы тройки удовлетворяют условиям \(a^2 + b^2 = c^2\) и \(a \lt b \lt c\).

Решение

Простейшее решение перебором даёт сложность \(O(n^2)\):

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

Эту же задачу можно решить за \(O(n)\). Из условий задачи следуют два уравнения:

  • \(a + b + c = N\)
  • \(a^2 + b^2 = c^2\)

\(N\) является константой. Примем так же за константу \(a\). Остаётся система из двух уравнений с двумя неизвестными. Последовательно решаем её.

  • \(c = N - a - b\) (1)
  • \(c^2 - b^2 = a^2\)
  • \((c - b)(c + b) = a^2\) (2)
  • \((n - a - b - b)(n - a - b + b) = a^2\) (подставляем 1 в 2)
  • \((n - a - 2b)(n - a) = a^2\)
  • \(n^2 - an - 2nb - an + a^2 + 2ab = a^2\)
  • \(n^2 - 2an - 2nb + 2ab = 0\)
  • \((2a - 2n)b = 2an - n^2\)
  • \(b = \frac{2an - n^2}{2a - 2n}\)
  • \(c = N - a - b\)

Используя формулы для вычисления \(b\) и \(c\) в цикле по \(a\) находим все пифагоровы тройки.

Проверка xml по xsd на Python через lxml

В библиотеке lxml содержаться функции для проверки xml по xsd. Пример кода:

Метод validate возвращает False если xml не проходит проверку по схеме. Свойство error_log содержит список несоответствий xml схеме из xsd.