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

Если в массиве под списком остались свободные места, то метод .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/

#код

Люди и код

Неожиданно для себя стал гостем подкаста. Мы с Тимуром Тукаевым хотели сделать статью, но в аудио-формате она получилась живее и интереснее.

Послушайте, если вам интересно про мои проекты или открытый код в целом.

Темы выпуска:

— Чего не хватает современному Open Source и какие у него проблемы.
— Зачем корпорации заигрывают с Open Source и насколько они разделяют идеи OSI и FSF.
— Что жизнеспособнее — открытое или проприетарное ПО.
— Как начать контрибьютить в Open Source и какие проекты выбрать.
— История открытых библиотек iuliia и sqlean.

https://we.fo/1604736632

P.S. Поскольку к записи мы специально не готовились, звучу я как из ведра. Но если потерпеть минуту, вы привыкнете 😁

⚫ В О Й Н А

Как изучать Python, если знаешь 1С

Пришел вопрос от подписчика:

Сейчас являюсь разработчиком в 1С, но хотел бы начать изучать Python и уйти полностью в него. С чего начать?

Знание любого языка программирования, в том числе 1С — отличная база для изучения питона. Вам уже не нужно объяснять базовые концепции (вроде переменных и циклов), так что можно сразу переходить к специфике.

На Степике есть хорошая пара курсов «Поколение Python» (первый, второй) — начните с них. Первый курс для вас будет простоват, так что очевидные вещи можно пропускать.

Дальше — в зависимости от специализации. Для веб-разработчика хорошими вариантами будут «Django, потанцуем?» или «Django 3».

Для старта в анализе данных или data science — «Введение в Data Science» или демка «Аналитик данных».

Что я НЕ рекомендую для старта:

— Обучаться по книгам и видео-лекциям на ютубе. Хороший вариант, но требует стальной силы воли, которой большинство людей не обладают.

— Покупать программу от Яндекс-практикума. В Практикуме учат хорошо, но если вы уже умеете программировать — я бы не спешил тратить 100–150К ₽. Всегда успеете.

— Покупать программу от «инфоцыган». Не буду называть конкретные бренды, но большинство «конкурентов» Яндекс-практикума — пустая трата денег. Избегайте их как огня.

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