Быстро найти элемент коллекции

Френк решил открыть магазин диковинок. Прайс-лист огромный, приведу только несколько позиций:

from collections import namedtuple
Product = namedtuple("Product", ("price", "name"))

products = [
  Product(1500, "живой багет"),
  Product(3300, "мельница для сыра"),
  Product(6500, "костюм картошки"),
  Product(9900, "беспилотная сова"),
]

Магазин открылся, торговля идёт бойко, но есть проблемка. Покупатели донимают вопросом «у меня есть X рублей, какую самую дорогую дичь я могу купить за эту сумму?».

Френк очень плохо считает (неудивительно для голубя), поэтому требуется наша помощь. Давайте сначала решим «в лоб»:

def suggest(max_price):
  best_product = Product(0, None)
  for product in products:
    if product.price > max_price:
      continue
    if product.price > best_product.price:
      best_product = product
  if best_product.name is None:
    return None
  return best_product

>>> suggest(5000)
Product(price=3300, name='мельница для сыра')

Работает как часы! Только Френк жалуется, что suggest() что-то долго думает (прайс-лист огромный, помните?). Это неудивительно, мы ведь каждый раз перебираем все товары — сложность алгоритма O(n)

Надо бы отсортировать товары по цене и использовать алгоритм бинарного поиска, который работает за O(log n). Правда, не слишком греет перспектива реализации алгоритма — Френк требует сделать всё сию же секунду.

Нам поможет модуль bisect стандартной библиотеки:

import bisect

prices = sorted(p.price for p in products)

def suggest(max_price):
  best_index = bisect.bisect(prices, max_price)
  if best_index == 0:
    return None
  return products[best_index - 1]

>>> suggest(5000)
Product(price=3300, name='мельница для сыра')

Работает так:

— Создали отсортированный список цен.
— Покупатель принёс 5000₽ денег.
— bisect.bisect() определил, на какую позицию списка можно вставить 5000, чтобы список остался отсортированным (третья позиция, между 3300 и 6500).
— Элемент слева от этой позиции и есть интересующий нас товар («мельница» за 3300).

Френк доволен.

#stdlib

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

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

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

— Складывать приходящие числа в неупорядоченную кучу, отсортировать в конце.
— Постоянно поддерживать отсортированный список (с помощью 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).

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

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

#задачка

C — не обязательно быстро

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

> Мне кажется, тут не совсем корректное сравнение. sorted оптимизированная и написана на С, в то время как insort — просто питоновская функция. Она гоняет питоновские структурки и при любом раскладе будет работать медленно.

Это вообще популярная точка зрения, что если что-то написано на «быстром» C, то оно уж всяко будет быстрее, чем написанное на «медленном» Python.

Конечно же, это не так. Алгоритмы отличаются асимптотической сложностью — в нашем примере было O(n logn) против O(n²). В такой ситуации O(n logn) будет всегда быстрее для достаточно большого n, даже если написать его на джаваскрипте и интерпретировать встроенной в Windows js-машиной, а O(n²) написать на самом быстром в мире C.

Другое дело, что оговорка «для достаточно большого n» может оказаться решающей. Бывает, что асимптотически более быстрый алгоритм начинает выигрывать, скажем, при n > 10 млрд — а у вас в программе всегда n < 1 млн. Именно поэтому стоит реализовать и сравнить в действии оба алгоритма, если нет 100% уверенности.

А ещё бывает, что при одинаковой асимптотической сложности один алгоритм в 5 раз быстрее другого — потому что она такие мелочи игнорирует. И тут тоже без тестирования никуда.

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

P.S. Модуль bisect на самом деле реализован на C. Если интересно, как выглядит «сишная» часть питона, посмотрите — это один из самых простых модулей.

#код

Очень странные модули

Когда-то создатели питона считали, что в стандартную библиотеку надо запихнуть вообще всё. В результате там до сих пор живут довольно экзотичные (кхм) модули. Вот некоторые из них, в порядке нарастания безумия:

array — типизированные массивы чисел (почувствуйте себя С-программистом).

