Сегодня == сейчас
В каждом языке есть участки, которые не особо удались создателям. Для большинства языков, созданных до двухтысячных годов, камнем преткновения стала работа со временем.
Питон — не исключение. Возьмём функцию, которая сравнивает дату-время с точностью до минуты:
И сравним «сегодня» и «сейчас»:
Оказывается, это одно и то же ツ Метод
А что насчёт времени по UTC?
Неожиданно,
Если работать с датой-временем средствами стандартной библиотеки, лучше всегда использовать или только наивные объекты (без часового пояса), или только осведомлённые (с часовым поясом). Если их смешать — гарантированно будет беда.
#stdlib
В каждом языке есть участки, которые не особо удались создателям. Для большинства языков, созданных до двухтысячных годов, камнем преткновения стала работа со временем.
Питон — не исключение. Возьмём функцию, которая сравнивает дату-время с точностью до минуты:
from datetime import datetime, timezone
def equal(dt1, dt2):
return dt1.replace(second=0, microsecond=0) == dt2.replace(second=0, microsecond=0)
И сравним «сегодня» и «сейчас»:
>>> equal(datetime.today(), datetime.now())
True
Оказывается, это одно и то же ツ Метод
today()
возвращает не начало дня, как можно было бы ожидать, а текущий момент времени.А что насчёт времени по UTC?
>>> equal(datetime.now(timezone.utc), datetime.utcnow())
False
Неожиданно,
now()
с часовым поясом UTC и utcnow()
возвращают разные значения. Это потому, что now()
возвращает объект с часовым поясом, а utcnow()
— без. Хотя дата-время у них и совпадают.Если работать с датой-временем средствами стандартной библиотеки, лучше всегда использовать или только наивные объекты (без часового пояса), или только осведомлённые (с часовым поясом). Если их смешать — гарантированно будет беда.
#stdlib
Дата из строки
До некоторых пор в питоне не было простого способа создать дату из строки.
Либо так:
Либо так:
Либо сторонние библиотеки вроде
Но с версии 3.7 делать это стало легко и приятно, если строковые даты вы храните в формате ISO 8601 (что в любом случае хорошая идея):
Для даты-времени тоже работает:
🐥
#stdlib
До некоторых пор в питоне не было простого способа создать дату из строки.
Либо так:
import time
from datetime import date
>>> date_struct = time.strptime("2019-02-20", "%Y-%m-%d")
>>> date(*date_struct[:3])
datetime.date(2019, 2, 20)
Либо так:
from datetime import date, datetime
>>> dt = datetime.strptime("2019-02-20", "%Y-%m-%d")
>>> dt.date()
datetime.date(2019, 2, 20)
Либо сторонние библиотеки вроде
dateutil
или arrow
.Но с версии 3.7 делать это стало легко и приятно, если строковые даты вы храните в формате ISO 8601 (что в любом случае хорошая идея):
>>> date.fromisoformat("2019-02-20")
datetime.date(2019, 2, 20)
Для даты-времени тоже работает:
>>> datetime.fromisoformat("2019-02-20T14:30:15")
datetime.datetime(2019, 2, 20, 14, 30, 15)
🐥
#stdlib
Очень противоречивый день недели
Помните, я писал, что работа с датой и временем в Питоне не очень удалась? Проявилось это и в нумерации дней недели.
Нашлось место аж трём вариантам, бережно размазанным по трём модулям:
Судя по всему, сначала борьба шла между
#stdlib
Помните, я писал, что работа с датой и временем в Питоне не очень удалась? Проявилось это и в нумерации дней недели.
Нашлось место аж трём вариантам, бережно размазанным по трём модулям:
time.strftime("%w")
интервал [0, 6], вс = 0
time.strftime("%u")
интервал [1, 7], пн = 1
time.struct_time.tm_wday
интервал [0, 6], пн = 0
datetime.date.weekday()
интервал [0, 6], пн = 0
datetime.date.isoweekday()
интервал [1, 7], пн = 1
calendar.weekday()
интервал [0, 6], пн = 0
Судя по всему, сначала борьба шла между
вс = 0
и пн = 0
, а потом пришёл ISO 8601 и вообще всё испортил ツ#stdlib
Очередь с приоритетами
Некоторое время назад мы с вами сделали систему обработки заявок с приоритетами. Правила простые: более важные заявки идут вперёд, но среди заявок с одинаковым приоритетом действовует принцип очерёдности (FIFO).
Помог нам в этом модуль
Для ленивых любителей ООП в питоне есть класс
Сделаем простую заявку из двух полей — заказчик и вес:
Если не понимаете, что это за
А очередь возьмём готовую:
Теперь проверим. Ожидаем, что первым будет Френк (у него больше вес), вторым Лукас (пришёл раньше), а третьей — Зоя.
Так и вышло ツ
Есть неприятный нюанс. Модуль
#stdlib
Некоторое время назад мы с вами сделали систему обработки заявок с приоритетами. Правила простые: более важные заявки идут вперёд, но среди заявок с одинаковым приоритетом действовует принцип очерёдности (FIFO).
Помог нам в этом модуль
heapq
. Он всем хорош, кроме того, что исполнен в архитектурном стиле «потроха наружу» — это не всегда удобно.Для ленивых любителей ООП в питоне есть класс
queue.PriorityQueue
, который реализует ровно то, что нам надо — очередь с приоритетами.Сделаем простую заявку из двух полей — заказчик и вес:
import time
from functools import total_ordering
@total_ordering
class Request:
def __init__(self, name, weight):
self.name = name
self.weight = -weight
self._timestamp = time.time_ns()
def __str__(self):
return self.name
def __eq__(self, other):
return (self.weight, self._timestamp) == (other.weight, other._timestamp)
def __gt__(self, other):
return (self.weight, self._timestamp) > (other.weight, other._timestamp)
Если не понимаете, что это за
@total_ordering
, странные методы с кучей подчёркиваний и зачем тут _timestamp
— не переживайте, разберём отдельно.А очередь возьмём готовую:
from queue import PriorityQueue
q = PriorityQueue()
q.put(Request(name="Лукас", weight=1))
q.put(Request(name="Зоя", weight=1))
q.put(Request(name="Френк", weight=10))
Теперь проверим. Ожидаем, что первым будет Френк (у него больше вес), вторым Лукас (пришёл раньше), а третьей — Зоя.
while not q.empty():
print(q.get())
Френк
Лукас
Зоя
Так и вышло ツ
Есть неприятный нюанс. Модуль
queue
вообще-то создан для многотопочной работы, поэтому если вызвать у очереди get()
, когда она пустая — поток выполнения заблокируется на веки вечные. Так что придётся со всех сторон обкладываться проверками empty()
и full()
(если решите ограничить максимальный размер очереди).#stdlib
Некоторые животные равнее: сравниваем объекты в питоне
Британские учёные, известные своими исследованиями, решили составить общемировой рейтинг животных. Согласно методике, каждая зверюга описывается четырьмя атрибутами:
С методикой разобрались, осталось всех сравнить и построить итоговый рейтинг:
Вот досада, по умолчанию питон не знает, как сравнивать зверей. Дальше к нашим услугам куча способов, как это сделать.
Если хотим просто отсортировать список, подойдёт аргумент
Если сортировать только по ЧСВ, можно даже свою функцию не писать — в модуле
Френк ожидаемо победил в обеих номинациях. Чёртова птица.
#stdlib
Британские учёные, известные своими исследованиями, решили составить общемировой рейтинг животных. Согласно методике, каждая зверюга описывается четырьмя атрибутами:
class Pet:
def __init__(self, type, name, weight, importance):
self.type = type
self.name = name
self.weight = weight
self.importance = importance
def __repr__(self):
return self.name
weight
— это вес в килограммах, а importance
— чувство собственной важности (единица измерения не сообщается). Общий ранг рассчитывается как (weight + importance)
.С методикой разобрались, осталось всех сравнить и построить итоговый рейтинг:
frank = Pet(type="голубь", name="Френк", weight=1, importance=100)
claire = Pet(type="лиса", name="Клер", weight=5, importance=90)
zoe = Pet(type="свинка", name="Зоя", weight=90, importance=10)
pets = [claire, frank, zoe]
sorted(pets)
TypeError: '<' not supported between instances of 'Pet' and 'Pet'
Вот досада, по умолчанию питон не знает, как сравнивать зверей. Дальше к нашим услугам куча способов, как это сделать.
Если хотим просто отсортировать список, подойдёт аргумент
key
в функции sorted
:
key = lambda x: x.weight + x.importance
sorted_pets = sorted(
pets,
key=key,
reverse=True
)
print("Рейтинг по методике:")
print(sorted_pets)
Рейтинг по методике:
[Френк, Зоя, Клер]
key
— это функция, которая принимает наш объект, а возвращает число. Функция sorted
упорядочивает список объектов именно по этим числам.Если сортировать только по ЧСВ, можно даже свою функцию не писать — в модуле
operator
есть готовая:
import operator
key = operator.attrgetter("importance")
sorted_pets = sorted(
pets,
key=key,
reverse=True
)
print("Рейтинг по ЧСВ:")
print(sorted_pets)
Рейтинг по ЧСВ:
[Френк, Клер, Зоя]
Френк ожидаемо победил в обеих номинациях. Чёртова птица.
#stdlib
Сравнение объектов: кортежи
Опубликованный рейтинг зверей подвергся разгромной критике Фонда защиты дикой природы. Недопустимо складывать ЧСВ с килограммами, возмущаются эксперты.
Британских учёных такими мелочами не смутишь. Они выпустили новую редакцию методики. Теперь, уважая право животных на самоопределение, мы должны прежде всего сравнивать их ЧСВ. И только если ЧСВ одинаковое, сравнивать вес.
Вопрос, как это реализовать. Раньше у нас была простая функция:
Как поменять её на «сначала ЧСВ, затем вес»? Очень просто — с помощью кортежа:
Питон сравнивает кортежи поэлементно, причём переходит к следующему элементу, только если предыдущие одинаковые:
Именно то, что нам надо! А что, если сделать весь объект
Теперь не приходится указывать
#stdlib
Опубликованный рейтинг зверей подвергся разгромной критике Фонда защиты дикой природы. Недопустимо складывать ЧСВ с килограммами, возмущаются эксперты.
Британских учёных такими мелочами не смутишь. Они выпустили новую редакцию методики. Теперь, уважая право животных на самоопределение, мы должны прежде всего сравнивать их ЧСВ. И только если ЧСВ одинаковое, сравнивать вес.
Вопрос, как это реализовать. Раньше у нас была простая функция:
key = lambda x: x.weight + x.importance
Как поменять её на «сначала ЧСВ, затем вес»? Очень просто — с помощью кортежа:
key = lambda x: (x.importance, x.weight)
Питон сравнивает кортежи поэлементно, причём переходит к следующему элементу, только если предыдущие одинаковые:
(1, 10) < (2, 1)
True
(1, 10) > (1, 1)
True
Именно то, что нам надо! А что, если сделать весь объект
Pet
кортежем?
from collections import namedtuple
Pet = namedtuple("Pet", ("importance", "weight", "name", "type"))
frank = Pet(...)
claire = Pet(...)
zoe = Pet(...)
pets = [claire, frank, zoe]
sorted_pets = sorted(pets, reverse=True)
print([p.name for p in sorted_pets])
['Френк', 'Клер', 'Зоя']
Теперь не приходится указывать
key
— питон сортирует зверей как кортежи. Бонусом получили возможность сравнивать объекты напрямую:
claire > zoe
True
#stdlib
Сравнение объектов: дандеры
На презентации второй версии отчёта Френк нагадил на научного руководителя проекта. Пребывая в крайне дурном настроении, тот зачем-то полез в исходники и обнаружил там нашу реализацию через
Брызжа слюной, научрук отверг её как «необъектную». Попытки объяснить ему, что в питоне всё — объект не увенчались успехом. Придётся переделывать на явное использование
Окей, вот наш класс:
Сравнение на нём, естественно, не работает:
А чтобы заработало — придётся перекрыть специальные методы (они же дандеры), которые отвечают за сравнение:
Поскольку перекрывать все шесть методов лениво, можно воспользоваться декоратором
Для краткости я опустил проверку, что
Теперь будет работать и обычное сравнение, и сортировка:
Такой способ создания «сравнибельных» объектов всем хорош. Проверен временем, его ещё Рюрик в битве при Фермопилах с ацтеками использовал. Но есть и более молодёжный. О нём в следующий раз.
#stdlib
На презентации второй версии отчёта Френк нагадил на научного руководителя проекта. Пребывая в крайне дурном настроении, тот зачем-то полез в исходники и обнаружил там нашу реализацию через
namedtuple
.Брызжа слюной, научрук отверг её как «необъектную». Попытки объяснить ему, что в питоне всё — объект не увенчались успехом. Придётся переделывать на явное использование
class
, а то не отстанет.Окей, вот наш класс:
class Pet:
def __init__(self, name, weight, importance):
self.name = name
self.weight = weight
self.importance = importance
Сравнение на нём, естественно, не работает:
frank = Pet(...)
claire = Pet(...)
zoe = Pet(...)
claire > zoe
TypeError: '>' not supported between instances of 'Pet' and 'Pet'
А чтобы заработало — придётся перекрыть специальные методы (они же дандеры), которые отвечают за сравнение:
__lt__ (<)
__le__ (<=)
__eq__ (==)
__ne__ (!=)
__gt__ (>)
__ge__ (>=)
Поскольку перекрывать все шесть методов лениво, можно воспользоваться декоратором
@functools.total_ordering
и перекрыть только два — eq
и ещё один (например, lt
). Остальное декоратор сделает сам.
@functools.total_ordering
class Pet:
...
@property
def rank(self):
return (self.importance, self.weight)
def __eq__(self, other):
return self.rank == other.rank
def __lt__(self, other):
return self.rank < other.rank
Для краткости я опустил проверку, что
other
обладает нужными свойствами.Теперь будет работать и обычное сравнение, и сортировка:
claire > zoe
True
sorted_pets = sorted(pets, reverse=True)
print(sorted_pets)
[Френк, Клер, Зоя]
Такой способ создания «сравнибельных» объектов всем хорош. Проверен временем, его ещё Рюрик в битве при Фермопилах с ацтеками использовал. Но есть и более молодёжный. О нём в следующий раз.
#stdlib
Сравнение объектов: финал
Плохие новости: британские учёные не угомонились. Теперь каждый релиз должен проходить согласование в архитектурном комитете. И наш последний вариант с total_ordering и дандерами комитет забраковал.
Обоснование, цитирую: «решение недостаточно инновационное» (если когда-нибудь наблюдали работу архитектурного комитета в жизни, вас такой дичью не удивить). В приватной беседе архитекторы намекнули, что следует использовать новые фичи языка. Ну что ж, расчехляем датаклассы.
Датаклассы! Эта абсолютно анти-pythonic штука, которая нарушает сразу несколько постулатов питонячьего дзена. Но реализация с ними будет более компактной, тут не поспоришь. Вот она:
А вот как это работает:
— декоратор
— параметр
— сравнение производится по полям в том порядке, как они перечислены в классе (importance, weight, name)
—
Дальше можно сравнивать объекты как обычно:
Инновационнее некуда. Надеюсь, архитекторы будут довольны. Хотя лично мне этот вариант нравится меньше всех предыдущих.
Теперь вы знаете о сравнении объектов больше, чем 90% питонистов. Осталась ещё пара нюансов — они выйдут в режиссёрской версии от Френка за 99₽ в семечковом эквиваленте.
#stdlib
Плохие новости: британские учёные не угомонились. Теперь каждый релиз должен проходить согласование в архитектурном комитете. И наш последний вариант с total_ordering и дандерами комитет забраковал.
Обоснование, цитирую: «решение недостаточно инновационное» (если когда-нибудь наблюдали работу архитектурного комитета в жизни, вас такой дичью не удивить). В приватной беседе архитекторы намекнули, что следует использовать новые фичи языка. Ну что ж, расчехляем датаклассы.
Датаклассы! Эта абсолютно анти-pythonic штука, которая нарушает сразу несколько постулатов питонячьего дзена. Но реализация с ними будет более компактной, тут не поспоришь. Вот она:
from dataclasses import dataclass, field
@dataclass(order=True)
class Pet:
importance: int
weight: int
name: str = field(compare=False)
А вот как это работает:
— декоратор
dataclass
генерит кучу дандеров для класса, включая eq— параметр
order=True
заставляет его дополнительно сгенерить дандеры lt, le, gt, ge— сравнение производится по полям в том порядке, как они перечислены в классе (importance, weight, name)
—
field(compare=False)
исключает поле name из сравнения, так что сравнивается только (importance, weight)Дальше можно сравнивать объекты как обычно:
frank = Pet(...)
claire = Pet(...)
zoe = Pet(...)
frank > claire > zoe
True
Инновационнее некуда. Надеюсь, архитекторы будут довольны. Хотя лично мне этот вариант нравится меньше всех предыдущих.
Теперь вы знаете о сравнении объектов больше, чем 90% питонистов. Осталась ещё пара нюансов — они выйдут в режиссёрской версии от Френка за 99₽ в семечковом эквиваленте.
#stdlib
Создать полный дубль коллекции
У нас ответственная миссия: запустить в космос автомобиль. Сначала подготовим инфраструктуру — собственно машину и мега-пушку:
Проверим:
Работает!
Как всякий уважающий себя космический завод, наш умеет копировать машины. Очень удобно — можно сделать копию коллекции машин и всячески над ней издеваться. Например, очистить:
Оригинальный список при этом не пострадал, его можно спокойно запускать:
О, тут инженерам ещё хохма в голову пришла:
Очень смешно, отправить в космос чела из Роскосмоса на жигулях, ха-ха. Пошутили и хватит, запускаем Теслу:
Ну вот (((
Проблема в том, что
Поэтому, меняя
Создать полный дубликат коллекции поможет модуль
Ну, другое дело.
#stdlib
У нас ответственная миссия: запустить в космос автомобиль. Сначала подготовим инфраструктуру — собственно машину и мега-пушку:
from dataclasses import dataclass
@dataclass
class Car:
brand: str
model: str
driver: str
class SpaceCannon:
def launch(self, cars):
car = cars[0]
print(f"{car.brand} {car.model} driven by {car.driver} sent to space!")
Проверим:
car = Car(brand="Tesla", model="Roadster", driver="Starman")
cars = [car]
cannon = SpaceCannon()
cannon.launch(cars)
Tesla Roadster driven by Starman sent to space!
Работает!
Как всякий уважающий себя космический завод, наш умеет копировать машины. Очень удобно — можно сделать копию коллекции машин и всячески над ней издеваться. Например, очистить:
copied_cars = cars[:]
copied_cars.clear()
Оригинальный список при этом не пострадал, его можно спокойно запускать:
cannon.launch(cars)
Tesla Roadster driven by Starman sent to space!
О, тут инженерам ещё хохма в голову пришла:
copied_cars = cars[:]
copied_cars[0].brand = "ToSky"
copied_cars[0].model = "Zhiguli"
copied_cars[0].driver = "Roskosmos guy"
Очень смешно, отправить в космос чела из Роскосмоса на жигулях, ха-ха. Пошутили и хватит, запускаем Теслу:
cannon.launch(cars)
ToSky Zhiguli driven by Roskosmos guy sent to space!
Ну вот (((
Проблема в том, что
cars[:]
выполняет так называемое поверхностное копирование — сам список копируется, но в качестве его элементов используются ссылки на элементы оригинального списка.Поэтому, меняя
copied_cars[0]
, мы превратили оригинальную Теслу в Жигули (что само по себе заслуживает уважения, конечно).Создать полный дубликат коллекции поможет модуль
copy
:
import copy
car = ...
cars = [car]
copied_cars = copy.deepcopy(cars)
copied_cars[0].model = "Zhiguli"
cannon.launch(cars)
Tesla Roadster driven by Starman sent to space!
Ну, другое дело.
#stdlib
Узнать день недели 40 лет назад
Есть в питоне модуль
На деле он занимается форматированием календарей в HTML (именно то, что требуется в стандартной библиотеке любого языка) и предоставляет гениальные методы вроде itermonthdays, itermonthdays2, itermonthdays3 и itermonthdays4 (оцените богатство выбора, прямо как на воскресной ярмарке).
Но есть в нём и полезные функции. Например, узнать день недели для любой даты в прошлом или будущем:
Или вспомнить, сколько дней в июне:
Или проверить, високосный ли год:
А генерировать HTML-календари с помощью
#stdlib
Есть в питоне модуль
calendar
. Лично я ожидал от него крутых фич по работе с датами, которые не влезли в datetime
.На деле он занимается форматированием календарей в HTML (именно то, что требуется в стандартной библиотеке любого языка) и предоставляет гениальные методы вроде itermonthdays, itermonthdays2, itermonthdays3 и itermonthdays4 (оцените богатство выбора, прямо как на воскресной ярмарке).
Но есть в нём и полезные функции. Например, узнать день недели для любой даты в прошлом или будущем:
import calendar
wday = calendar.weekday(1959, 11, 5)
calendar.day_name[wday]
'Thursday'
Или вспомнить, сколько дней в июне:
import datetime as dt
today = dt.date.today()
_, days = calendar.monthrange(today.year, today.month)
days
30
Или проверить, високосный ли год:
calendar.isleap(2020)
True
А генерировать HTML-календари с помощью
calendar
вы не будете, надеюсь ツ#stdlib
Быстро найти элемент коллекции
Френк решил открыть магазин диковинок. Прайс-лист огромный, приведу только несколько позиций:
Магазин открылся, торговля идёт бойко, но есть проблемка. Покупатели донимают вопросом «у меня есть X рублей, какую самую дорогую дичь я могу купить за эту сумму?».
Френк очень плохо считает (неудивительно для голубя), поэтому требуется наша помощь. Давайте сначала решим «в лоб»:
Работает как часы! Только Френк жалуется, что
Надо бы отсортировать товары по цене и использовать алгоритм бинарного поиска, который работает за
Нам поможет модуль
Работает так:
— Создали отсортированный список цен.
— Покупатель принёс 5000₽ денег.
—
— Элемент слева от этой позиции и есть интересующий нас товар («мельница» за 3300).
Френк доволен.
#stdlib
Френк решил открыть магазин диковинок. Прайс-лист огромный, приведу только несколько позиций:
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), в конце просто вернуть его.
Опрос следует.
#задачка
Допустим, вы пишете программу, которой на вход последовательно, одно за другим, приходят числа. Ваша задача — накапливать их как-то, а потом, когда числа перестанут приходить — вернуть отсортированный список.
Как думаете, что будет работать быстрее:
— Складывать приходящие числа в неупорядоченную кучу, отсортировать в конце.
— Постоянно поддерживать отсортированный список (с помощью bisect), в конце просто вернуть его.
Опрос следует.
#задачка
Что быстрее?
Anonymous Poll
42%
Отсортировать в конце
44%
Держать отсортированным через bisect
14%
Одинаково
Сортировать в конце или держать отсортированным?
Вы пишете программу, которой на вход одно за другим приходят числа. Задача — накапливать их, а потом вернуть отсортированный список.
Вопрос — что будет работать быстрее:
— Отсортировать список в конце.
— Постоянно держать отсортированным.
---
Ну что, давайте разбираться!
Сразу оговорюсь, что оценивать будем именно чистое время выполнения нашего обработчика. Понятно, что если источник будет присылать по одному числу в минуту, то общее время выполнения будет определяться именно скоростью источника, а не нашим обработчиком — вне зависимости от выбранного алгоритма. Поэтому исходим из того, что источник фигачит числами как из пулемёта.
Мы знаем, что сортировка на n числах занимает O(n logn) операций. Это сложность варианта «сортировать в конце».
Мы также знаем, что один бинарный поиск занимает O(log n) операций. В варианте «поддерживать отсортированным» мы выполняем поиск n раз, значит итоговая сложность O(n logn).
Там O(n logn) и тут O(n logn) — значит, варианты равнозначные, расходимся.
На самом деле нет ツ Посмотрите на реализацию варианта «поддерживать отсортированным»:
Да, бинарный поиск выполняется за логарифмическое время. Но после него идёт вставка в массив — она занимает линейное время.
Таким образом, на каждое число алгоритм тратит O(n) операций, а на n чисел — O(n²). Это сильно медленнее, чем O(n logn).
Чтобы не быть голословным, я реализовал и сравнил в действии оба алгоритма. Не верьте на слово и попробуйте сами (смотреть на десктопе).
Итого, вариант «сортировать в конце» побеждает с большим отрывом.
#задачка
Вы пишете программу, которой на вход одно за другим приходят числа. Задача — накапливать их, а потом вернуть отсортированный список.
Вопрос — что будет работать быстрее:
— Отсортировать список в конце.
— Постоянно держать отсортированным.
---
Ну что, давайте разбираться!
Сразу оговорюсь, что оценивать будем именно чистое время выполнения нашего обработчика. Понятно, что если источник будет присылать по одному числу в минуту, то общее время выполнения будет определяться именно скоростью источника, а не нашим обработчиком — вне зависимости от выбранного алгоритма. Поэтому исходим из того, что источник фигачит числами как из пулемёта.
Мы знаем, что сортировка на 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. Если интересно, как выглядит «сишная» часть питона, посмотрите — это один из самых простых модулей.
#код
Получил такой комментарий на заметку про быстрый и медленный алгоритмы:
> Мне кажется, тут не совсем корректное сравнение. 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. Если интересно, как выглядит «сишная» часть питона, посмотрите — это один из самых простых модулей.
#код
Очень странные модули
Когда-то создатели питона считали, что в стандартную библиотеку надо запихнуть вообще всё. В результате там до сих пор живут довольно экзотичные (кхм) модули. Вот некоторые из них, в порядке нарастания безумия:
Надеюсь, вам никогда не придётся с ними столкнуться ツ
#stdlib
Когда-то создатели питона считали, что в стандартную библиотеку надо запихнуть вообще всё. В результате там до сих пор живут довольно экзотичные (кхм) модули. Вот некоторые из них, в порядке нарастания безумия:
array
— типизированные массивы чисел (почувствуйте себя С-программистом).curses
— создание «ASCII-арт» интерфейсов под линукс (серьёзно?).reprlib
— объектный интерфейс к repr
(что вообще происходит).formatter
— мега-извратный способ работы с текстом (ммм, форматирование, его же так мало в питоне).msilib
— создание установочных MSI-пакетов под винду (фууу).macpath
— работа с путями файловой системы в Mac OS 9 (поздравим её, в этом году 20 лет исполняется).chunk
— поддержка аудиоформата времён компьютеров Commodore и Amiga (40 лет назад! спасибо, что живой).Надеюсь, вам никогда не придётся с ними столкнуться ツ
#stdlib
Перечислить элементы коллекции с порядковыми номерами
Одна уважаемая компания заказала вам разработку теста для соискателей на позицию «дизайнер продукта». Есть список вопросов с вариантами ответа:
Вы написали код, который показывает на экране каждый вопрос с вариантами ответа:
Но есть нюанс — варианты должны быть пронумерованы. Как бы это сделать?
Да, но нет. Очень часто, когда видите в коде
P.S. Если это для вас слишком просто, представьте себя сумасшедшим любителем однострочников и попробуйте расшифровать такое:
#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
Проверить, что выполняется хотя бы одно условие
Френк решил обзавестить новым домом. Он весьма требовательная скотинка, поэтому подготовил набор критериев для оценки жилья:
Допустим, место подходит, если хотя бы одно условие выполняется. При этом, конечно, мы хотим проверять не все условия, а до первого сработавшего:
Но до чего же унылая получилась эта
А что, если Френк согласен заселиться только туда, где выполняются все условия? Думаю, вы уже поняли:
Есть нюанс. Допустим, Френк в отчаянии отказался от всех проверок. Как поведут себя
P.S. Сможете сделать то же самое на
#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
Создать словарь по списку ключей
Предположим, вы сделали робота для общественных пространств. Он будет помогать людям.
Вы решаете, что полезно собирать статистику добрых дел — что и сколько раз робот сделал. Для этого удобно использовать счётчик, ключами которого будут названия действий, а значениями — количество выполнений.
Робот постоянно учится новым полезным активностям, так что набор дел не фиксированный. Он хранится в списке:
Как бы из этого списка сделать счётчик? Так не надо, конечно:
Намного роднее воспользоваться dictionary comprehension (простите, что на англ — непереводимая игра слов):
Или малоизвестным методом
Первый аргумент — список ключей, второй — умолчательное значение. Удобно, а?
#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 есть специальная секция scripts для таких штук. Для Питона ничего подобного не предусмотрено. Но есть отличное решение:
https://antonz.ru/makefile/
#код
Когда разрабатываешь библиотеку или приложение, всегда найдутся задачи, которые выполняешь изо дня в день:
— проверить код линтерами,
— прогнать тесты с замером покрытия,
— запустить в докере,
...
JS-разработчикам повезло: у них в package.json есть специальная секция scripts для таких штук. Для Питона ничего подобного не предусмотрено. Но есть отличное решение:
https://antonz.ru/makefile/
#код