Планировщик задач

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

Поэтому Дэн Бэйдер сделал schedule — «планировщик для людей». Смотрите, какой милый:

import schedule
import time

def job():
 print("I'm working...")

schedule.every().hour.do(job)
schedule.every(5).to(10).minutes.do(job)
schedule.every().day.at("10:30").do(job)

while True:
 schedule.run_pending()
 time.sleep(1)

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

#пакетик

Задачка: неэффективный планировщик

Субботний пакет-планировщик вскрыл интересное искажение у некоторых подписчиков. Давайте проверим, есть ли оно у вас ツ

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

def job():
  print("Executing job")

И есть планировщик. Он ужасно плохо написан, и тупит 0.2 секунды при каждом запуске:

class Scheduler:
  def run_pending(self):
    time.sleep(0.2)
    print(dt.datetime.now())
    // запускает job(),
    // если наступила новая минута

Мы гоняем планировщик в бесконечном цикле каждую секунду:

sched = Scheduler()

while True:
  sched.run_pending()
  time.sleep(1)

И — о ужас — с каждым запуском планировщик все сильнее запаздывает:

2021-05-24 15:19:01.9
2021-05-24 15:19:03.1
2021-05-24 15:19:04.3
2021-05-24 15:19:05.6
2021-05-24 15:19:06.8
2021-05-24 15:19:08.0
2021-05-24 15:19:09.2
2021-05-24 15:19:10.4

Вопрос: насколько сильно будет опаздывать запуск задачи job()? Напомню, она должна запускаться каждую минуту.

Опрос следует.

#задачка

Поэлементно сравнить коллекции

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

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

Допустим, мы ведем учет посетителей:

jan = ["Питер", "Клер", "Френк"]
feb = ["Френк", "Зоя", "Дуглас"]
mar = ["Клер", "Питер", "Зоя"]

И хотим узнать, кто приходил в январе и феврале. Нет ни малейшего желания писать вложенный цикл с перебором jan и feb. Намного приятнее (и быстрее) использовать множества.

jan = {"Питер", "Клер", "Френк"}
feb = {"Френк", "Зоя", "Дуглас"}
mar = {"Клер", "Питер", "Зоя"}

Были в январе и феврале:

>>> jan & feb
{'Френк'}

В январе или марте:

>>> jan | mar
{'Питер', 'Клер', 'Зоя', 'Френк'}

В феврале, но не в марте:

>>> feb - mar
{'Френк', 'Дуглас'}

В январе или феврале, но не в оба месяца:

>>> jan ^ feb
{'Питер', 'Клер', 'Зоя', 'Дуглас'}

Все эти операции выполняются за линейное время O(n) вместо квадратичного O(n²), как было бы на списках.

Кроме обычных множеств бывают замороженные (их нельзя менять):

>>> visitors = frozenset().union(jan, feb, mar)
>>> visitors
frozenset({'Питер', 'Клер', 'Зоя', 'Френк', 'Дуглас'})

Множество можно слепить из любого iterable-типа. Например, из строки:

>>> frozenset('abcde')
frozenset({'b', 'd', 'e', 'c', 'a'})

Или даже из диапазона:

>>> set(range(1, 10))
{1, 2, 3, 4, 5, 6, 7, 8, 9}

В общем, полезная штука.

#stdlib

Счетчик для огромных коллекций

В стандартной библиотеке есть класс Counter. Он отлично подходит, чтобы считать количество объектов разных типов. Но что делать, если объектов миллиарды, и счетчик просто не помещается в оперативную память?

Поможет bounterbounter — это счетчик, который предоставляет схожий интерфейс, но внутри построен на вероятностных структурах данных. За счет этого он занимает в 30–250 раз меньше памяти, но может (слегка) привирать.

from bounter import bounter
counts = bounter(size_mb=128)
counts.update(["a", "b", "c", "a", "b"])

>>> counts.total()
5

>>> counts["a"]
2

Ноль зависимостей, питон 3.3+

#пакетик

Главный критерий хорошего кода

Хороший код — понятный и непрожорливый до ресурсов. Давайте поговорим об этом.

Время на понимание

Главный критерий хорошего кода — это время T, которое требуется не-автору, чтобы разобраться в коде. Причем разобраться не на уровне «вроде понятно», а достаточно хорошо, чтобы внести изменения и ничего не сломать.

Чем меньше T, тем лучше код.

Допустим, Нина и Витя реализовали одну и ту же фичу, а вы хотите ее доработать. Если разберетесь в коде Нины за 10 минут, а в коде Вити за 30 минут — код Нины лучше. Неважно, насколько у Вити чистая архитектура, функциональный подход, современный фреймворк и всякое такое.

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

Напрямую T не очень-то померяешь, поэтому часто отслеживают вторичные метрики, которые влияют на T:

— соответствие код-стайлу (black для питона),
— «запашки» в коде (pylint, flake8),
— цикломатическую сложность (mccabe),
— зависимости между модулями (import-linter).

