Основы программирования в Python

Материал подготовил: Виталий Евтушенко, НИУ ВШЭ

Containers basics, Loops and Sorting, Computational complexity and big-O

Контейнеры (в Python и как абстрактный тип данных)

Многие понятия в компьютерной науке и программировании были придуманы и концептуализированы задолго до появления ЯП Python, а порой и до появления компьютеров в нашем понимании этого.

Одной из таких концепций, существующих в компьютерной науке является абстрктный тип данных (abstract data type), обитающий на более высоком уровне абстракции, чем обычный тип данных (есть обычный, а есть абстрктный, он более абстрактный, чем обычный) и структура данных (как данные хранятся, какие методы поддерживаются, какова сложность методов из-за особенностей хранения данных).

В общем виде, можно сказать, что абстрактный тип данных является нашим идеальным представлением о том, как должно быть (какие функции реализованы, как себя ведет), а с помощью структуры данных мы реализуем (implementation) это идеальное представление на ЭВМ.

Что такое контейнер в Python?

  • Контейнер (container) - любой тип или объект, который содержит в себе ссылки на другие объекты.
  • Примеры встроенных контейнеров: list (листы - лист, реализованный в Python с помощью массива), tuple (неизменяемые листы), dictionary (словари - ассоциативный массив реализованный в Python с помощью хэш-таблицы), set (множества, реализованные в Python с помощью вычисления хэш-функции), frozenset (неизменяемые множества). Отдельно стоит отметить модуль коллекций в Python - это уже оптимизированные (быстрее выполняются, менее затратны по памяти) для определенных задач контейнеры.
  • Пример еще более оптимизированного контейнера : class numpy.array из библиотеки для численных вычислений numpy (numerical python). Его главная особенность в том, что он, как и вся библиотека (в общем виде, которая - интерфейс для доступа к более низкоуровнему коду не на ЯП Python) написан на ЯП Fortran (Formula translator), который работает много быстрее, чем интерпретируемый ЯП Python. Класс позволяет проводить операция с массивом как с вектором и тем самым экономить время на написание явные циклов или списковых включений/ генераторов списков (list comprehensions) на Python'е.

Циклы

Каждая вычислительная операция, например, сложение двух простых чисел или же вычисление матрицы попырных расстояний, имеет свою вычислительную сложность, которая определяет. Сложность и по времени, и по памяти можно измерить (например, запустить алгоритм много раз и замерить время, или затраты памяти) или описать функцией.

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

$O$ - нотация - асимптотическое ограничение функции, описывающей алгоритм, сверху (не более). Отражает изменение времени выполнения в зависимости от изменения числа элементов.

фраза «сложность алгоритма есть O(f(n))» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n);

$\Omega$ - нотация - как и $O$- нотация - это асимптотическое ограничение функции, описывающей алгоритм, но уже снизу (не менее). В реальной жизни много чаще используется O - нотация.

Стоит повторно ометить, что сложность алгоритма обычно принято описывать по члену с максимальной степени (при стремлении к бесконечности, степень возрастает быстрее, чем коэфициент). Например, если в $O$-нотации алгоритм работает за $O(n^3 + 8n + \sqrt{9n})$ (какой-нибудь поиск на графе, в том числе социальном), то его запишут, как $O(n^3)$.

Почему важно?

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

Полезные ссылки:

Сортировки

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

Формулировка задачи сортировки

На что обратить внимание?

  • Такие алгоритмы сортировок, как merge sort, quicsort(очень часто используемые), bubble sort (с него, обычно, начинают знакомство с сортировками), counting sort (иногда бывает полезным. удобно реализовать в python используя dictionary и set) и bogosort/ случайная сортировка (пример того, какими не эффективными могут быть сортировки)
  • Условия применимости алгоритмов сортировки (и не только сортировки). Например, merge- или quicsort не всегда могут оказаться лучшим (самым быстрым, подходящим по по памяти), для Ваших данных или их структуры, алгоритмом.

Полезные ссылки:

Замерить время исполнения алгоритма в Jupiter'e можно, используя одну из следующих магических команд (рассмотрены на первом занятии) или с помощью модуля datetime

Полезные ссылки:

In [1]:
def big_loop():
    i = 0
    while i < 10000000:
        i += 1
In [2]:
# измеряет время
%time {big_loop()}
CPU times: user 4 µs, sys: 0 ns, total: 4 µs
Wall time: 7.87 µs
In [3]:
%%timeit
# запускает ячейку n раз, замеряя среднее время выполнения и выводя его в приятном виде
big_loop()
661 ms ± 113 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [4]:
#с помощью модуля datetime
class timeit():
    from datetime import datetime
    def __enter__(self):
        self.tic = self.datetime.now()
    def __exit__(self, *args, **kwargs):
        print('runtime: {}'.format(self.datetime.now() - self.tic))
        
with timeit():
    # your code, e.g., 
    big_loop()
runtime: 0:00:00.515888