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

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

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

#пакетик

День списков

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

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

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

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

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

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

#stdlib

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

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

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

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

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

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

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

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

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

#stdlib

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

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

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

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 элементов.

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

#stdlib

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

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

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

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

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

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

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

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

#stdlib

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

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

Если в массиве под списком остались свободные места, то метод .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(), то питон его скукожит — выделит новый массив поменьше и перенесет элементы в него.

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

#stdlib

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

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

Выборка из списка по индексу работает за 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) — подробности в комментариях.

#stdlib

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

Как мы выяснили, у списка работают за 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 элементов — это уже заметно. Или если список из миллиона элементов — тоже.

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

#stdlib

Сложность алгоритмов

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

Можно измерить чистое время выполнения в секундах, но это ненадежно — зависит от аппаратной конфигурации и объема исходных данных. Поэтому придумали мерить сложность алгоритма в терминах количества операций.

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

Такую оценку называют «Big-O» или «асимптотическим анализом» (потому что она работает для больших значений N).

Вот распространенные оценки алгоритмов от более быстрых (мало операций) к более медленным (много операций):

Константная сложность O(1)

Время выполнения алгоритма не зависит от объема исходных данных. Идеальный алгоритм!

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

lst = [random.random() for _ in range(n)]
idx = random.randint(0, n-1)
# O(1)
lst[idx]

Логарифмическая O(log n)

При увеличении n время выполнения алгоритма растет такими же темпами, как log(n). Логарифм растет медленно (log 1000000 ≈ 20), так что даже при больших n логарифмические алгоритмы работают достаточно быстро.

Например, найти элемент в отсортированном списке:

el = random.random()
sorted_lst = sorted(lst)
# O(log n)
bisect.bisect(sorted_lst, el)

Линейная O(n)

Время выполнения алгоритма растет такими же темпами, как n. Как правило, такие алгоритмы перебирают все исходные данные.

Например, найти элемент в неотсортированном списке:

el = random.random()
# O(n)
idx = lst.index(el)

Линейно-логарифмическая O(n log n)

Время выполнения алгоритма растет такими же темпами, как n × log(n). Алгоритм получается медленнее, чем O(n), но не слишком (логарифм n намного меньше n, помните?).

Например, отсортировать список:

# O(n log n)
sorted(lst)

Продолжение следует ツ Если что непонятно — спрашивайте в комментариях.

#код

Сложность алгоритмов: полиномиальные

Продолжаем рассматривать оценки скорости алгоритмов, которые часто встречаются на практике. С быстрыми (константные, логарифмические) и «условно-быстрыми» (линейные, линейно-логарифмические) мы разобрались. Продолжим «условно-медленными» — полиномиальными.

Квадратичная сложность O(n²)

Время выполнения растет как n². Обычно это значит, что алгоритм перебирает все элементы, и на каждом шаге перебирает их еще раз. На больших n квадратичные алгоритмы работают ощутимо медленно.

Например, сравнить два списка по принципу «каждый элемент с каждым»:

# O(n²)
for a in lst1:
  for b in lst2:
    print(a > b)

Полиномиальная O(nᵏ)

Время выполнения растет как n в некоторой фиксированной степени k: n³, n⁴, n⁵.

С одной стороны, по сравнению с O(log n) это медленно. С другой, когда действительно сложную задачу можно решить за полиномиальное время — это успех.

Если слышали о проблеме «P vs NP», то P — как раз полиномиальные (= быстрые) алгоритмы, а NP — суперполиномиальные (= медленные). Так что для некоторых задач O(nᵏ) очень даже быстро ツ

Строго говоря, линейные (k=1) и квадратичные (k=2) алгоритмы — частные случаи полиномиальных.

Пример полиномиального алгоритма — наивное умножение двух матриц. Выполняется за O(n³):

# A размера n×m
# B размера m×p
for i in range(0, n):
  for j in range(0, p):
    sum_ = 0
    for k in range(0, m):
      sum_ += A[i][k] * B[k][j]
    C[i][j] = sum_

Продолжение следует ツ Если что непонятно — спрашивайте в комментариях.

#код

Сложность алгоритмов: суперполиномиальные

Продолжаем рассматривать оценки скорости алгоритмов, которые часто встречаются на практике.

С быстрыми (константные, логарифмические), «условно-быстрыми» (линейные, линейно-логарифмические) и «условно-медленными» (полиномиальными) мы разобрались. Остались только улиточки — суперполиномиальные.

Экспоненциальная сложность O(2ⁿ)

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

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

