Skip to content

Instantly share code, notes, and snippets.

@jabooth

jabooth/Introduction to Python for Algorithms 202.ipynb

Last active August 29, 2015 14:14
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jabooth/650658a4a34435636c6a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jabooth/650658a4a34435636c6a to your computer and use it in GitHub Desktop.
Download ZIP
Introduction to Python for Algorithms 202
Display the source blob
Display the rendered blob
Raw
Introduction to Python for Algorithms 202.ipynb
{
"metadata": {
"name": "",
"signature": "sha256:aad1efffdecd7de47c6305c2d13208f2a620ea76fca79378089b99b67b5ef499"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Introduction to Python for Algorithms 202"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*by James Booth*"
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Getting set up"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To use this notebook, you'll first need to install miniconda. To get set up you can follow the start of the [instructions given here for Windows, OS X, and Linux](http://www.menpo.org/installation/). Only go as far as 'Setting Up A Fresh Environment' then jump back here to install the stuff we need (not menpo).\n",
"\n",
"- Create a Python environment with all the code we need in it\n",
"\n",
"```\n",
"> conda create -n algo202 python=3 pip matplotlib ipython-notebook\n",
"```\n",
"- Activate the environment. On OS X/Linux thats:\n",
"```\n",
"> source activate algo202\n",
"```\n",
"and on Windows...\n",
"```\n",
"> activate algo202\n",
"```\n",
"- Finally install the line_profiler tool (you can read more about that at our [blog post](http://www.menpo.org/blog/2014/05/line_profiler_ipython/))\n",
"```\n",
"(algo202) > pip install --pre line_profiler\n",
"```\n",
"- Now we are all set up. In the future you only need to reactivate the environment to get to work. To run this notebook, launch an IPython notebook server, and browse to this downloaded file\n",
"```\n",
"(algo202) > ipython notebook\n",
"```"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {
"internals": {
"slide_type": "subslide"
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Basics"
]
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Outputting state"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print('hello world')"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"hello world\n"
]
}
],
"prompt_number": 1
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Variable definitions"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# dynamic typing\n",
"x = 1\n",
"y = 2\n",
"z = x + y\n",
"print(z)"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"3\n"
]
}
],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# string literals\n",
"hello = \"'ello\"\n",
"world = 'world!'\n",
"print(hello + \" \" + world)"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"'ello world!\n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# strong typing\n",
"# x + hello # TypeError!\n",
"\n",
"# explictly cast to show our intent\n",
"str(x) + \". \" + hello # no complaining"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 4,
"text": [
"\"1. 'ello\""
]
}
],
"prompt_number": 4
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Formatting strings"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# for building strings though we normally use format\n",
"# (simple template system - replaces '{}' with input)\n",
"s = \"{}): {} {}\".format(x, hello, world)\n",
"print(s)\n",
"\n",
"# no need to build the string seperately..\n",
"print(\"{}): {} {}\".format(x, hello, world))"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"1): 'ello world!\n",
"1): 'ello world!\n"
]
}
],
"prompt_number": 5
},
{
"cell_type": "heading",
"level": 3,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Data structures"
]
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"List"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# literal\n",
"l = ['a', 'b', 'c', 'd', 'e']\n",
"print('l: {}'.format(l))\n",
"\n",
"# indexing\n",
"print('the first element is: ' + l[0])\n",
"print('the last element is: ' + l[-1])\n",
"print('the second-to-last element is: ' + l[-2])"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"l: ['a', 'b', 'c', 'd', 'e']\n",
"the first element is: a\n",
"the last element is: e\n",
"the second-to-last element is: d\n"
]
}
],
"prompt_number": 6
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# slicing\n",
"print('cutting off the ends: {}'.format(l[1:-1]))\n",
"print('first three: {}'.format(l[:3]))\n",
"print('last two: {}'.format(l[-2:]))"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"cutting off the ends: ['b', 'c', 'd']\n",
"first three: ['a', 'b', 'c']\n",
"last two: ['d', 'e']\n"
]
}
],
"prompt_number": 7
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# mutability - pass by *object* reference\n",
"l2 = l\n",
"# l2 is another name that points to the same object in\n",
"# memory as l -> changing l2 changes l\n",
"l[4] = 2\n",
"print('l is now: {}'.format(l))\n",
"print('l2 is now: {}'.format(l2))"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"l is now: ['a', 'b', 'c', 'd', 2]\n",
"l2 is now: ['a', 'b', 'c', 'd', 2]\n"
]
}
],
"prompt_number": 8
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# but notice the difference from pass by reference\n",
"l2 = 1\n",
"# the name 'l2' is now pointed to a different object\n",
"print('l is now: {}'.format(l))\n",
"print('l2 is now: {}'.format(l2))\n",
"# so l is not affected."
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"l is now: ['a', 'b', 'c', 'd', 2]\n",
"l2 is now: 1\n"
]
}
],
"prompt_number": 9
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Dictionary (HashMap)"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# literal \n",
"d = {1: 'one', \n",
" 2: 'two', \n",
" \"three\": 3}\n",
"print('d: {}'.format(d))\n",
"\n",
"# item retrieval\n",
"print('d[1]: {}'.format(d[1]))\n",
"print('d[2]: {}'.format(d[2]))\n",
"print('d[\"three\"]: {}'.format(d[\"three\"]))"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"d: {1: 'one', 2: 'two', 'three': 3}\n",
"d[1]: one\n",
"d[2]: two\n",
"d[\"three\"]: 3\n"
]
}
],
"prompt_number": 10
},
{
"cell_type": "heading",
"level": 3,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Flow of control"
]
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"`for` loop"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# use range(n) to iterate from 0 -> n-1\n",
"for i in range(3):\n",
" print(i)"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n",
"1\n",
"2\n"
]
}
],
"prompt_number": 11
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# we can also set the start and step size\n",
"for i in range(1, 3):\n",
" print(i)"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n",
"2\n"
]
}
],
"prompt_number": 12
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# jump by 25\n",
"for i in range(0, 76, +25):\n",
" print(i)"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n",
"25\n",
"50\n",
"75\n"
]
}
],
"prompt_number": 13
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# go backwards\n",
"for i in range(75, -1, -25):\n",
" print(i)"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"75\n",
"50\n",
"25\n",
"0\n"
]
}
],
"prompt_number": 14
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Side note - use ? to find out what a function does"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# note this is IPython specific!\n",
"range?"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [],
"prompt_number": 15
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Side note - use shift + tab to see this inline"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"range(# hit shift + tab immediately after '('"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": []
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"if else elif"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"i = 5\n",
"\n",
"if i == 2:\n",
" print('wahoo i is 2!')\n",
"elif i == 3:\n",
" print('hmm i is 3..')\n",
"else:\n",
" print('sadly, i is not 2...')"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"sadly, i is not 2...\n"
]
}
],
"prompt_number": 17
},
{
"cell_type": "heading",
"level": 3,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Concepts"
]
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"size"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# Collections have a size we can query with len(x)\n",
"print('len(l) = {}'.format(len(l)))\n",
"print('len(d) = {}'.format(len(d)))"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"len(l) = 5\n",
"len(d) = 3\n"
]
}
],
"prompt_number": 18
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"iteration"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# Containers are all iterable (you can for loop them)\n",
"print('Looping over l:')\n",
"for x in l:\n",
" print(x)"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Looping over l:\n",
"a\n",
"b\n",
"c\n",
"d\n",
"2\n"
]
}
],
"prompt_number": 19
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print('Iterating over a dictionary iterates the keys:')\n",
"for k in d:\n",
" print(k)"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Iterating over a dictionary iterates the keys:\n",
"1\n",
"2\n",
"three\n"
]
}
],
"prompt_number": 20
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"the power of iterators"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"#\u00a0So was range a list?\n",
"print('does range(4) == [0, 1, 2, 3]?: '\n",
" '{}'.format(range(4) == [0, 1, 2, 3]))\n",
"\n",
"# Nope, range is a iterator - it generates the next value \n",
"# dynamically as it is requested. This way we don't need \n",
"# all the things we want to iterate over in memory\n",
"\n",
"# no memory cost\n",
"summation = 0\n",
"for i in range(1, 10 ** 8 + 1):\n",
" summation += i\n",
"print('summation over [1,..., 10 ** 8] = {}'.format(summation))"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"does range(4) == [0, 1, 2, 3]?: False\n",
"summation over [1,..., 10 ** 8] = 5000000050000000"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
}
],
"prompt_number": 21
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# a list with 10 ** 8 elements in RAM!\n",
"# boy this is expensive (check your RAM usage)\n",
"range_as_list = list(range(1, 10 ** 8 + 1))\n",
"\n",
"summation = 0\n",
"for i in range_as_list:\n",
" summation += i\n",
"print('summation over [1, ..., 10 ** 8] = {}'.format(summation))"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"summation over [1, ..., 10 ** 8] = 5000000050000000\n"
]
}
],
"prompt_number": 22
},
{
"cell_type": "heading",
"level": 3,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"building functions"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# let's write a bubble sort!\n",
"\n",
"def bubble_sort(a):\n",
" n = len(a)\n",
" for i in range(n):\n",
" for j in range(n - 1, i - 1, -1):\n",
" if a[j] < a[j - 1]:\n",
" a[j], a[j - 1] = a[j - 1], a[j]\n",
" return a"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [],
"prompt_number": 23
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# let's try our implementation\n",
"l = [-1, 4, 1, 2, 8]\n",
"bubble_sort(l)"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 24,
"text": [
"[-1, 1, 2, 4, 8]"
]
}
],
"prompt_number": 24
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# interestingly we can sort letters too..\n",
"l = ['b', 'w', 'a', 'd']\n",
"\n",
"bubble_sort(l)"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 25,
"text": [
"['a', 'b', 'd', 'w']"
]
}
],
"prompt_number": 25
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# to convert a string to a list is trivial\n",
"bubble_sort(list('helloworld'))"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 26,
"text": [
"['d', 'e', 'h', 'l', 'l', 'l', 'o', 'o', 'r', 'w']"
]
}
],
"prompt_number": 26
},
{
"cell_type": "heading",
"level": 3,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Measuring performance"
]
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Generating some data"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import random\n",
"\n",
"# lambdas are just one line functions\n",
"\n",
"# make us a random list length (between 1 - 2000)\n",
"rand_len = lambda: random.randint(1, 2e3)\n",
"\n",
"# choose a random value for a list element (between 0 1e6)\n",
"rand_int = lambda: random.randint(0, 1e6)\n",
"\n",
"# generate a random list of random length -\n",
"# here we use a list comprehension, a very tidy\n",
"# way of transforming lists of data\n",
"rand_list = lambda: [rand_int() \n",
" for i in range(rand_len())]"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [],
"prompt_number": 27
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# test our rand_list() function\n",
"# peek at the first 5 elements\n",
"rand_list()[:5] # hit ctrl + enter to run this cell many times"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 28,
"text": [
"[16975, 177447, 395636, 451669, 825106]"
]
}
],
"prompt_number": 28
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# check lists are randomly sized\n",
"len(rand_list()) # hit ctrl + enter to run this cell many times"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 29,
"text": [
"618"
]
}
],
"prompt_number": 29
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# build 100 lists to test\n",
"random_lists = [rand_list() for i in range(100)]"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 30
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# IPython has a very convienient timer module!\n",
"# chooses how many times to repeat based on how\n",
"# long the execution time is and averages for us\n",
"%timeit bubble_sort([0, 1, 2, 3])s\n",
"\n",
"# but we want to programatically record the\n",
"# timings..."
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"100000 loops, best of 3: 4.65 \u00b5s per loop\n"
]
}
],
"prompt_number": 31
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# on a longer input the %timeit does many less\n",
"# loops to keep running time sensible\n",
"%timeit bubble_sort(random_lists[10])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"100 loops, best of 3: 13.3 ms per loop\n"
]
}
],
"prompt_number": 33
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Making a quick timer"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import time\n",
"\n",
"def time_f(f):\n",
" before = time.clock()\n",
" f()\n",
" after = time.clock()\n",
" return after - before"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [],
"prompt_number": 34
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"t = []\n",
"n = []\n",
"\n",
"# test our bubble sort - record the time (t) it took to\n",
"# run and the length of the input (n)\n",
"for r_list in random_lists:\n",
" # lambdas are very convienient here (we want\n",
" # to delay the invocation of the function).\n",
" # notice we are passing a *function*, not it's\n",
" # result (fuctions are first class citizens in\n",
" # Python)\n",
" t.append(time_f(lambda: bubble_sort(r_list)))\n",
" n.append(len(r_list))"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [],
"prompt_number": 35
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%matplotlib inline\n",
"from matplotlib import pyplot as plt\n",
"plt.scatter(n, t)\n",
"plt.xlabel('n')\n",
"plt.ylabel('time (/s)')\n",
"plt.xlim(0)\n",
"plt.ylim(0)"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 36,
"text": [
"(0, 0.50000000000000011)"
]
},
{
"metadata": {},
"output_type": "display_data",
"png": "iVBORw0KGgoAAAANSUhEUgAAAYoAAAEPCAYAAABcA4N7AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAH/5JREFUeJzt3X90XWWd7/H3N22jcSh3SDMLBGrhtghSa0lYw48pLuKV\nJK1LgrU6wAgT6iwKLhChh1I7BSnSrFolwHXJCEUGMzhMZylTJ8yV7gYv6TVzHbEQK2KLVKFDqXQo\nRS9o9FDyvX/sneTkJDk9Sc4+Pz+vtc7q2fvsnDxnr0O+PM/3eb6PuTsiIiLjqSp0A0REpLgpUIiI\nSEYKFCIikpEChYiIZKRAISIiGSlQiIhIRrEGCjNbbGa7zex5M1s9xuuNZvZbM+uLHjfH2R4REZm4\n6XG9sZlNA74GXAC8DPzYzLrcfVfapdvdvTWudoiIyNTE2aM4C9jj7i+6+1vAZuCiMa6zGNsgIiJT\nFGegOAF4KeV4X3QulQN/YWY7zex7ZnZ6jO0REZFJiG3oiTAIHMnTwGx3/72ZLQG+C7w3xjaJiMgE\nxRkoXgZmpxzPJuxVDHH3N1KeP2Zmf2dmte5+KPU6M1NBKhGRSXD3KQ/vxzn0tAM4xcxOMrNq4GKg\nK/UCMzvWzCx6fhZg6UFikLvr4c6tt95a8DYUy0P3QvdC9yLzI1di61G4+2EzuxYIgGnAA+6+y8yu\nil6/D/gE8BkzOwz8HrgkrvaIiMjkxDn0hLs/BjyWdu6+lOf3APfE2QYREZkarcwuMY2NjYVuQtHQ\nvRimezFM9yL3LJfjWHExMy+FdoqIFBMzw4s8mS0iImVAgUJERDJSoBARkYwUKEREJCMFChERyUiB\nQkREMlKgEBGRjBQoREQkIwUKERHJSIFCREQyUqAQEZGMFChERCQjBQoREclIgUJESlYQBDQ3L6O5\neRlBEBS6OWVLZcZFpCQFQcDSpW30928EoKZmNVu2dNLS0lLglhWPXJUZV6AQkZLU3LyM7u5WoC06\n00lTUxfbtj1SyGYVFe1HISIieRHrntkiInFJJFbQ29tGf394XFOzmkSis7CNKlMaehKRkhUEAR0d\nm4AwcCg/MZJyFCIikpFyFCIikhcKFCIikpEChYiIZKRAISIiGSlQiIhIRgoUIiKSkQKFiIhkpEAh\nIiIZKVCIiEhGChQiIpKRAoWIFCVtSlQ8VOtJRIpOEAS0tl5OMvkVAKqrV9HV9ZCK/k2QigKKSNlq\naGikr285qZsS1dc/yNNP9xSwVaVHRQFFpGzt2fOrUef27t1XgJYIxBwozGyxme02s+fNbHWG6/7c\nzA6b2cfjbI+IFL8gCHjjjVeB64DO6HEdxxzzjsI2rILFtsOdmU0DvgZcALwM/NjMutx91xjXbQS2\nAlPuIolIaQs3IjoDWAR0RWev5OijdxSuURUuzh7FWcAed3/R3d8CNgMXjXHdZ4HvAK/G2BYRKTkL\ngEeixwLq6mYVuD2VK85AcQLwUsrxvujcEDM7gTB4fD06pYy1SIVLJFZQXb0buJHBoafq6lUkEisK\n3LLKFdvQE9n90b8b+Ly7u5kZGYae1q1bN/S8sbGRxsbGqbZPRIpQS0sLXV2bWbPmdvbuvZ05c05k\nwwZNjc1GT08PPT09OX/f2KbHmtk5wDp3XxwdrwEG3H1jyjW/Yjg41AG/B650966099L0WBGRCSr6\ndRRmNh14DvgwsB94Erg0PZmdcv2DwKPu/i9jvKZAISIyQUW/jsLdDwPXAgHwc+Cf3X2XmV1lZlfF\n9XtFpLQEQUBDQyOzZs2joeE8lesoQlqZLSIFk16qA26kuvowXV2blZPIgaIfesolBQqR8tTcvIzu\n7lZSS3XAvTQ1Hc+2bY8UsGXloeiHnkRExjNYGfapp3YWuimShTinx4qIjBIEAUuXttHfvxE4mbBU\nx6Bw6CmRWFeYxsmYFChEJHZBEESlOeDgwQNRkGgben3mzC8wY8YM5sw5lQ0bblF+osgoUIhIrEb2\nIKCq6gbgmZQrFnDOOS8oJ1HEFChEJFYdHZtG9CAGBqCqKsHAwAIAampWk0h0FrCFciQKFCKSdwsX\nvp+6urAAQyLRqaGmIqfpsSISq/Shp5qa1WzZouCQD1pHISIlIzWZnUisUJDIEwUKERHJSAvuRKSo\nDC6ia25epnpNZUaBQkSmbDAP0d3dSnd3K0uXtg0FCwWQ0qdZTyIyZelTYPv7GcpJpCaye3vblMgu\nQQoUIhKb8QKIAkVp0dCTiExZuM/19cC5wLlUV1+vPa7LiHoUIpIjM4Cro+ergDCA9Pa20d8fntUq\n7NKk6bEiMmVj7SvR1NTFtm2PaA1FAeVqeqx6FCISq5aWFgWHEqdAISJTpiGm8qahJxGZsLGGkzTE\nVHxUwkNECkJF/kqHSniISN4FQcBf/dU19PefDBwHhAFjsCch5UmBQkSyMtiTOHToY9GZTwHthWyS\n5ImS2SKSlXCV9WXAt4CN0dnrqa6GRGJzAVsmcVOgEJEJ+HfCINE2dGb+/AeVnyhzGnoSkawkEiuo\nqnq+0M2QAlCgEJGstLS08MUv3oDZ9UBn9LiRZ5/dqfLhZU7TY0VkQhoazqOv723geGAF8MpQuQ4p\nLpoeKyJ5kb7xUF3dsYTF/x4BlJuoBEpmi8i40hfX9fa2sXbtZ+ntXa1yHRVEgUJExjXWxkPbt3ex\nZUtnSrkOrcoudwoUIjJhqghbWRQoRGRc55/fwPe/fwMDA+GxhpkqkwKFiIwSBAFr1mxg586fMTDw\nP4B7qap6nrVrb1BPogJp1pOIAGFwaGg4j5kzj2fJkkvo61vOwEAH0AusY2Cgg+3bny50M6UAYu1R\nmNli4G5gGvANd9+Y9vpFwBeBgeixyt3/d5xtEpHRgiCgtfUSksnpwDzC6a9tKVdsAloL0jYpvNh6\nFGY2DfgasBg4HbjUzN6Xdtnj7r7Q3euBKwi/jSISo/R1ERDObkomTwPuIFxIl25/lJ9Ykc+mSpGI\ns0dxFrDH3V8EMLPNwEXArsEL3P13KdcfBRyMsT0iFW+sdRFbtqQnp1eQ2pswu54zzpjPhg2aBlup\n4gwUJwAvpRzvA85Ov8jMPgZsAN4NNMfYHpGKN9a6iI6OTSQSK9i+/RKSyRsJexWXASuB4znjjPk8\n/XRv4RotBRdnMjur4kzu/l13fx9wIfBQjO0RkTEcPHiAjo5NzJ+/kHe+cwC4GdgBPAzcGJXskEoW\nZ4/iZWB2yvFswl7FmNz9B2Y23cxmuftr6a+vW7du6HljYyONjY25a6lIhUgkVtDb2zZUfqO6+nqe\nfXYGyeSV0fEqqqvfJJlcDryidRMlpqenh56enpy/b2zVY81sOvAc8GFgP/AkcKm770q5Zi7wK3d3\nM2sAvu3uc8d4L1WPFcmRIAiGym8cPPgafX3LGc5JdFJf/yB1dbOAMLAoL1G6clU9NqsehZn9CWGP\nwIF9aUnoMbn7YTO7FggIp8c+4O67zOyq6PX7gGXAX5vZW8CbwCWT+xgikq3U8hvNzctGvV5XN0sl\nw2WEcQOFmc0EriT8410HHAAMONbMXgP+Ebjf3d8c7z3c/THgsbRz96U8/zLw5al8ABGZnCAIOHjw\nAFVVKtEhmWXqUXwX2Axc6O4HUl8ws+MIV9/8K+HQkoiUkJHTZJ+hqirBwoXv1xRYGZN2uBMpQ6l5\niLHyDM3Ny+jubiU1N6Fd6spP3na4M7PzzOyo6PnlZnaXmc2Z6i8WkXgM9ha6u1vp7m5l6dI27Wkt\nU5LNOoqvA78zs4WEK3D2AP8Qa6tEZNJGLqoLh5cGexeDEokV1NSsBjqBTpXnkIyyCRSHo3GfjwH3\nuPs9wMx4myUicWppaWHLlnC4qakp3LFOuQkZzxFzFGb2f4CtwHLgg8CrwE/cfUH8zRtqg3IUIllK\nr+dUU7NagaBC5S1HAVwM/BH4tLu/QljD6StT/cUiEo/B3kJ9/f3U1t7OaaedVugmSYkbN1CYWWBm\nNwD/zd073P0HAO7+n+6uHIVIkdu9ew+HDt1CX99yJbRlSsYdejKzdxPuJdECnAr8iHDx3OPZrMzO\nJQ09iUyMpr8K5KGEh7v/GngQeDDahOhsYAlwk5n9AQiildUiIlLGsqr15O5vA/83etxiZn+G9o4Q\nKQrpi+sAleaQnMo09LQO+Hp6+Y6U198NXO3ut8bXvKHfpaEnkTGkz3Cqrr4emEEy+RXC0hzfjEpz\nrNGspwqUj+qxO4DNZlYNPA38mrAo4HFAA+FMqDum2gARmbz0HeuSyXuBq4eOBwYWUFfXpSAhU5Ip\nR/FvwL+Z2WxgEfCe6KVeYKO7j7sJkYiIlI8j5ijc/SXCKrIiUmTCva4vJ5kMj6dP30VV1aqhY+Um\nJBfi3ApVRPLiLeBeAKqqjC984XNs394FQCKhFdkydSozLlLCGhrOo6/vbeB4YAXwitZLyJC8boUq\nIsUnCAJ27vw5cFd0pg24rIAtknJ1xEBhZqcCfwcc5+7zzewDQKu7r4+9dSIyro6OTQwM3MXw6muo\nqkqQSPxj4RolZSmbooD3A38LROkxngEuja1FIjJpCxe+XzkJyblshp7e5e4/MguHudzdzeyteJsl\nIkeSSKygt7eN/v7wuKZmNRs2aIaT5F42geJVM5s3eGBmnyBcfCciBTRYTny4fIdmOEk8stm4aC6w\nCfgL4HXgBeBT7v5i7K0bboNmPYmITFDeNi5y91+6+4eBOuBUd1+UzyAhUsmCIKC5eRnNzcu0n4QU\nTDY9imOAvwZOYnioyt39unibNqIN6lFIxdGWpjJV+VxH8T3gh8BPgQHCwoD6qy0Ss/SCf/394TkF\nCsm3bALFO9x9ZewtERGRopRNoHjYzFYAjxKWFgfA3Q/F1ioRGXP6qwr8SSFkk6O4FmgHfkM49ARh\njuK/x9y21DYoRyEVKX33Og07yUTkKkeRTaB4Afhzdz841V82WQoUIiITl7fpscDzQP9Uf5GIiJSm\nbHIUvwd+YmZPMJyjyOv0WJFypyEmKWbZDD1dMcZpd/e8ZdU09CTlTOslJC55y1EUAwUKKWfNzcvo\n7m5luFx4pzYfkpyIfcGdmX3b3T9pZs+M8bK7+wem+stFRKT4ZcpRfC7696OEq7FT6X/vRaYgNSdx\n/vkN9Pau1noJKVrZ5Cg2uvvqI53L8POLgbuBacA33H1j2uufAm4iDEZvAJ9x95+mXaOhJykbY+Uk\n1q79LNu3Pw0omS25k891FH3uXp927hl3X3DENzebBjwHXAC8DPwYuNTdd6Vccy7wc3f/bRRU1rn7\nOWnvo0AhZUM5CcmX2NdRmNlnovzEqWb2TMrjRcICgdk4C9jj7i+6+1vAZuCi1Avc/Yfu/tvo8EfA\niRP+FCIlYLBk+FNP7Sx0U0QmJFOO4mHgMeBLwGqG8xRvuPtrWb7/CcBLKcf7gLMzXP83hNVqRUpO\nprUQI4ebTgaGlyEpJyHFbtxAEf1f/m+BS6bw/lmPF5nZh4BPA4um8PtECiI979Db2zZiLUR6yXCA\n2trbOfPMhdrCVIpeNiuzp+JlYHbK8WzCXsUIZvYB4H5gsbu/PtYbrVu3buh5Y2MjjY2NuWynyJRM\nfO+IBZx55gvKS0hO9fT00NPTk/P3jTtQ7ABOMbOTgP3AxcClqReY2XuAfwEuc/c9471RaqAQKTUq\nGS75kP4/0bfddltO3jf2ldlmtoTh6bEPuPsGM7sKwN3vM7NvAEuB/4x+5C13PyvtPTTrSYpaNmU4\nVM9J8k0lPESKjAKBFJt8lhkXkUkYnA7b3LyMIAgK3RyRSVOPQiQH0oeeqquvB2aQTH4FUEVYKQwN\nPYkUkdGrrc8Frkarr6WQNPQkUgTa29uZNWseTzzRCzxa6OaIxCLu6bEiZau9vZ2bb/4y8NXozHXA\nJ4ALqa7eDawimQxf0XRYKWUaehKZpFmz5nHo0C2kDi9Nn34TH/rQeSQSKwA0C0oKKvaNi0Rk4o4+\neuaIPISCg5QDBQqRCUhdK3HhhefR2XldyqvXsXLlTYVpmEiMNPQkQnaL5cZaff2Xf7mYRx/tBWDl\nyuWsXbs2f40WOQINPYnkyJEqvw4aq/Df/v1dvPbauCXKRMqCAoVUvIlXfhWpLAoUIllSBVipVMpR\nSMXLpvJr6rWa8iqlQiU8RHJIAUDKkQKFiIhkpFpPIiKSFwoUIiKSkQKFiIhkpEAhgnajE8lEyWyp\neBOZHitSSjTrSSRHRu9Op93opDxo1pPIBARBQEPDecyaNY+GhkYNL4lMgEp4SNkLgoDW1ktIJqcD\nd3DoELS2Xk5X10O0tLSoNIfIEWjoScpeOLS0H7ia8YaXtDJbypHKjItkIQgCnnpqJ/DHjNe1tLQo\nOIiMQ4FCytbI2UzPAMO70VVXryKReKhgbRMpJQoUUrbS95kAmD79JhYseB8bNjykHoRIlhQopIIs\n4EMfOk/TXkUmSIFCSl56IhrC3sTBgweorl5FMhlep9lMIpOjWU9S0trb27nlljtxfy+wiOnTv0lV\n1dskk3cDUF19PfPnL6SubpZmM0nF0awnqXhBEHDLLXfgfnd0ZjWHD18B/DuDeYlkEurqtMpaZCq0\nMltK1po1t+N+GtAFHAdsJAwSIpJL6lFISQqCgJ07fw7cFZ1pAy4DfoFZEvcwF6G8hMjUKVBIUTrS\nSumOjk0MDNxF6tRXuIHp05OsW7eG7du7op9VFViRqVKgkKKTXva7t7ctq7LfM2cexbe/fT8tLS2s\nXZuPlopUBs16kqKTTdlv7SEhcmQlUWbczBab2W4ze97MVo/x+mlm9kMz+4OZJeJsi5SXlpYWtmwJ\nA0hTU5eChEiMYutRmNk04DngAuBl4MfApe6+K+WaPwPmAB8DXnf3jnHeSz2KCqLegkhulEKP4ixg\nj7u/6O5vAZuBi1IvcPdX3X0H8FaM7ZASdNppp1Fbezv19fcrSIgUWJzJ7BOAl1KO9wFnx/j7pAyk\n9yb6+0eNWIpInsUZKHI6VrRu3bqh542NjTQ2Nuby7aVIpFd87e8Pz6lHIXJkPT099PT05Px94wwU\nLwOzU45nE/YqJiU1UIiIyGjp/xN922235eR94wwUO4BTzOwkYD9wMXDpONdOOdki5UH7V4sUn1jX\nUZjZEuBuYBrwgLtvMLOrANz9PjM7jnA21NHAAPAGcLq7v5n2Ppr1VEG0f7VIbuRq1pMW3ImIlKlS\nmB4rMiQIApqbl9HcvIwgCArdHBGZAPUoJHZBENDaegnJ5GkAVFfvpqtrs4aURGKmHoWUhCAI+OQn\nrySZrAIWAVeTTE5nzZrbC900EcmSAoXEJuxJXM4bb9wO3Al8i3CDoTvYu/eVwjZORLKmMuMSmzVr\nNpBMfoWRe0ZsAlqZM+fEArVKRCZKgUJyJn1a6969Y62v3E919So2bHgov40TkUlTMlsmLQgC1qzZ\nwN69+zjmmHexd++vOHx4ARAmrGfPns0vf/lr4I7oJ67nqKNq+M53HlQiWyQPcpXMVo9CJmUw/xAO\nLcGhQzcSlvdaBCwgmbwReJvq6sMkk/cCUF2NgoRICVKgkEnp6Ng0Rv7hXuAFBnsQr79+O11dm1OG\no9YpSIiUIAUKmZSDB1874jVz5pxIS0uLgoNIiVOgkAkLgoBnn90J3JhydiXwB8Khp04lrEXKiJLZ\nMmHNzcvo7m4lXBOxCdjPUUft5fOfv4bt258GVMxPpBgomS15kbmSa0v06OTcc7tYu3Yta9cWopUi\nEif1KGSUweBw8OBrPPvsTpLJu4Fwb4gtW8K9IVK3Kx08rx6ESHFRj0Jikb5ndZiHOA5oGdqWdNu2\nR9iypTOlp6EgIVLOFCgq2FjDSul7Voc2EQ4xDdNsJpHKoUBRodrb2/nCF+5iYOAUYBG9vW1Dw0qj\n7Qc6tS2pSIVSjqKCpOYe+vp+BJwRvbIb+Buaml4gkVgxYuipunoV8+e/l7q6YzWTSaTEKEchE3LF\nFVfQ2dkFnEq41qGPwXIbYR7ifwGn09LSkpZ/eEjBQaTCqUdR5oIg4JprVvLLX+4DvhqdXQ1cRlhu\n4xGgE1jJ1q0PKyiIlBH1KOSIhmcwzSAMEul1mY4fOpo79z0KEiIyJu1wV4KCIKC5eRnNzcsIgmDE\na+3t7cyaNY9Zs+ZxzTUro1zDO8Z4l93AyQyW27jnni/loeUiUoo09FRi0tc5pC52a29v5+abv8zw\nENN1QBNQD4w8f8EFZ2F2NKByGyLlKldDTwoUJWa4ztLgMFInTU1dbNv2CLNmzePQoVtGvBYW67sT\neBR4gpkzj2L16hWsVa0NkbKnHEXFCxgsyHfw4LRxr5o58yjOOacLgERCyWoRmTj1KEpMuLPcJSST\n0xncIKi6ehVdXQ+xY8eOUUNP69ffpN6DSIVSj6KMZarY2tLSwvz5C+nrW87gEFMyOVyDCeDOO28H\nYOVKBQkRmToFiiKTnqweLK2RGizq6maN+/NhqW8FBxHJHQWKIpDagzh48LURRfkGK7amBopEYgW9\nvW3094fHqsEkInFSoMijsYaU0nsQVVWJI77P6DIbKvMtIvFRMjtPxlv/0NGxKW26641UVf09AwN3\njbhOgUBEJkrJ7CI3XKn1ADCdvXv30d9/GelDSqMtYOHC04EH2bt3H3PmzMtjq0VERlMJjxwLgoCG\nhkY+8pFP0d1t9PU9R1/f8mghXCfh+odhicQKampWR6+Fez4sW7aE3bt3c+jQLfT1XcnSpW2jSnWI\niOSNuxf9I2xm8Vi/fr3X1s712tq5vn79+qHzW7du9ZqaYx2+GT1mRf969PimwzkO3/SammN969at\nQz/X1PRxb2r6+NDz9J9ravp4oT6uiJSo6G/nlP8Ga+gpS01NTTz++NPR0W+BBwC4+ebrgHBa6uht\nRO8d9T61ta9y5pldIxLQ6duKjj0kJSJSGLEGCjNbDNwNTAO+4e4bx7jmq8AS4PfAFe7eF2ebUrW3\nt3PnnQ8CcOGF57F//xvA6EVuYZB4kpHF9r4FdAPhArex1y4sAq4fOqqpWc3DDx85Ma3pryJSVHLR\nLRnrQRgc9gAnATOAnwDvS7vmI8D3oudnA/8xzntNuMs1OIRTX3++19cvGhrWGbR+/XqHo6MhnkTK\n85HDQmH3bawhpFlDz2tr5w79ztShp6qqY3zu3NO9vv78Ub8/2/an/9wTTzwx4XtRrnQvhuleDNO9\nGEaOhp7iDBTnAltTjj8PfD7tmnuBi1OOdwPHjvFeXls71+vrF/nWrVt969atXl+/KDp3/tC5wT+s\n69evT8sV1DkkRgSA2tq5KX/8M+cExg4UtdG/R4/KU4z1Bz5Xbr311py/Z6nSvRimezFM92JYrgJF\nnENPJwAvpRzvi3oNR7rmROBA+psdOnQLhw7dyEc/ugyYzuHDM4A7OHQIPvrRT1FV9TbJ5N0AfP/7\nCQYGOhi5o1sX/f0bR61yzsYFF9Tz+OPXpZy5DvgdNTVrWLt2ZD2l9HyDiEipizNQZLtCLn0xyDg/\nF/7RP3z4ZsJYcnXKOQg7J+HxwMDoJHK6lSuXDyWiw53ehgNBek6gu7s7ylOsBGDatCS33XabaiqJ\nSEWIbWW2mZ0DrHP3xdHxGmDAUxLaZnYv0OPum6Pj3cD57n4g7b1Ke1m2iEiBeJGvzN4BnGJmJwH7\ngYuBS9Ou6QKuBTZHgeU36UECcvNBRURkcmILFO5+2MyuJVyKPA14wN13mdlV0ev3ufv3zOwjZrYH\n+B2wPK72iIjI5JREUUARESmcoq71ZGaLzWy3mT1vZqsL3Z58MLMXzeynZtZnZk9G52rNrNvMfmFm\n28zsT1OuXxPdn91m1ly4lk+dmf29mR0ws2dSzk34s5vZmWb2TPTa/8z358iFce7FOjPbF303+sxs\nScpr5XwvZpvZE2b2rJn9zMyui85X3Hcjw72I97uRizm2cTzIYsFeOT6AF4DatHNfBm6Knq8GvhQ9\nPz26LzOi+7QHqCr0Z5jCZ/8gUA88M8nPPthDfhI4K3r+PWBxoT9bju7FrcDKMa4t93txHHBG9Pwo\n4DngfZX43chwL2L9bhRzj+IsYI+7v+jubwGbgYsK3KZ8SU/etxKWlyX692PR84uAf3L3t9z9RcIv\nwVl5aWEM3P0HwOtppyfy2c82s3cDM939yei6f0j5mZIxzr2A0d8NKP978Yq7/yR6/iawi3ANVsV9\nNzLcC4jxu1HMgWKsxXgnjHNtOXHgcTPbYWZXRueO9eHZYAeAY6PnxxPel0HleI8m+tnTz79Med2T\nz5rZTjN7IGWopWLuRTSLsh74ERX+3Ui5F/8RnYrtu1HMgaJSs+yL3L2esFDiNWb2wdQXPewnZro3\nZXvfsvjs5e7rhKtDzwB+DXQUtjn5ZWZHAY8An3P3N1Jfq7TvRnQvvkN4L94k5u9GMQeKl4HZKcez\nGRkBy5K7/zr691VgC+FQ0gEzOw4g6jL+V3R5+j06MTpXTiby2fdF509MO18W98Td/8sjwDcYHmYs\n+3thZjMIg8RD7v7d6HRFfjdS7sW3Bu9F3N+NYg4UQwv2zKyacMFeV4HbFCsze5eZzYye/wnQDDxD\n+LkHC1e1AYP/oXQBl5hZtZmdDJxCmKAqJxP67O7+CvD/zOxsMzPg8pSfKWnRH8NBSwm/G1Dm9yJq\n+wPAz9397pSXKu67Md69iP27Uegs/hEy/EsIs/p7gDWFbk8ePu/JhDMUfgL8bPAzA7XA48AvgG3A\nn6b8zN9G92c30FLozzDFz/9PhKv4k4T5qeWT+ezAmdF/KHuArxb6c+XoXnyaMOH4U2Bn9B/1sSnX\nl/O9OA8YiP676IseiyvxuzHOvVgS93dDC+5ERCSjYh56EhGRIqBAISIiGSlQiIhIRgoUIiKSkQKF\niIhkpEAhIiIZKVCIiEhGChQiIpKRAoXIJESlZXaZ2aZoA5nAzN5Z6HaJxEGBQmTy5gFfc/f3A78B\nlhW4PSKxUKAQmbwX3P2n0fOnCHcQEyk7ChQik/fHlOdvA9ML1RCROClQiIhIRgoUIpOXXnpZpZil\nLKnMuIiIZKQehYiIZKRAISIiGSlQiIhIRgoUIiKSkQKFiIhkpEAhIiIZKVCIiEhGChQiIpLR/wcD\nevxz0617gAAAAABJRU5ErkJggg==\n",
"text": [
"<matplotlib.figure.Figure at 0x10653aba8>"
]
}
],
"prompt_number": 36
},
{
"cell_type": "heading",
"level": 3,
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Profiling"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# import the function from a module (so Python knows \n",
"# how to get the source code)\n",
"\n",
"# firstly, go and copy the bubble sort above into a text\n",
"# file next to this notebook called 'algo202.py'\n",
"#\n",
"# then..\n",
"from algo202 import bubble_sort\n",
"\n",
"# Python can see the source!\n",
"bubble_sort??"
],
"language": "python",
"metadata": {
"internals": {},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [],
"prompt_number": 37
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# execute this cell to set up the %lprun magic command \n",
"# we use below\n",
"import line_profiler\n",
"import IPython\n",
"ip = IPython.get_ipython()\n",
"ip.define_magic('lprun', line_profiler.magic_lprun)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 40
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# profile the function\n",
"# even checking the size of the list has a noticable\n",
"# effect on running time!\n",
"%lprun -f bubble_sort bubble_sort([0, 1, 2, 3, 4])"
],
"language": "python",
"metadata": {
"internals": {
"slide_helper": "subslide_end"
},
"slide_helper": "slide_end",
"slideshow": {
"slide_type": "-"
}
},
"outputs": [],
"prompt_number": 38
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# try with a longer list\n",
"# on a longer list the len call cost is completely\n",
"# amortised - hence why we ignore constants in\n",
"# complexity analysis\n",
"%lprun -f bubble_sort bubble_sort(random_lists[4])"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 39
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment