Френк вчера так достал своей беспилотной совой, что я совсем забыл спросить у вас одну вещь.

Допустим, вы пишете программу, которой на вход последовательно, одно за другим, приходят числа. Ваша задача — накапливать их как-то, а потом, когда числа перестанут приходить — вернуть отсортированный список.

Как думаете, что будет работать быстрее:

— Складывать приходящие числа в неупорядоченную кучу, отсортировать в конце.
— Постоянно поддерживать отсортированный список (с помощью bisect), в конце просто вернуть его.

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

#задачка

Сортировать в конце или держать отсортированным?

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

Вопрос — что будет работать быстрее:

— Отсортировать список в конце.
— Постоянно держать отсортированным.

---

Ну что, давайте разбираться!

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

Мы знаем, что сортировка на n числах занимает O(n logn) операций. Это сложность варианта «сортировать в конце».

Мы также знаем, что один бинарный поиск занимает O(log n) операций. В варианте «поддерживать отсортированным» мы выполняем поиск n раз, значит итоговая сложность O(n logn).

Там O(n logn) и тут O(n logn) — значит, варианты равнозначные, расходимся.

На самом деле нет ツ Посмотрите на реализацию варианта «поддерживать отсортированным»:

def keep_sorted(generator):
  collection = []
  for number in generator:
    index = bisect.bisect(collection, number)
    collection.insert(index, number)
  return collection

Да, бинарный поиск выполняется за логарифмическое время. Но после него идёт вставка в массив — она занимает линейное время.

Таким образом, на каждое число алгоритм тратит O(n) операций, а на n чисел — O(n²). Это сильно медленнее, чем O(n logn).

Чтобы не быть голословным, я реализовал и сравнил в действии оба алгоритма. Не верьте на слово и попробуйте сами (смотреть на десктопе).

Итого, вариант «сортировать в конце» побеждает с большим отрывом.

#задачка

Задачка: сотрудникофикатор

Время для задачки! Допустим, вы основали модный HR-стартап, который подбирает идеальные коллективы сотрудников. Дело это нелёгкое, так что начали с простой эвристики:

> Любой коллектив идеален, пока в нём не появляется Френк

Подготовили интеллектуальный алгоритм, который предлагает сотрудника:

import random
names = ["Френк", "Клер", "Зоя", "Питер", "Лукас"]

def employee():
  name = random.choice(names)
  return name

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

>>> [name for name in employeficator()]
['Зоя', 'Зоя', 'Питер']
>>> [name for name in employeficator()]
['Лукас', 'Зоя', 'Питер']

Ваша задача — реализовать employeficator() максимально идиоматично.

Давайте я для затравки начну заведомо неудачным вариантом:

def employeficator():
  employees = []
  name = employee()
  while name != "Френк":
    employees.append(name)
    name = employee()
  return employees

Ссылка на репл

Форкайте, реализуйте свой employeficator() и присылайте ссылку на форк мне → @nalgeon

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

#задачка

Решение: сотрудникофикатор

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

Для начала, что такое «идиоматично». Идиоматичный код использует «родные» конструкции языка и стандартной библиотеки, не нарушая при этом питонячий дзен (simple is better than complex, readability counts, вот это всё).

Месиво из вложенных циклов с break и continue вряд ли можно назвать идиоматичным. Точно также не будет идиоматичной «функциональная» колбаса из вызовов functools и itertools. Абсолютных критериев тут нет, но общий смысл, надеюсь, понятен.

Теперь к решению. Задача была с небольшим подвохом: искомый employeficator() уже есть в стандартной библиотеке. Больше того, не просто в стандартной библиотеке, а в самом её сердце, в built-in функциях! Вот он:

[name for name in iter(employee, "Френк")]

Да, это функция iter(). Обычно её вызывают с одним аргументом — коллекцией:

>>> seq = [1, 2, 3]
>>> it = iter(seq)
>>> next(it)
1

Но в варианте с двумя аргументами iter() работает иначе:

iter(callable, sentinel)

Первый аргумент — функция или что-нибудь вызываемое (callable), второй — контрольное значение (sentinel). Каждое обращение к итератору вызывает callable() и возвращает результат его выполнения. А как только callable() возвращает значение sentinel, итератор прекращает работу.

Это ровно то поведение, что требовалось в задаче — вызывать employee(), пока очередной вызов не вернёт "Френк".

Так что iter() здесь — идеальное решение. Поздравляю всех, кто его предложил! Есть и другие хорошие варианты, разберём их в следующий раз.

P.S. Некоторые участники решили, что коллектив обязательно должен состоять из 3 сотрудников или не может включать нескольких сотрудников с одинаковыми именами. Но таких ограничений в условиях не было. Вы сами усложнили себе задачу 🤷‍♀️

#задачка

А вот и полный разбор задачки о сотрудникофикаторе. Не обошлось без моржа: https://antonz.ru/iter-with-sentinel/

#задачка

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

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

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

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()? Напомню, она должна запускаться каждую минуту.

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

#задачка

Считаем котов на ютубе

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

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

Подготовим функцию для каждого шага:

def reader(filename):
  for line in open(filename):
    # video url
    yield line.strip()

def process(url):
  video_id = url.partition("=")[2]
  cat_count = count_cats(url)
  return Video(video_id, url, cat_count)

def writer(out):
  while True:
    video = yield
    line = f"{video.id},{video.cat_count}\n"
    out.write(line)

И объединим в единый алгоритм:

w = writer(sys.stdout)
w.send(None)
for url in reader("data/urls.txt"):
  video = process(url)
  w.send(video)

Функция count_cats() вызывает огромный мощный кластер, который принимает на входе URL, обрабатывает видео и считает в нем котов. Обработка одного ролика всегда занимает 1 сек, но сам кластер при этом загружен на 0.01%.

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

Что же делать? Опрос следует.

песочница

#задачка

Задачка: летающая свинья

Допустим, вы написали утилиту, которая отправляет что угодно в полет:

def launch(thing):
  thing.fly()

Ну то есть не прям все что угодно, а любую штуку с методом .fly(). Очень удобно: одной функцией запускаем и голубя Френка, и самолет, и даже Супермена:

class Frank:
  def fly(self):
    print("💩")

class Plane:
  def fly(self):
    print("Рейс задержан")

class Superman:
  def fly(self):
    print("ε===(っ≧ω≦)っ")

Вжух:

f = Frank()
launch(f)
# 💩

p = Plane()
launch(p)
# Рейс задержан

s = Superman()
launch(s)
# ε===(っ≧ω≦)っ

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

Работает, и ладно. Но иногда (особенно если программа разрастается) разработчику хочется добавить немного строгости. Дать понять, что параметр thing в launch() — это не любой объект, а обязательно летающая хреновина с методом fly(). Как лучше это сделать?

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

песочница

#задачка