curses — создание «ASCII-арт» интерфейсов под линукс (серьёзно?).

reprlib — объектный интерфейс к repr (что вообще происходит).

formatter — мега-извратный способ работы с текстом (ммм, форматирование, его же так мало в питоне).

msilib — создание установочных MSI-пакетов под винду (фууу).

macpath — работа с путями файловой системы в Mac OS 9 (поздравим её, в этом году 20 лет исполняется).

chunk — поддержка аудиоформата времён компьютеров Commodore и Amiga (40 лет назад! спасибо, что живой).

Надеюсь, вам никогда не придётся с ними столкнуться ツ

#stdlib

Перечислить элементы коллекции с порядковыми номерами

Одна уважаемая компания заказала вам разработку теста для соискателей на позицию «дизайнер продукта». Есть список вопросов с вариантами ответа:

survey = {
  "Чем известен Джони Айв?": [
    "Придумал анимированные эмодзи",
    "Снялся в фильме про белую комнату",
    "Изобрёл мышку с зарядкой в пузе",
  ],
  "Почему важно надувать щёки?": [ ... ],
  "Сколько у вас статей про дизайн-системы?": [ ... ],
}

Вы написали код, который показывает на экране каждый вопрос с вариантами ответа:

for question, answers in survey.items():
  print(question)
  print_answers(answers)

Но есть нюанс — варианты должны быть пронумерованы. Как бы это сделать?

def print_answers(answers):
  i = 1
  for answer in answers:
    print(f"{i}: {answer}")
    i += 1

Чем известен Джони Айв?
1: Придумал анимированные эмодзи
2: Снялся в фильме про белую комнату
3: Изобрёл мышку с зарядкой в пузе

Да, но нет. Очень часто, когда видите в коде i = .. и затем i += 1 — это красный флаг. Лучше так:

def print_answers(answers):
  for idx, answer in enumerate(answers, start=1):
    print(f"{idx}: {answer}")

enumerate возвращает итератор, который при каждом обращении выдаёт пару из счётчика и соответствующего ему элемента последовательности. А аргумент start указывает, с какого числа стартовать счётчик (по умолчанию — с нуля).

P.S. Если это для вас слишком просто, представьте себя сумасшедшим любителем однострочников и попробуйте расшифровать такое:

deque(map(print, map(lambda item: f"{item[0]}: {item[1]}", enumerate(answers, start=1))), maxlen=0)

#stdlib

Проверить, что выполняется хотя бы одно условие

Френк решил обзавестить новым домом. Он весьма требовательная скотинка, поэтому подготовил набор критериев для оценки жилья:

def no_cats(place):
  # они ВЕЗДЕ
  return False

def close_to_subway(place):
  # Френк знает только одно метро
  return "Третьяковск" in place

def lots_of_garbage(place):
  # ммм, очень много
  return "Макдак" in place

Допустим, место подходит, если хотя бы одно условие выполняется. При этом, конечно, мы хотим проверять не все условия, а до первого сработавшего:

checks = [no_cats, close_to_subway, lots_of_garbage]

def check_place(place):
  for check in checks:
    if check(place):
      return True
  return False

place = "Макдак на Третьяковской"

>>> check_place(place)
True

Но до чего же унылая получилась эта check_place(), верно? Ну её к чёрту, намного лучше так:

>>> any(check(place) for check in checks)
True

А что, если Френк согласен заселиться только туда, где выполняются все условия? Думаю, вы уже поняли:

>>> all(check(place) for check in checks)
False

Есть нюанс. Допустим, Френк в отчаянии отказался от всех проверок. Как поведут себя any() и all()? Возможно, не так, как вы ожидали:

checks = []

>>> any(check(place) for check in checks)
False

>>> all(check(place) for check in checks)
True

P.S. Сможете сделать то же самое на map() и без лямбд?

#stdlib

Создать словарь по списку ключей

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

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

Робот постоянно учится новым полезным активностям, так что набор дел не фиксированный. Он хранится в списке:

actions = ["махать флагом", "чесать котов", "смешить детей", "рвать шаблоны"]

