Метка: python

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

Сегодня простая, но важная тема. Алгоритм сортировки пузырьком, его проходят на курсах, его часто спрашивают на собеседованиях. Сортировка — это процесс выстраивания массива или списка по возрастанию или убыванию. На примере чисел: [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 👈 

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 👈 

Декораторы в Python

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

@app.route('/')
def index():
    return "Hello, World!"

Разберемся, что такое декоратор, и как он работает. Этот вопрос часто спрашивают на собеседованиях.

Декоратор – это функция, которая принимает как аргумент другую функцию*. Цель декоратора – расширить функциональность переданной ему функции без непосредственного изменения кода самой функции. Вот и все!

* Примечание: декорировать можно и класс, но об этом расскажу потом!

В Python функция – тоже объект, и ее можно передавать как аргумент, возвращать из другой функции, ей также можно назначать атрибуты.

Символ собачка (@) – всего лишь синтаксический сахар:

@decorator
def foo():
    ...

# эквивалентно:

def foo():
    ...
foo = decorator(foo)