Рубрика: Программирование

Посты, связанные с разработкой ПО.

​​Сортировка пузырьком

Сегодня простая, но важная тема. Алгоритм сортировки пузырьком, его проходят на курсах, его часто спрашивают на собеседованиях. Сортировка — это процесс выстраивания массива или списка по возрастанию или убыванию. На примере чисел: [3, 1, 4, 2] → [1, 2, 3, 4].

Смысл пузырьковой сортировки заключается в следующем: мы начинаем с начала списка и сравниваем элементы попарно (нулевой и первый), если нулевой больше первого, то меняем их местами. Независимо от того, была ли замена или нет, мы шагаем вправо и сравниваем элементы вновь. Если на прошлом шаге была замена, то на этом шаге у нас окажется тот же элемент, и если он опять оказался больше, то «всплывет» снова вправо. Так за один проход наибольший элемент всплывет в самый-самый конец списка, подобно тому, как пузырек воздуха всплывает в бутылке воды. Когда все пузырьки всплывут – список будет отсортирован.

📎 Пример: a = [3, 1, 4, 2] – 4 элемента:

Первый проход:
  1. Сравним a[0] = 3 и a[1] = 1, 3 > 1. Меняем их местами. Теперь a = [1, 3, 4, 2].
  2. Сравним a[1] = 3 и a[2] = 4, 3 < 4. Менять не надо.
  3. Сравним a[2] = 4 и a[3] = 2, 4 > 2. Меняем. a = [1, 3, 2, 4].

Проход окончен. 4 «всплыла» в самый конец списка на свое место a[3]. Поэтому мы не трогаем больше конец списка, но список еще не отсортирован до конца, и следующий проход будет рассматривать только первые 3 элемента списка.

Второй проход:
  1. Сравним a[0] = 1 и a[1] = 3, 1 < 3. Менять не надо.
  2. Сравним a[1] = 3 и a[2] = 2, 3 > 2. Меняем их. a = [1, 2, 3, 4]. Проход окончен.
Третий проход:
  1. Сравним a[0] = 1 и a[1] = 3, 1 < 3. Менять не надо. Список отсортирован. Можно выходить.

👨‍💻 Переходим к реализации на Python:

def bubble_sort(a):
    n = len(a)
    
    # номер прохода i = 0..(n-2), т.е. (n-1 раз):
    for i in range(n - 1):
        # номер сравнения j = 0..(n - i - 2)
        for j in range(n - i - 1):
            # сравниваем только соседние элементы
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

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

  • Начинаем всегда с начала (0-го элемента).
  • Число проходов меньше на 1, чем число элементов
  • С каждым проходом мы делаем все меньше и меньше сравнений, так как сортированный хвост списка растет на 1 после каждого прохода
  • Сравниваем только соседние элементы a[j] > a[j + 1], (а не i и j).
  • Если знак сравнения перевернуть, то сортировка будет по убыванию.

Временная сложность алгоритма квадратичная O(n^2) – имеются два вложенных цикла по элементам. Поэтому алгоритм медлителен для больших списков.  В реальной жизни чаще применяются другие алгоритмы сортировки, но пузырек до сих пор не забывают преподавать и спрашивать.

🐉 Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈 

Класс-декоратор и декоратор класса

Эти две темы не так близки, как кажется, но я не мог разнести их в разные посты, лишая себя такого заголовка. Узнаем, как из класса сделать декоратор, и как написать декоратор для класса. Код примеров доступен в GIST под каждым из разделов.

Класс как декоратор

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

class Functor:
    def __call__(self, a, b):
        print(a * b)

f = Functor()
# вызов как будто функция
f(10, 20)

Как мы помним из https://tirinox.ru/parametric-decorator/ , справа от собачки в декораторе может стоять не только функция-декоратор, но любой вызываемый объект, например, функтор. __call__, которого будет принимать на вход единственный параметр – декорируемую функцию. На примере того же декоратора-повторителя вызовов:

from functools import wraps

class Repeater:
    def __init__(self, n):
        self.n = n

    def __call__(self, f):
        @wraps(f)
        def wrapper(*args, **kwargs):
            for _ in range(self.n):
                f(*args, **kwargs)
        return wrapper

@Repeater(3)
def foo():
    print('foo')

foo() 
# foo
# foo
# foo

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

Код здесь https://gist.github.com/tirinox/b6fd34de1b9de229ec2666f160c1ad82.