Как бы из этого списка сделать счётчик? Так не надо, конечно:

from collections import Counter

counter = Counter()
for action in actions:
  counter[action] = 0

>>> counter

Counter({
  'махать флагом': 0,
  'чесать котов': 0,
  'смешить детей': 0,
  'рвать шаблоны': 0})

Намного роднее воспользоваться dictionary comprehension (простите, что на англ — непереводимая игра слов):

counter = Counter({action: 0 for action in actions})

Или малоизвестным методом dict.fromkeys():

counter = Counter(dict.fromkeys(actions, 0))

Первый аргумент — список ключей, второй — умолчательное значение. Удобно, а?

#stdlib

💣 Автоматизация задач в Python-проекте

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

— проверить код линтерами,
— прогнать тесты с замером покрытия,
— запустить в докере,
...

JS-разработчикам повезло: у них в package.json есть специальная секция noscripts для таких штук. Для Питона ничего подобного не предусмотрено. Но есть отличное решение:

https://antonz.ru/makefile/

#код

📦 Как сделать классный Python-пакет

Раньше я думал, что создание пакетов в питоне — жуткая головная боль. Никогда с этим не связывался.

Оказывается, ситуация давно изменилась, и делать библиотеки стало легко и приятно. Буквально так:

flit init
...
flit publish

Попробуйте: https://antonz.ru/packaging/

P.S. Если у вас есть собственная библиотека, которой не стыдно поделиться — присылайте в личку. Про самые интересные напишу отдельно.

#код

Python и Go

Странным образом многие питон-разработчики рано или поздно приходят к языку Go. Кто-то переключается на него полностью, кто-то использует для отдельных задач. Так или иначе, Go и Python образуют пару максимально непохожих, но часто упоминаемых вместе языков.

Go прост, можно даже сказать — примитивен. При этом код на нём читать заметно тяжелее, чем на питоне. Но только пока не начнёте писать асинхронщину — тут ситуация переворачивается.

Go беден библиотеками (как стандартной, так и third-party). Но это помогает использовать его только там, где уместно.

Go быстр. Правда быстр. И, благодаря компиляции в машинный код, очень компактен (как вам докер-образ размером в 10 Мб?).

А ещё Go мало кого оставляет равнодушным: его либо любят, либо ненавидят. Мы решили исследовать этот феномен, взяли по человеку от каждого лагеря и завели канал, где перемоем Go все косточки.

Подписывайтесь, если Go вам интересен: @thank_go

Отрезать строке голову и хвост

В Python 3.9 строке добавили методы, которые удаляют префикс и суффикс:

>>> "Френк и семечки".removeprefix("Френк и ")
'семечки'

>>> "Френк и семечки".removesuffix(" и семечки")
'Френк'

На стадии обсуждения PEP разгорелся нешуточный спор. Сначала автор предложил названия cutprefix() и cutsuffix(), но сообществу не понравился глагол cut. Альтернативой предложили strip, trim и remove, долго и мучительно обсуждали, наконец остановились на remove.

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

До сих пор в языке remove использовался в смысле «удалить элемент коллекции»:

deque.remove()
array.remove()
os.remove()

А в строках для обрезки части — strip:

str.strip()
str.lstrip()
str.rstrip()

Да, само по себе strip — не слишком удачное название (в других языках чаще используют trim). Но оно давно прижилось, так что логично его и использовать дальше.

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

#stdlib

Прочитать произвольную строку из файла

Предположим, вы решили разработать продвинутого саппорт-бота. В нём будет машин лёнинга до самых краёв, так что человек почти не понадобится. К сожалению, неотложные дела отвлекли ваше внимание, и вы делегировали задачу Френку.

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

# answers.txt
Перезагрузите ваше устройство, пожалуйста
Проверили, проблема на вашей стороне
Спасибо, займёмся этим позже
Наши технические возможности исчерпаны

Простой, надёжный алгоритм. Осталось воплотить его в питоне. Здесь Френку поможет linecache.getline():

import linecache
import random

