#!/usr/bin/env python
# coding: utf-8

# # Основы программирования в Python
# Материал подготовил: Виталий Евтушенко, НИУ ВШЭ

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

# ## [Контейнеры](https://en.wikipedia.org/wiki/Container_(abstract_data_type%29) (в Python и как абстрактный тип данных)

# Многие понятия в компьютерной науке и программировании были придуманы и концептуализированы задолго до появления ЯП Python, а порой и до появления компьютеров в нашем понимании этого. 
# 
# Одной из таких концепций, существующих в компьютерной науке является [абстрктный тип данных (abstract data type)](https://en.wikipedia.org/wiki/Abstract_data_type), обитающий на более высоком уровне абстракции, чем обычный тип данных (есть обычный, а есть абстрктный, он более абстрактный, чем обычный) и [структура данных](https://en.wikipedia.org/wiki/Data_structure) (как данные хранятся, какие методы поддерживаются, какова сложность методов из-за особенностей хранения данных). 
# 
# **В общем виде**, можно сказать, что абстрактный тип данных является нашим идеальным представлением о том, как должно быть (какие функции реализованы, как себя ведет), а **с помощью структуры данных мы реализуем (implementation)** это идеальное представление на ЭВМ.
# 
# [Что такое контейнер в Python?](https://stackoverflow.com/questions/11575925/what-exactly-are-containers-in-python-and-what-are-all-the-python-container)
# - **Контейнер (container)** - любой тип или объект, который содержит в себе ссылки на другие объекты.
# - **Примеры встроенных контейнеров**: [list](https://en.wikipedia.org/wiki/List_(abstract_data_type%29) (листы - лист, реализованный в Python с помощью массива), tuple (**неизменяемые** листы), [dictionary](https://en.wikipedia.org/wiki/Associative_array) (словари - ассоциативный массив реализованный в Python с помощью хэш-таблицы), [set](https://en.wikipedia.org/wiki/Set_(abstract_data_type%29) (множества, реализованные в Python с помощью вычисления хэш-функции), frozenset (**неизменяемые** множества). Отдельно стоит отметить модуль [коллекций](https://docs.python.org/3/library/collections.html) в Python - это уже оптимизированные (быстрее выполняются, менее затратны по памяти) для определенных задач контейнеры.
# - **Пример еще более оптимизированного контейнера** : class [numpy.array](https://docs.scipy.org/doc/numpy/reference/generated/numpy.array.html) из библиотеки для численных вычислений numpy (numerical python). Его главная особенность в том, что он, как и вся библиотека (в общем виде, которая - интерфейс для доступа к более низкоуровнему коду не на ЯП Python) написан на ЯП Fortran (Formula translator), который работает много быстрее, чем интерпретируемый ЯП Python. Класс позволяет проводить операция с массивом как с вектором и тем самым экономить время на написание явные циклов или списковых включений/ генераторов списков (list comprehensions) на Python'е.

# ## Циклы

# В общем виде, цикл в программировании - это [управляющая конструкция](https://en.wikipedia.org/wiki/Control_flow)
# - [Алгоритмические структуры (типы алгоритмов) с блок-схемами](https://www.inf1.info/algorithmtype) **(сюда стоит зайти)**
# - [Циклы](https://en.wikipedia.org/wiki/Control_flow#Loops)
# - [Виды циклов](https://ru.wikipedia.org/wiki/%D0%A6%D0%B8%D0%BA%D0%BB_(%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%29#%D0%92%D0%B8%D0%B4%D1%8B_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2)

# ## [Вычислительная сложность](http://www.machinelearning.ru/wiki/index.php?title=%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C)