Декоратор для класса

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

  1. Декоратор класса имеет более глубокие возможности по влиянию на класс, он может удалять, добавлять, менять, переименовывать атрибуты и методы класса. Он может возвращать совершенно другой класс.
  2. Старый класс «затирается» и не может быть использован, как базовый класс при полиморфизме
  3. Декорировать можно любой класс одним и тем же универсальный декоратором, а при наследовании – мы ограничены иерархией классов и должны считаться с интерфейсами базовых классов.
  4. Презираются все принципы и ограничения ООП (из-за пунктов 1-3).

Декораторы классов полезны, чтобы внедриться в класс (иногда незаметно) и массово воздействовать на его методы и атрибуты. Типичный пример – создадим декоратор, который будет измерять время выполнения каждого метода класса. При этом сам класс никаких изменений не претерпит и не будет знать, что за ним следят:

import time

# это вспомогательный декоратор будет декорировать каждый метод класса, см. ниже
def timeit(method):
    def timed(*args, **kw):
        ts = time.time()
        result = method(*args, **kw)
        te = time.time()
        delta = (te - ts) * 1000
        print(f'{method.__name__} выполнялся {delta:2.2f} ms')
        return result
    return timed


def timeit_all_methods(cls):
    class NewCls:
        def __init__(self, *args, **kwargs):
            # проксируем полностью создание класса
            # как создали этот NewCls, также создадим и декорируемый класс
            self._obj = cls(*args, **kwargs)

        def __getattribute__(self, s):
            try:
                # папа, у меня есть атрибут s?
                x = super().__getattribute__(s)
            except AttributeError:
                # нет сынок, это не твой атрибут
                pass
            else:
                # да сынок, это твое
                return x

            # объект, значит у тебя должен быть атрибут s
            attr = self._obj.__getattribute__(s)

            # метод ли он?
            if isinstance(attr, type(self.__init__)):
                # да, обернуть его в измеритель времени
                return timeit(attr)
            else:
                # не метод, что-то другое
                return attr
    return NewCls


@time_all_class_methods
class Foo:
    def a(self):
        print("метод a начался")
        time.sleep(0.666)
        print("метод a кончился")


f = Foo()
f.a()

# метод a начался
# метод a кончился
# a 668.74 ms

Рассмотрим подробно части кода. timeit – это простой декоратор для функций, мы его уже умеем делать. Он нужен для того, чтобы декоратор класса timeit_all_methods обернул в timeit каждый метод декорируемого класса.

Декоратор timeit_all_methods содержит в себе определение нового класса NewCls и возвращает его вместо оригинального класса. Т.е. класс Foo – это уже не Foo, а NewCls. Конструктор класса NewCls принимает произвольные аргументы (ведь нам не известно заранее, какой конструктор у Foo, и у любого другого класса, который мы декорируем). Поэтому конструктор просто создает поле, где будет хранить экземпляр оригинального класса, и передает ему в конструктор все свои аргументы.

Самый сложный метод – __getattribute__ – он полон магии. Он вызывается, когда кто-то пытается обратиться как какому угодно атрибуту (полю, методы и т. п.) класса NewCls. Первым делом мы должны обратиться к своему родителю super() и спросить у него, не обладаем ли мы сами атрибутом, который проверяем. Именно к родителю, чтобы избежать рекурсии (иначе мы попадем в тот же метод, в котором уже находимся)! Если это наш атрибут (атрибут класса декоратора) – вернем его сразу, с ним ничего не надо делать. Иначе, вероятно, это атрибут исходного класса – получим его у него. И проверим его тип, сравним его с типом любого метода. Если тип – метод (bound method), то обернем его в декоратор timeit и вернем, иначе (это не метод, а свойство или статический метод) – вернем без изменений.

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

Задание на дом: создать класс декоратор класса, иначе говоря скрестить два раздела статьи и сделать класс-функтор, который может декорировать другой класс. Идея: декоратор, который измеряет время выполнения каждого метода, и печатает предупреждение, только если время выполнения было больше критического (параметр):

@TimeItCritical(critical_time=0.3)
class Foo:
    def a(self):
        print("медленный метод начался")
        time.sleep(1.0)
        print("медленный метод кончился")

    def b(self):
        time.sleep(0.1)
        print('быстрый метод')

f = Foo()
f.a()
f.b()

# медленный метод начался
# медленный метод кончился
# a выполнялся медленно 1.0011 s
# быстрый метод

Код доступен в https://gist.github.com/tirinox/507258b36e77dfec1448f8cf1d259356