def get_answer():
  line_num = random.randint(1, 4)
  answer = linecache.getline("answers.txt", line_num)
  return answer.strip()

>>> get_answer()
'Проверили, проблема на вашей стороне'

Ничего себе! Это едва ли не короче, чем hello world. К тому же, функция getline() кеширует все строчки файла в списке, так что следующие вызовы get_answer() отработают моментально.

Бот готов, Френк возвращается к своим семечкам.

#stdlib

Зачем читать исходники

Я как-то писал, что в документацию питона добавили ссылки на исходники модулей. Читать их не только увлекательно, но и полезно.

Помните linecache.getline() из прошлого поста, который выбирает строчку файла по номеру?

>>> linecache.getline("answers.txt", 3)
'Проверили, проблема на вашей стороне'

Модуль не случайно называется linecache. При первом обращении к файлу linecache записывает его содержимое в кеш (в глобальную переменную cache). Именно из этого кеша getline() и выбирает строку по номеру. Благодаря кешу второй и последующие вызовы уже не читают файл и отрабатывают моментально.

# lines - список строк файла
cache[filename] = size, mtime, lines, fullname

И есть в модуле функция linecache.checkcache(). Вот её документация:

> Check the cache for validity. Use this function if files in the cache may have changed on disk, and you require the updated version.

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

def checkcache(filename=None):
  # проверка, обновился ли файл
  # по сравнению с кешем
  # и если обновился, то:
  cache.pop(filename)

Оказывается, checkcache() не актуализирует, а очищает кеш! Из-за этого следующий вызов getline() отработает заметно медленнее: придётся заново начитывать весь файл.

Конкретно в случае с linecache это вряд ли станет большой проблемой, но представьте, какой был бы неприятный сюрприз, если бы речь шла о продакшен-кеше вашего приложения ツ

В любой непонятной ситуации читай исходники, как говорил Урбан Мюллер, автор языка Brainfuck.

#код

Ищем фильмы, книги и подкасты с помощью Python

У Apple есть API поиска по iTunes Store и другим каталогам. Очень простое, но мало кто за пределами экосистемы айос-разработчиков про него знает. Поэтому решил написать о нём — конечно, с примерами на питоне:

import requests

def search(term, media):
  url = "https://itunes.apple.com/search"
  payload = {"term": term, "media": media}
  response = requests.get(url, params=payload)
  response.raise_for_status()
  results = response.json().get("results", [])
  return results

Статья на хабре:
https://habr.com/ru/post/509192/

#код

Проверить, входит ли элемент в коллекцию

Предположим, вы ведёте реестр монет. В нём записаны монетки всех времён, стран и достоинств. На вашем сайте любой может проверить, есть ли та или иная монета в реестре, и если нет — добавить её.

Как проверить, есть ли монета в реестре?

Можно так:

coins = ["1 aud", "5 ars", "1 byn", "10 ghs"]

def has(coin):
    return coin in coins

>>> has("1 byn")
True
>>> has("20 cny")
False

Конечно, так делать нехорошо. Операция element in list последовательно проверяет каждый элемент списка, то есть её сложность O(n). Незаметно на маленьких списках, но если у вас в реестре 1 млн монет, а с сайта приходит по тысяче запросов в секунду — начнёт тормозить:

>>> import random
>>> import timeit
>>> list_ = [random.random() for _ in range(1_000_000)]
>>> num = random.random()
>>> timeit.timeit(lambda: num in list_, number=1000)
9.66

10 секунд на проверку тысячи элементов, пффф. Решение — использовать множества:

>>> set_ = set(random.random() for _ in range(1_000_000))
>>> num = random.random()
>>> timeit.timeit(lambda: num in set_, number=1000)
0.00018

Операция element in set выполняется за O(1). На множестве проверка отработала примерно в 50000 раз быстрее, чем на списке.

А что с памятью? Проверим:

from pympler import asizeof

def size_mb(obj):
    return round(asizeof.asizeof(obj) / 1024**2)

>>> size_mb(list_)
31
>>> size_mb(set_)
55