# Каждая вычислительная операция, например, сложение двух простых чисел или же вычисление матрицы попырных расстояний, имеет свою вычислительную сложность, которая определяет. **Сложность и по времени, и по памяти можно измерить** (например, запустить алгоритм много раз и замерить время, или затраты памяти) или **описать функцией**. 
# 
# Выделяют сложность [в лучшем, в среднем и в худшем случаях](https://en.wikipedia.org/wiki/Best,_worst_and_average_case) (некоторые алгоритмы очень зависят от данных и их структур, которые подаются на вход).
# 
# [**$O$ - нотация**](https://en.wikipedia.org/wiki/Big_O_notation) - асимптотическое ограничение функции, описывающей алгоритм, сверху (не более). Отражает изменение времени выполнения в зависимости от изменения числа элементов.
# > фраза «сложность алгоритма есть O(f(n))» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n);
# 
# - [Math FANDOM](http://ru.math.wikia.com/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5)
# 
# **$\Omega$ - нотация** - как и $O$- нотация - это асимптотическое ограничение функции, описывающей алгоритм, но уже снизу (не менее). В реальной жизни много чаще используется O - нотация.
# 
# Стоит повторно ометить, что сложность алгоритма обычно принято описывать по члену с максимальной степени (при стремлении к бесконечности, степень возрастает быстрее, чем коэфициент). Например, если в $O$-нотации алгоритм работает за $O(n^3 + 8n + \sqrt{9n})$ (какой-нибудь поиск на графе, в том числе социальном), то его запишут, как $O(n^3)$.
# 
# **Почему важно?**
# - Крайне рекомендуется хотя бы в общих чертах понимать, что происходит под "капотом" Вашей "машины", если с ней возникают какие-то проблемы (слишком долго исполняется код, тратится вся оперативная память) и есть желание улучшить это (например, меньше времени ждать, пока обучается модель или понимать, почему выдается ошибка о, например, нехватке памяти). Есть риск, что проблема не в машине, а в неудачно выбранном для текущей задачи алгоритме.
# 
# **Полезные ссылки:**
# - [Analysis of algorithms](https://en.wikipedia.org/wiki/Analysis_of_algorithms)
# - [Know Thy Complexities!](http://bigocheatsheet.com/)
# - [A Gentle Introduction to Algorithm Complexity Analysis](http://discrete.gr/complexity/) и [перевод в 4 статьях](https://habrahabr.ru/post/196226/) **(сюда стоит зайти)**
# 

# ## Сортировки

# > Сортировка (англ. sorting) - **упорядочивание**, последовательное расположение объектов **в зависимости от выбранного критерия** (определяем этим критерием последовательность расположения, правило упорядочивания). **Примеры**: отсортировать по возрастанию, отсортировать так, чтобы на чётных местах объекты были расположены согласно убиванию их квадратных корней, а на нечётных согласно возрастанию их кубических значений.   
# 
# [**Формулировка задачи сортировки**](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8#%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8)
# 
# **На что обратить внимание?**
# - Такие **алгоритмы сортировок**, как [merge sort](https://en.wikipedia.org/wiki/Merge_sort), [quicsort](https://en.wikipedia.org/wiki/Quicksort)(очень часто используемые), [bubble sort](https://en.wikipedia.org/wiki/Bubble_sort) (с него, обычно, начинают знакомство с сортировками), [counting sort](https://en.wikipedia.org/wiki/Counting_sort) (иногда бывает полезным. удобно реализовать в python используя dictionary и set) и [bogosort/ случайная сортировка](https://ru.wikipedia.org/wiki/Bogosort) (пример того, какими не эффективными могут быть сортировки)
# - **Условия применимости алгоритмов сортировки (и не только сортировки)**. Например, merge- или quicsort не всегда могут оказаться лучшим (самым быстрым, подходящим по по памяти), для Ваших данных или их структуры, алгоритмом.
# 
# **Полезные ссылки:**
# - [Таблица сравнения сложности алгоритмов сортировки](https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms) **(сюда стоит зайти)**
# - Серия видео [AlgoRythmics
# ](https://www.youtube.com/watch?v=XaqR3G_NVoo) - ансамбли, танцующие под классическую и народную музыку, своими движениями и перестановками визуализирующие алгоритмы. **(сюда стоит зайти)**
# - [Хороший пример времени выполнения разных алгоритмов сортировки](https://www.youtube.com/watch?v=ZZuD6iUe3Pc)
# - [Список алгоритмов сортировки](https://en.wikipedia.org/wiki/Sorting_algorithm) **(сюда стоит зайти)**
# 

# **Замерить время исполнения алгоритма в Jupiter'e можно, используя одну из следующих [магических команд](https://ipython.readthedocs.io/en/stable/interactive/magics.html) (рассмотрены на первом занятии) или с помощью модуля datetime** 

# **Полезные ссылки:**
# - [Ссылка 1](http://pynash.org/2013/03/06/timing-and-profiling/)
# - [Ссылка 2](https://stackoverflow.com/questions/32565829/simple-way-to-measure-cell-execution-time-in-ipython-notebook)

# In[1]:


def big_loop():
    i = 0
    while i < 10000000:
        i += 1


# In[2]:


# измеряет время
get_ipython().run_line_magic('time', '{big_loop()}')


# In[3]:


get_ipython().run_cell_magic('timeit', '', '# запускает ячейку n раз, замеряя среднее время выполнения и выводя его в приятном виде\nbig_loop()\n')


# 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()