🤩 Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway! 👈

Python 3.8 здесь!

3.8

🐍Отложим дела ради классной новости! Python версии 3.8 официально релизнулся!

Что в новой версии?

1️⃣ Оператор морж (писал о нем ранее). Присваивание переменной внутри других выражений:

if (n := len(a)) > 10:
    print("слишком длинно")

while (block := f.read(256)) != '':
    process(block)

[clean_name.title() for name in names
 if (clean_name := normalize('NFC', name)) in allowed_names]

2️⃣ Разделитель позиционных аргументов (слэш /). Указывает, что первые несколько аргументов могут быть только позиционными (в строгом порядке, без указания имени). Напомню, что именные аргументы передаются с указанием имени, и не важно в каком порядке. В примере ниже a и b – только позиционные, c и d — могут быть позиционные или переданы по имени, а e и f – исключительно именные:

def f(a, b, /, c, d, *, e, f):
    print(a, b, c, d, e, f)

# разрешенный вызов:
f(10, 20, 30, d=40, e=50, f=60)

# НЕЛЬЗЯ передать b по имени 
# (b стоит до слэша)
f(10, b=20, c=30, d=40, e=50, f=60) 

# НЕЛЬЗЯ передать e без указания имени
# (e стоит после звездочки)
f(10, 20, 30, 40, 50, f=60) 

3️⃣ Спецификатор = для f-строк. Тут проще на примере, раньше мы писали с повторами:

>>> user = 'eric_idle'
>>> since = date(1975, 7, 31)
>>> f'user={user} since={since}'
"user='eric_idle' since=datetime.date(1975, 7, 31)"

А теперь можно так:

>>> f'{user=} {since=}'
"user='eric_idle' since=datetime.date(1975, 7, 31)"

После знака равно можно добавлять и прочие спецификаторы форматирования:

>>> delta = date.today() - since
>>> f'{user=!s} {delta.days=:,d}'
'user=eric_idle delta.days=16,075'

Для отладки принтами — просто восторг!

4️⃣ Теперь можно continue внутри finally

Еще есть множество улучшений со стороны C-API, всякие хуки аудита, вектор-коллы. Новая настройка PYTHONPYCACHEPREFIX, чтобы вынести кэш байткода из стандартной директории pycache куда вам удобно. Очень-очень много разных мелких изменений в стандартных модулях и функциях, о которых расскажу при случае.

Что нового по-английски

Как вам новая версия?

Декораторы с параметрами

Схема параметрического декоратора

Как я сказал ранее, декоратор – по сути функция с аргументом – другой функцией, но как добавить туда еще аргументы, подобно коду ниже?

@lru_cache(maxsize=100)
def sqr(i):
    return i ** 2

Справа от знака собачки (@) в синтаксисе декоратора должен стоять какой-то вызываемый объект (т.е. тот, который можно вызвать как функцию), короче нечто foo, которое будет вызвано, как foo(f) в процессе декорации, где f – декорируемая функция. Под это описание попадают:

  • имя функции
  • переменная, которой присвоена функция
  • экземпляр класса, у которого реализован __call__
  • или собственно функциональный вызов func(...), который вернет что-то тоже вызываемое из списка выше

Последний вариант и обеспечивает передачу параметров в декоратор:

@decorator(param=42)
def foo(x, y):
    return x + y

Эквивалентно примерно этому:

foo = decorator(param=42)(foo)

# или

pure_decorator = decorator(param=42)
foo = pure_decorator(foo)

Т. е. сначала вызываем декоратор с параметрами (decorator), он возвращает нам «чистый» декоратор (я назвал его pure_decorator) – функцию с одним параметром, а потом он уже оборачивает исходную функцию foo. Короче функция, которая возвращает декоратор, который возвращаем обернутую функцию. Как же это реализовать? Попробуем на примере декоратор, который повторяет функцию n раз. Начнем с фиксированного n = 5:

from functools import wraps

def repeat(f):
    n = 5
    
    @wraps(f)
    def inner(*args, **kwargs):
        for _ in range(n):
            f(*args, **kwargs)
    return inner

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

def repeat(n=5):
    def _repeat(f):
        @wraps(f)
        def inner(*args, **kwargs):
            for _ in range(n):
                f(*args, **kwargs)
        return inner
    # не забываем ее вернуть!
    return _repeat

