{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "# MLClass. \"Прикладной анализ данных\"\n", "# Модуль \"Инструментарий Data Science\"\n", "\n", "\n", "## Автор материала: Юрий Кашницкий, ФКН НИУ ВШЭ\n", "
\n", "Материал распространяется на условиях лицензии Ms-RL. Можно использовать в любых целях, кроме коммерческих, но с обязательным упоминанием автора материала." ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Урок 5. Функции. Рекурсия\n", "## Часть 2. Рекурсивные функции" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Python 2 and 3 compatibility\n", "# pip install future\n", "from __future__ import (absolute_import, division,\n", " print_function, unicode_literals)\n", "from builtins import *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Рекурсивная функция - это функция, которая в теле вызывает сама себя." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Пример.** Вычисление факториала (итеративная версия)" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def factorial_iter(n):\n", " k = 1\n", " for i in range(2, n + 1):\n", " k *= i\n", " return k" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 1\n", "2 2\n", "3 6\n", "4 24\n", "5 120\n", "6 720\n", "7 5040\n", "8 40320\n", "9 362880\n" ] } ], "source": [ "for i, k in enumerate(range(1, 10)):\n", " print(i+1, factorial_iter(k))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Временная сложность - линейная по n. " ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "100 loops, best of 3: 3.55 ms per loop\n" ] } ], "source": [ "%timeit factorial_iter(3200)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Пример.** Вычисление факториала (рекурсивная версия)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 1\n", "2 2\n", "3 6\n", "4 24\n", "5 120\n", "6 720\n", "7 5040\n", "8 40320\n", "9 362880\n" ] } ], "source": [ "def factorial_recur(n):\n", " if n == 1:\n", " return 1\n", " else:\n", " return n * factorial_recur(n-1)\n", "\n", "# n! = n * (n-1)!\n", "# 4! = 4 * 3 * 2 * 1 = 24\n", "for i, k in enumerate(range(1, 10)):\n", " print(i+1, factorial_recur(k))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Временная сложность - линейная по n. " ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "100 loops, best of 3: 4.98 ms per loop\n" ] } ], "source": [ "from sys import setrecursionlimit\n", "setrecursionlimit(1000000)\n", "%timeit factorial_recur(3200)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Пример.** Вычисление элементов последовательности Фибоначчи (итеративная версия) " ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def fib_iter(n):\n", " a, b = 1, 1\n", " for i in range(n):\n", " a, b = b, a + b\n", " return a" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, " ] } ], "source": [ "for i in range(11):\n", " print(fib_iter(i), end=\", \")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Временная сложность - линейная по n. " ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "100000 loops, best of 3: 2.71 µs per loop\n" ] } ], "source": [ "%timeit fib_iter(20)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Пример.** Вычисление элементов последовательности Фибоначчи (рекурсивная версия) " ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def fib_recur(n):\n", " if n <= 1:\n", " return 1\n", " else:\n", " return fib_recur(n - 1) + fib_recur(n - 2)" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, " ] } ], "source": [ "for i in range(11):\n", " print(fib_recur(i), end=\", \")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Временная сложность - экспоненциальная по n. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Доказательство** (метод математической индукции)\n", "\n", "Уравнение рекурии $T(n) = T(n-1) + T(n-2) + O(1)$. Обозначение O - пояснение на Википедии\n", "\n", "$T(n \\leq 1) = O(1)$\n", "\n", "Пусть $T(n - 1) = O(2^{n-1})$\n", "\n", "Тогда $T(n) = T(n-1) + T(n-2) + O(1) = O(\\frac{2^{n}}{2}) + O(2^{n-2}) + O(1) = O(2^n)$" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 loops, best of 3: 1min 22s per loop\n" ] } ], "source": [ "%timeit fib_recur(40)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Пример**. Метод сортировки QuickSort" ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def qs(a_list):\n", " if len(a_list) <= 1:\n", " return a_list\n", " else:\n", " el0 = a_list[0]\n", " left, right = [], []\n", " for elem in a_list[1:]:\n", " if elem < el0:\n", " left.append(elem)\n", " else:\n", " right.append(elem)\n", " return qs(left) + [el0] + qs(right)\n", " " ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[4, 5, 6, 7, 8, 9]" ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" } ], "source": [ "qs([9, 8, 7, 6, 5, 4])" ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from random import choice\n", "\n", "def quick_sort(a_list):\n", " if len(a_list) <= 1:\n", " return a_list\n", " pivot = choice(range(len(a_list)))\n", " return quick_sort([i for i in a_list[:pivot] + a_list[pivot+1:] \n", " if i < a_list[pivot]]) + [a_list[pivot]] + \\\n", " quick_sort([i for i in a_list[:pivot] + a_list[pivot+1:] \n", " if i >= a_list[pivot]])" ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3, 4, 6]" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quick_sort([3, 4, 2, 1, 6])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Временная сложность - $O(n*log(n))$" ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10000 loops, best of 3: 60.3 µs per loop\n" ] } ], "source": [ "%timeit quick_sort([3, 4, 2, 1, 6, 145, 56, 23, 45, 234, 21])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Примеры дерева рекурсии QuickSort\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Опорный элемент - всегда нулевой\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "T(n) = 2*T(n/2) + O(n)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "При случайном выборе опорного элемента\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Реализация, мимимизирующая потребление дополнительной памяти " ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import random\n", "\n", "def sub_partition(array, start, end, idx_pivot):\n", "\n", " 'returns the position where the pivot winds up'\n", "\n", " if not (start <= idx_pivot <= end):\n", " raise ValueError('idx pivot must be between start and end')\n", "\n", " array[start], array[idx_pivot] = array[idx_pivot], array[start]\n", " pivot = array[start]\n", " i = start + 1\n", " j = start + 1\n", "\n", " while j <= end:\n", " if array[j] <= pivot:\n", " array[j], array[i] = array[i], array[j]\n", " i += 1\n", " j += 1\n", "\n", " array[start], array[i - 1] = array[i - 1], array[start]\n", " return i - 1\n", "\n", "def quicksort_inplace(array, start=0, end=None):\n", "\n", " if end is None:\n", " end = len(array) - 1\n", "\n", " if end - start < 1:\n", " return\n", "\n", " idx_pivot = random.randint(start, end)\n", " i = sub_partition(array, start, end, idx_pivot)\n", " #print array, i, idx_pivot\n", " quicksort_inplace(array, start, i - 1)\n", " quicksort_inplace(array, i + 1, end)" ] }, { "cell_type": "code", "execution_count": 68, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3, 4, 6, 7]" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a_list = [3, 4, 2, 1, 6, 7]\n", "quicksort_inplace(a_list)\n", "a_list" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "**Пример**. Простая визуализация бинарного дерева" ] }, { "cell_type": "code", "execution_count": 72, "metadata": { "collapsed": false }, "outputs": [], "source": [ "class BinaryTree:\n", " def __init__(self, rootObj):\n", " self.root = rootObj\n", " self.leftChild = None\n", " self.rightChild = None\n", "\n", " def insertLeft(self, newNode):\n", " if self.leftChild == None:\n", " self.leftChild = BinaryTree(newNode)\n", " else:\n", " t = BinaryTree(newNode)\n", " t.leftChild = self.leftChild\n", " self.leftChild = t\n", "\n", " def insertRight(self,newNode):\n", " if self.rightChild == None:\n", " self.rightChild = BinaryTree(newNode)\n", " else:\n", " t = BinaryTree(newNode)\n", " t.rightChild = self.rightChild\n", " self.rightChild = t\n", "\n", " def getRightChild(self):\n", " return self.rightChild\n", "\n", " def getLeftChild(self):\n", " return self.leftChild\n", "\n", " def setRootVal(self,obj):\n", " self.root = obj\n", "\n", " def getRootVal(self):\n", " return self.root\n", " \n", " def __str__(self):\n", " output = str(self.root)\n", " if self.leftChild:\n", " output = '/'.join([self.leftChild.__str__(), output]) \n", " else:\n", " output = '[' + output\n", " if self.rightChild:\n", " output = '\\\\'.join([output, self.rightChild.__str__()]) \n", " else:\n", " output = output + ']'\n", " return output" ] }, { "cell_type": "code", "execution_count": 73, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Root: a\n", "Left child: [b]\n", "Tree: [b]/a\\[c]\n", "Tree: [d]/b\\[e]/a\\[c]\n", "Tree: [d]/b\\[e]/a\\[f]/c\\[g]\n" ] } ], "source": [ "r = BinaryTree('a')\n", "r.insertLeft('b')\n", "r.insertRight('c')\n", "print(\"Root:\", r.getRootVal())\n", "print(\"Left child:\", r.getLeftChild())\n", "print(\"Tree:\", r)\n", "r.getLeftChild().insertLeft('d')\n", "r.getLeftChild().insertRight('e')\n", "print(\"Tree:\", r)\n", "r.getRightChild().insertLeft('f')\n", "r.getRightChild().insertRight('g')\n", "print(\"Tree:\", r)\n", "\n", "# a\n", "# / \\\n", "# b c\n", "# / \\ / \\\n", "# d e f g" ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.10" }, "name": "4_Functions.ipynb" }, "nbformat": 4, "nbformat_minor": 0 }