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

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

>>> 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 раз при сохранении приемлемой скорости иногда может вам пригодиться.

#пакетик

Субботний пакет

Репозиторий питонячих пакетов (PyPI) включает аж 300 тысяч проектов. Среди них есть прикладные (requests) и инфраструктурные (pip), полезные (redis) и не очень (insultgenerator). Есть большие и маленькие, надежные и бажные, набирающие обороты и давно заброшенные. Всякие есть.

Я подумал, что было бы неплохо писать об одном из них раз в неделю, по субботам — в рубрике #пакетик. Так что если вы автор какого-нибудь классного пакета — дайте знать в личку (@nalgeon). Может, одна из суббот станет вашей ツ

Естественная сортировка

Мой сегодняшний выбор — пакет Сета Мортона natsort, который сортирует строки привычным для человека образом.

Допустим, у нас есть список важных гостей. Он в легком беспорядке:

data = [
  "4 - Дуглас",
  "2 - Клер",
  "11 - Зоя",
  "1 - Френк",
  "31 - Питер",
]

Отсортируем:

>>> sorted(data)
['1 - Френк', '11 - Зоя', '2 - Клер', '31 - Питер', '4 - Дуглас']

Порядка не прибавилось ツ А вот как будет с natsort:

>>> import natsort
>>> natsort.natsorted(data)
['1 - Френк', '2 - Клер', '4 - Дуглас', '11 - Зоя', '31 - Питер']

Другое дело!

#пакетик

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

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

Поэтому Дэн Бэйдер сделал 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)

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

#пакетик

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

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

Поможет bounter — это счетчик, который предоставляет схожий интерфейс, но внутри построен на вероятностных структурах данных. За счет этого он занимает в 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+

#пакетик

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

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

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

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

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.

А я вот отказался от него в пользу замечательного httpx от Тома Кристи. Синхронный и асинхронный интерфейсы, поддержка 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 друга вылетели в Копенгаген'

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

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

#пакетик