Плюс код-ревью.

Количество ресурсов

Второй критерий хорошего кода — количество ресурсов R, которое он потребляет (времени, процессора, памяти, диска). Чем меньше R, тем лучше код.

Если Нина и Витя реализовали фичу с одинаковым T, но код Нины работает за O(n), а код Вити за O(n²) (при одинаковом потреблении прочих ресурсов) — код Нины лучше.

Насчет ситуации «пожертвовать понятностью ради скорости». Для каждой задачи есть порог потребления ресурсов R0, в который должно уложиться решение. Если R < R0, не надо ухудшать T ради дальнейшего сокращения R.

Если некритичный сервис обрабатывает запрос за 50мс — не надо переписывать его с питона на C, чтобы сократить время до 5мс. И так достаточно быстро.

Иногда, если ресурсы ограничены, или исходные данные большие — не получается достичь R < R0 без ухудшения T. Тогда действительно приходится жертвовать понятностью. Но:

1) Это последний вариант, когда все прочие уже испробованы.
2) Участки кода, где T↑ ради R↓, должны быть хорошо изолированы.
3) Таких участков должно быть мало.
4) Они должны быть подробно документированы.

Итого

Мнемоника хорошего кода:

T↓ R<R0

Оптимизируйте T, следите за R. Коллеги скажут вам спасибо.

#код

Универсальные оповещения

Есть куча способов отправлять уведомления — от проверенного SMTP и удобного Telegram до смс и специальных приложений для мобилок вроде Pushover.

Обычно для этого используют 3rd-party библиотеку соответствующего провайдера. Но есть более удобный способ — пакет notifiersnotifiers от Ора Карми. Он предоставляет простой универсальный интерфейс для отправки сообщений через любой сервис.

Например, через телеграм:

import notifiers

token = "bot_token"
chat_id = 1234
tg = notifiers.get_notifier("telegram")
tg.notify(message="Привет!", token=token, chat_id=chat_id)

Поддерживается аж 16 провайдеров, а интерфейс один — метод .notify(). И никаких дополнительных 3rd-party библиотек. Удобно!

Питон 3.6+

#пакетик

Современный HTTP-клиент

Мало у какого языка такая нажористая стандартная библиотека, как у питона. Но все равно для работы с HTTP люди пользуются сторонним пакетом requests.

А я вот отказался от него в пользу замечательного httpxhttpx от Тома Кристи. Синхронный и асинхронный интерфейсы, поддержка wsgi/asgi, плюс все фичи requests — и совместимость с ним!

Можно заменить requests → httpx, и все продолжит работать:

>>> import httpx
>>> r = httpx.get("http://httpbingo.org/json")

>>> r.status_code
200

>>> r.headers["content-type"]
'application/json; encoding=utf-8'

>>> r.json()["slideshow"]["title"]
'Sample Slide Show'

Питон 3.6+

#пакетик

Разбор текста по шаблону

Все знают, как в питоне форматировать текст по шаблону:

import datetime as dt

date = dt.date(2020, 11, 20)
who = "Френк"
count = 42

tmpl = "{:%Y-%m-%d}: {} и его {:d} друга вылетели в Копенгаген"

>>> tmpl.format(date, who, count)
'2020-11-20: Френк и его 42 друга вылетели в Копенгаген'

А благодаря библиотеке parseparse от Ричарда Джонса, с такой же легкостью можно разбирать текст обратно по переменным:

import parse

tmpl = "{:ti}: {} и его {:d} друга вылетели в Копенгаген"
txt = "2020-11-20: Френк и его 42 друга вылетели в Копенгаген"

>>> date, who, count = parse.parse(tmpl, txt)
>>> date
datetime.datetime(2020, 11, 20, 0, 0)
>>> who
'Френк'
>>> count
42

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

Внутри работает на регулярках. Ноль зависимостей, питон 2 и 3

#пакетик

День списков

Давайте проведем тематический день! (если честно, то несколько)

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

Все знают, как работать со списком в питоне:

>>> guests = ["Френк", "Клер", "Зоя"]
>>> guests[1]
'Клер'

Наверняка вы знаете, что выборка элемента по индексу — guests[idx] — отработает очень быстро даже на списке из миллиона элементов. Более точно, выборка по индексу работает за константное время O(1) — то есть не зависит от количества элементов в списке.

А знаете, за счет чего так быстро работает? Как внутри устроено? Опрос следует.

Список = массив?

В основе питонячего списка лежит массив. Массив — это набор элементов (1) одинакового размера и (2) расположенных в памяти подряд друг за другом, без пропусков.

Раз элементы одинаковые и идут подряд, получить элемент массива по индексу несложно — достаточно знать адрес самого первого элемента («головы» массива).

Допустим, голова находится по адресу 0x00001234, а каждый элемент занимает 8 байт. Тогда элемент с индексом idx находится по адресу 0x00001234 + idx*8 (картинка прилагается).

Поскольку операция «получить значение по адресу» выполняется за константное время, то и выборка из массива по индексу выполняется за O(1).