Вот перед нами три уровня вложенности функций. Это может показаться сложновато, но нужно понять, какая функция для чего нужна:

  • repeat нужна, чтобы передать параметр n в _repeat, потому что _repeat не может принять ничего кроме единственного аргумента функции f.
  • _repeat нужна, чтобы создать симулякр inner, который умеет принимать любые неважно какие аргументы
  • inner нужна, чтобы обернуть вызовы к f и транслировать аргументы f.

Тестируем:

@repeat(3)
def foo():
    print('hello')

foo()
# hello
# hello
# hello

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

twice = repeat(2)

@twice
def bar():
    print('bar')
bar() # два раза вызовет

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

Декоратор, который умеет вызываться с параметром и без

Если мы не укажем n, то repeat будет делать 5 повторов по умолчанию. Можно избавить от необходимости писать пустые скобки, а модифицировать код, чтобы стал более гибким и, работало и так, и так:

@repeat(n=5)
def baz(): ...

@repeat
def baz(): ...

Тут нужна хитрость. Добавим в декоратор скрытый параметр _func = None на самом первом месте. Получится так, что если декоратор вызван без скобок, то единственным его параметром будет декорируемая функция (что подпадает под определение чистого декоратора), которая попадет в переменную _func, а иначе она будет равна None. Если же, мы передаем только именованный параметр n=10, то остается _func = None и благодаря этому декоратор понимает вызвали его с параметром или нет:

def repeat(_func=None, *, n=5):
    def _repeat(f):
        @wraps(f)
        def inner(*args, **kwargs):
            for _ in range(n):
                f(*args, **kwargs)
        return inner

    if _func is None:
        # вызов с параметрами как раньше
        return _repeat
    else:
        # вызов без параметра - сделаем доп. вызов сами
        return _repeat(_func)

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

# уже нельзя
@repeat(10)

# нужно или
@repeat(n=10)
# или
@repeat

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

🤩 Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway! 👈

Перечисления (Enum)

В Python нет специального синтаксиса для перечислений, зато есть модуль enum и класс Enum в нем, от которого можно отнаследоваться для создания собственного перечисления:

from enum import Enum
class Color(Enum):
    RED = 1
    GREEN = 2
    BLUE = 3

Задавать переменные этого типа можно несколькими способами:

c = Color(2)     # по значению
c = Color['RED'] # по строковому имени
c = Color.RED    # по члену класса

Значения из Enum человеко-читаемы при печати:

>>> print(Color.RED)
Color.RED

А также:

>>> Color.RED.name
'RED'
>>> Color.RED.value
1

Для сравнения эквивалентности используют оператор is (хотя == и != тоже работают):

if c is Color.RED:
    print('Red!')
if c is not Color.BLUE:
    print('Not blue!')

Для нескольких значений можно использовать in:

if c in (Color.BLUE, Color.GREEN):
    print('No red at all!')

Если неохота задавать значение самостоятельно, можно делать это автоматически:

from enum import Enum, auto
class Numbers(Enum):
    ONE = auto()
    TWO = auto()
    THREE = auto()
    FOUR = auto()

Члены перечислений хэшируемы и могут быть ключами словаря:

apples = {}
apples[Color.RED] = 'sweet'
apples[Color.GREEN] = 'sour'
>>> apples
{<Color.RED: 1>: 'sweet', <Color.GREEN: 2>: 'sour'}

Кратко создать перечислимый тип можно в функциональном стиле:

from enum import Enum
Animal = Enum('Animal', 'ANT BEE CAT DOG')

Семантика такого определения напоминает namedtuple. Первый аргумент – название перечисления, а второй – строка, где через пробел указаны названия вариантов. Пользоваться таким Enum можно также, как и заданным, через класс (см. выше), единственное, что могут быть проблемки с pickle

Допускается множество способов определить имен и значений вариантов перечисления: в строке через пробел или запятую, списком, списком кортежей имя-значение, словарем:

Animal = Enum('Animal', 'ANT, BEE, CAT, DOG')
Direction = Enum('Direction', ['NORTH', 'SOUTH', 'WEST', 'EAST'])
Color = Enum('Color', [('CYAN', 4), ('MAGENTA', 5), ('YELLOW', 6)])
Mood = Enum('Mood', {'HAPPY': ':-)', 'SAD': ':-('})

P.S. К сожалению, не все современные IDE понимают такое определение Enum, даже последний PyCharm ругается на аргументы и не активирует авто-дополнение по вариантам. Надеюсь, в будущем ситуация изменится в лучшую сторону.

🧙 Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