Типичная задача с экспоненциальным временем решения — задача о рюкзаке:

Вор пробрался на склад, где хранится N ценных штуковин. У каждого предмета своя стоимость и вес. В рюкзаке можно унести барахла не больше X кг общего веса. Какой набор штуковин выбрать вору, чтобы унести добра на максимальную сумму?

Чтобы выбрать оптимальный набор, придется сравнить все возможные комбинации предметов — их как раз 2ⁿ (все подмножества множества из n элементов).

На практике можно решить, например, «жадным» алгоритмом, который сортирует предметы по удельной ценности (стоимость / вес), и набивает рюкзак по убыванию этой ценности, пока не закончится место. Сложность становится всего-то O(n logn) — хотя решение не оптимальное, конечно.

Или если веса целочисленные, задача о рюкзаке и вовсе решается методом динамического программирования за O(nX).

Факториальная O(n!)

Время выполнения растет как факториал от n (n! = n × (n-1) × (n-2) × ... × 1). Это жесть! Если алгоритм факториальной сложности — вы не сможете использовать его даже на наборе из 20 элементов.

Типичная задача с факториальным временем решения — задача коммивояжера:

Рьяному менеджеру по продажам нужно объехать N городов в разных точках страны. Как найти самый короткий маршрут, чтобы заехать в каждый город хотя бы раз и в итоге вернуться домой?

Выбрать первый город можно n способами, второй n-1, третий n-2, и так далее — так и получается n! маршрутов, среди которых приходится искать оптимальный.

На практике можно решать методом динамического программирования, который дает экспоненциальную сложность O(2ⁿn²). Тоже не вариант для больших n, но значительно быстрее факториального алгоритма.

Или забыть об оптимальном решении и считать жадным алгоритмом, который всегда выбирает ближайший город (O(n²)).

Окончание следует ツ Если что непонятно — спрашивайте в комментариях.

#код

Сложность алгоритмов: итоги

Вот какие алгоритмы мы рассмотрели:

— Константные O(1)
— Логарифмические O(log n)
— Линейные O(n)
— Линейно-логарифмические O(n log n)
— Квадратичные O(n²)
— Полиномиальные O(nᵏ)
— Экспоненциальные O(2ⁿ)
— Факториальные O(n!)

O(1) — всегда лучший вариант, а O(log n) — почти всегда.

С полиномиальными сложнее — тут все зависит от задачи. Где-то стыдно выбирать O(n), а где-то и O(n²) будет большим успехом.

O(2ⁿ) и O(n!) не работают на больших n, поэтому на практике вместо них часто используют неоптимальные, но быстрые алгоритмы.

А еще с помощью «big-O» можно измерять потребление памяти алгоритмом. Там тоже много интересного.

Константного времени вашим алгоритмам! Ну или логарифмического ツ

#код

Кстати! Если разбор алгоритмов показался вам суховатым или занудным, у меня есть короткое объяснение на котиках и с картинками 🐈
https://antonz.ru/big-o/

#код

Если вы написали отличную статью, о которой никто не знает

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

Поэтому провожу эксперимент! Готов опубликовать ссылку на вашу статью, если она мне понравится. Бесплатно. Знаменитостью это вас не сделает, но статью точно увидит больше людей.

Все условия

Прогнозируем будущее по настоящему

Поговорим о простом, но действенном способе предсказывать будущее.

Основан он на цепях Маркова. Марков — великий русский ясновидец и экстрасенс. Враги приковали его цепями к стене и пытали, выведывая будущее. Отсюда название.

Если вы обалдели от такого начала, то не зря. Я бессовестно соврал. Андрей Марков был математиком, и никто его не пытал.

Но цепи Маркова действительно предсказывают будущее! Причем очень по-человечески — смело и наивно.

Например, я посмотрел архив погоды за 10 лет, и выяснил, что если в какой-то день Д было +5°, то и на следующий (Д+1) чаще всего тоже. Поэтому я теперь считаю, что если сегодня +5° — завтра наверняка тоже +5°. При этом что там было вчера и позавчера, я игнорирую.

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

Например, предиктивный ввод. Это когда вы пишете «привет», а айфон предлагает сразу добавить «как» и «как дела». У айфона внутри нейросеть, но цепи Маркова тоже так умеют.

Если же не предлагать варианты слов человеку, а выбирать автоматически — получится генератор текста. Саша Беспоясов недавно как раз написал классный разбор такого генератора на JS, а теперь мы добавили примеры и на Python.

Посмотрите:
https://bespoyasov.ru/blog/text-generation-with-markov-chains/

#код