{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Основы программирования в Python\n",
    "Материал подготовил: Виталий Евтушенко, НИУ ВШЭ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Containers basics, Loops and Sorting, Computational complexity and big-O"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Контейнеры](https://en.wikipedia.org/wiki/Container_(abstract_data_type%29) (в Python и как абстрактный тип данных)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Многие понятия в компьютерной науке и программировании были придуманы и концептуализированы задолго до появления ЯП Python, а порой и до появления компьютеров в нашем понимании этого. \n",
    "\n",
    "Одной из таких концепций, существующих в компьютерной науке является [абстрктный тип данных (abstract data type)](https://en.wikipedia.org/wiki/Abstract_data_type), обитающий на более высоком уровне абстракции, чем обычный тип данных (есть обычный, а есть абстрктный, он более абстрактный, чем обычный) и [структура данных](https://en.wikipedia.org/wiki/Data_structure) (как данные хранятся, какие методы поддерживаются, какова сложность методов из-за особенностей хранения данных). \n",
    "\n",
    "**В общем виде**, можно сказать, что абстрактный тип данных является нашим идеальным представлением о том, как должно быть (какие функции реализованы, как себя ведет), а **с помощью структуры данных мы реализуем (implementation)** это идеальное представление на ЭВМ.\n",
    "\n",
    "[Что такое контейнер в Python?](https://stackoverflow.com/questions/11575925/what-exactly-are-containers-in-python-and-what-are-all-the-python-container)\n",
    "- **Контейнер (container)** - любой тип или объект, который содержит в себе ссылки на другие объекты.\n",
    "- **Примеры встроенных контейнеров**: [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 - это уже оптимизированные (быстрее выполняются, менее затратны по памяти) для определенных задач контейнеры.\n",
    "- **Пример еще более оптимизированного контейнера** : 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'е."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Циклы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В общем виде, цикл в программировании - это [управляющая конструкция](https://en.wikipedia.org/wiki/Control_flow)\n",
    "- [Алгоритмические структуры (типы алгоритмов) с блок-схемами](https://www.inf1.info/algorithmtype) **(сюда стоит зайти)**\n",
    "- [Циклы](https://en.wikipedia.org/wiki/Control_flow#Loops)\n",
    "- [Виды циклов](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)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Вычислительная сложность](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)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Каждая вычислительная операция, например, сложение двух простых чисел или же вычисление матрицы попырных расстояний, имеет свою вычислительную сложность, которая определяет. **Сложность и по времени, и по памяти можно измерить** (например, запустить алгоритм много раз и замерить время, или затраты памяти) или **описать функцией**. \n",
    "\n",
    "Выделяют сложность [в лучшем, в среднем и в худшем случаях](https://en.wikipedia.org/wiki/Best,_worst_and_average_case) (некоторые алгоритмы очень зависят от данных и их структур, которые подаются на вход).\n",
    "\n",
    "[**$O$ - нотация**](https://en.wikipedia.org/wiki/Big_O_notation) - асимптотическое ограничение функции, описывающей алгоритм, сверху (не более). Отражает изменение времени выполнения в зависимости от изменения числа элементов.\n",
    "> фраза «сложность алгоритма есть O(f(n))» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n);\n",
    "\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)\n",
    "\n",
    "**$\\Omega$ - нотация** - как и $O$- нотация - это асимптотическое ограничение функции, описывающей алгоритм, но уже снизу (не менее). В реальной жизни много чаще используется O - нотация.\n",
    "\n",
    "Стоит повторно ометить, что сложность алгоритма обычно принято описывать по члену с максимальной степени (при стремлении к бесконечности, степень возрастает быстрее, чем коэфициент). Например, если в $O$-нотации алгоритм работает за $O(n^3 + 8n + \\sqrt{9n})$ (какой-нибудь поиск на графе, в том числе социальном), то его запишут, как $O(n^3)$.\n",
    "\n",
    "**Почему важно?**\n",
    "- Крайне рекомендуется хотя бы в общих чертах понимать, что происходит под \"капотом\" Вашей \"машины\", если с ней возникают какие-то проблемы (слишком долго исполняется код, тратится вся оперативная память) и есть желание улучшить это (например, меньше времени ждать, пока обучается модель или понимать, почему выдается ошибка о, например, нехватке памяти). Есть риск, что проблема не в машине, а в неудачно выбранном для текущей задачи алгоритме.\n",
    "\n",
    "**Полезные ссылки:**\n",
    "- [Analysis of algorithms](https://en.wikipedia.org/wiki/Analysis_of_algorithms)\n",
    "- [Know Thy Complexities!](http://bigocheatsheet.com/)\n",
    "- [A Gentle Introduction to Algorithm Complexity Analysis](http://discrete.gr/complexity/) и [перевод в 4 статьях](https://habrahabr.ru/post/196226/) **(сюда стоит зайти)**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Сортировки"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Сортировка (англ. sorting) - **упорядочивание**, последовательное расположение объектов **в зависимости от выбранного критерия** (определяем этим критерием последовательность расположения, правило упорядочивания). **Примеры**: отсортировать по возрастанию, отсортировать так, чтобы на чётных местах объекты были расположены согласно убиванию их квадратных корней, а на нечётных согласно возрастанию их кубических значений.   \n",
    "\n",
    "[**Формулировка задачи сортировки**](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)\n",
    "\n",
    "**На что обратить внимание?**\n",
    "- Такие **алгоритмы сортировок**, как [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) (пример того, какими не эффективными могут быть сортировки)\n",
    "- **Условия применимости алгоритмов сортировки (и не только сортировки)**. Например, merge- или quicsort не всегда могут оказаться лучшим (самым быстрым, подходящим по по памяти), для Ваших данных или их структуры, алгоритмом.\n",
    "\n",
    "**Полезные ссылки:**\n",
    "- [Таблица сравнения сложности алгоритмов сортировки](https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms) **(сюда стоит зайти)**\n",
    "- Серия видео [AlgoRythmics\n",
    "](https://www.youtube.com/watch?v=XaqR3G_NVoo) - ансамбли, танцующие под классическую и народную музыку, своими движениями и перестановками визуализирующие алгоритмы. **(сюда стоит зайти)**\n",
    "- [Хороший пример времени выполнения разных алгоритмов сортировки](https://www.youtube.com/watch?v=ZZuD6iUe3Pc)\n",
    "- [Список алгоритмов сортировки](https://en.wikipedia.org/wiki/Sorting_algorithm) **(сюда стоит зайти)**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замерить время исполнения алгоритма в Jupiter'e можно, используя одну из следующих [магических команд](https://ipython.readthedocs.io/en/stable/interactive/magics.html) (рассмотрены на первом занятии) или с помощью модуля datetime** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Полезные ссылки:**\n",
    "- [Ссылка 1](http://pynash.org/2013/03/06/timing-and-profiling/)\n",
    "- [Ссылка 2](https://stackoverflow.com/questions/32565829/simple-way-to-measure-cell-execution-time-in-ipython-notebook)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def big_loop():\n",
    "    i = 0\n",
    "    while i < 10000000:\n",
    "        i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4 µs, sys: 0 ns, total: 4 µs\n",
      "Wall time: 7.87 µs\n"
     ]
    }
   ],
   "source": [
    "# измеряет время\n",
    "%time {big_loop()}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "661 ms ± 113 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "# запускает ячейку n раз, замеряя среднее время выполнения и выводя его в приятном виде\n",
    "big_loop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "runtime: 0:00:00.515888\n"
     ]
    }
   ],
   "source": [
    "#с помощью модуля datetime\n",
    "class timeit():\n",
    "    from datetime import datetime\n",
    "    def __enter__(self):\n",
    "        self.tic = self.datetime.now()\n",
    "    def __exit__(self, *args, **kwargs):\n",
    "        print('runtime: {}'.format(self.datetime.now() - self.tic))\n",
    "        \n",
    "with timeit():\n",
    "    # your code, e.g., \n",
    "    big_loop()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}