Множество оказалось в 2 раза тяжелее списка. Ничего, для миллиона монеток хватит. Но что делать, если в коллекции один миллиард объектов, тоже всё в память запихивать? Есть и другие варианты, о них в следующий раз.

#stdlib

Проверить, есть ли элемент в огромной коллекции

Как мы выяснили в прошлый раз, проверка на вхождение элемента в множество выполняется моментально, но занимает прилично места:

>>> set_ = set(str(random.random()) for _ in range(1_000_000))
>>> num = str(random.random())
>>> timeit.timeit(lambda: num in set_, number=1000)
0.000160

>>> size_mb(set_)
101

Для множества на 1 млн элементов получилось 160 микросекунд на 1000 проверок, 101 Мб в памяти.

Что если элементов будет 1 млрд? Это уже около 100 Гб, не хотелось бы держать их в памяти. Устроил бы компромиссный вариант, который работает медленнее, но занимает меньше места.

И он существует! Это фильтр Блума — специальная вероятностная структура данных. Она отвечает на вопрос «есть ли элемент в коллекции?» одним из двух вариантов:

— точно нет;
— возможно есть.

Вот как это работает:

>>> from bloom_filter import BloomFilter
>>> bloom = BloomFilter(max_elements=1_000_000, error_rate=0.001)
>>> for el in set_:
...   bloom.add(el)
>>> size_mb(bloom)
3

Фильтр Блума на 1 млн элементов с вероятностью ложно-положительного ответа 0.1% занимает всего 3 Мб (вместо 100 Мб «честного» множества). А что со скоростью?

>>> timeit.timeit(lambda: num in bloom, number=1000)
0.015

15 миллисекунд — это в 100 раз медленнее, чем проверка по множеству, но всё ещё достаточно быстро (например, в 600 раз быстрее проверки по списку).

Проверим на 1 млрд:

>>> bloom = BloomFilter(max_elements=1_000_000_000, error_rate=0.001)
>>> size_mb(bloom)
3428

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

#пакетик

Грамотно работать с любым диапазоном

Все знают, что range() в питоне используется, когда нужно что-то сделать сколько-то раз:

>>> for i in range(3, 0, -1):
...   print(i)

3
2
1

Но не все знают, что range — это коллекция (что? да!), вполне себе полноценная:

>>> seq = range(10, 100)
>>> len(seq)
90
>>> 52 in seq
True
>>> seq[10]
20

И даже так:

>>> max(seq)
99
>>> seq.index(31)
21
>>> seq.count(42)
1

И так тоже:

>>> s1 = range(0, 10, 3)
>>> s2 = range(0, 11, 3)
>>> s1 == s2
True

При этом range, в отличие от всех прочих коллекций, занимает мизерное место в памяти (48 байт), вне зависимости от того, сколько элементов в него попадают. Это потому, что хранит он только 3 атрибута: start, stop, step

>>>from pympler import asizeof
>>> seq = range(0, 100)
>>> asizeof.asizeof(seq)
48
>>> seq = range(0, 100_000)
>>> asizeof.asizeof(seq)
48
>>> seq = range(0, 100_000_000)
>>> asizeof.asizeof(seq)
48

А время выполнения операций при этом как в обычном списке: len(), in, [idx] — за O(1).

Ну разве он не чудо?

#stdlib

Скорость работы оператора in range

После вчерашней заметки некоторые подписчики справедливо заметили, что сложность проверки «element in list» составляет O(n), а не O(1). А я пишу, что для range она O(1). Да, вы молодцы, так и есть ツ

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

Допустим, есть выражение x in range(start, stop, step). Для положительного step можно обойтись без перебора всех элементов, вот так:

def contains(range_, x):
  if x < range_.start:
    return False
  if x >= range_.stop:
    return False
  return (x - range_.start) % range_.step == 0

>>> r = range(1000, 10000, 3)
>>> contains(r, 2068)
True
>>> contains(r, 2070)
False

Проверили границы, посчитали остаток от деления, бумс, готово. Для отрицательного step работает аналогично.

Так что in range действительно выполняется за O(1), в отличие от in list.

#stdlib