Грубо говоря, питонячий список именно так и устроен. Он хранит указатель на голову массива и количество элементов в массиве. Количество хранится отдельно, чтобы функция len() тоже отрабатывала за O(1), а не считала каждый раз фактическое количество элементов списка.

Все хорошо, но есть пара проблем:

— все элементы массива одного размера, а список умеет хранить разные (true/false, числа, строки разной длины);
— массив имеет фиксированную длину, а в список можно добавить сколько угодно элементов.

Чуть позже посмотрим, как их решить.

Ну очень примитивный список

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

Но кое-что можно сделать:

class OhMyList:
  def __init__(self):
    self.length = 0
    self.capacity = 8
    self.array = (self.capacity * ctypes.py_object)()

  def append(self, item):
    self.array[self.length] = item
    self.length += 1

  def __len__(self):
    return self.length

  def __getitem__(self, idx):
    return self.array[idx]

Наш самописный список имеет фиксированную вместимость (capacity = 8 элементов) и хранит элементы в массиве array.

Модуль ctypes дает доступ к сишным структурам, на которых построена стандартная библиотека. В даннам случае мы используем его, чтобы создать массив размером в capacity элементов.

Попробуйте поработать с OhMyList в песочнице.

А завтра продолжим ツ

Список = массив указателей

Итак, список моментально выбирает элемент по индексу, потому что внутри у него массив. А массив такой быстрый, потому что все элементы у него одинакового размера.

Но при этом в списке элементы могут быть очень разные:

guests = ["Френк", "Клер", "Зоя", True, 42]

Чтобы решить эту задачку, придумали хранить в массиве не сами значения, а указатели на них. Элемент массива — адрес в памяти, а если обратиться по адресу — получишь настоящее значение (картинка прилагается).

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

1. Получить адрес из элемента массива.
2. Получить значение по адресу.

Но это все еще константное время O(1).

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

Список = динамический массив

Если в массиве под списком остались свободные места, то метод .append(item) выполнится за константное время — достаточно записать новое значение в свободную ячейку и увеличить счетчик элементов на 1:

def append(self, item):
  self.array[self.length] = item
  self.length += 1

Но что делать, если массив уже заполнен?

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

Примерно так:

def append(self, item):
  if self.length == self.capacity:
    self._resize(self.capacity*2)
  self.array[self.length] = item
  self.length += 1

def _resize(self, new_cap):
  new_arr = (new_cap * ctypes.py_object)()
  for idx in range(self.length):
    new_arr[idx] = self.array[idx]
  self.array = new_arr
  self.capacity = new_cap

_resize() — затратная операция, так что новый массив создают с запасом. В примере выше новый массив в два раза больше старого, а в питоне используют более скромный коэффициент — примерно 1.12.

Если удалить из списка больше половины элементов через .pop(), то питон его скукожит — выделит новый массив поменьше и перенесет элементы в него.

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

Когда место в старом массиве заканчивается, приходится создавать новый

Добавление элемента в конец списка

Выборка из списка по индексу работает за O(1) — с этим разобрались. Метод .append(item) тоже отрабатывает за O(1), пока не приходится расширять массив под списком. Но любое расширение массива — это операция O(n). Так за сколько же в итоге отрабатывает append()?

Оценивать отдельную операцию вставки было бы неправильно — как мы выяснили, она иногда выполняется за O(1), а иногда и за O(n). Поэтому используют амортизационный анализ — оценивают общее время, которое займет последовательность из K операций, затем делят его на K и получают амортизированное время одной операции.

Так вот. Не вдаваясь в подробности скажу, что амортизированное время для .append(item) получается константным — O(1). Так что вставка в конец списка работает очень быстро.

Итого, у списка есть такие гарантированно быстрые операции:

# O(1)
lst[idx]

# O(1)
len(lst)

# амортизированное O(1)
lst.append(item)
lst.pop()

P.S. Если интересно, как именно получается амортизированное O(1) — подробности в комментариях.

Список: итоги

Как мы выяснили, у списка работают за O(1):

— выборка по индексу lst[idx]
— запрос длины len(lst)
— добавление элемента в конец списка .append(item)
— удаление элемента из конца списка .pop()

Остальные операции — «медленные».

Вставка и удаление из произвольной позиции — .insert(idx, item) и .pop(idx) — работают за линейное время O(n), потому что сдвигают все элементы после целевого.

Поиск и удаление элемента по значению — item in lst, .index(item) и .remove(item) — работают за линейное время O(n), потому что перебирают все элементы.

Выборка среза из k элементов — lst[from:to] — работает за O(k).

Значит ли это, что «медленные» операции нельзя использовать? Конечно, нет. Если у вас список из 1000 элементов, разница между O(1) и O(n) для единичной операции незаметна.

С другой стороны, если вы миллион раз выполняете «медленную» операцию на списке из 1000 элементов — это уже заметно. Или если список из миллиона элементов — тоже.

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