06-Performance.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Performance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Avoiding slow code\n",
    "\n",
    "With pandas, you'll get the most bang for your buck by *avoiding antipatterns*.\n",
    "There are additional options like using Numba or Cython if you *really* need to optimize a piece of code, but that's more work typically."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook will walk through several common miskates, and show more performant ways of achieving the same thing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "import random\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import seaborn as sns\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "pd.options.display.max_rows = 10\n",
    "plt.style.use('default')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mistake 1: Using pandas\n",
    "\n",
    "- At least not for things it's not meant for.\n",
    "- Pandas is very fast at joins, reindex, factorization\n",
    "- Not as great at, say, matrix multiplications or problems that aren't vectorizable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mistake 2: Using object dtype\n",
    "\n",
    "Avoid it if possible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jake VanderPlas has a [great article](https://jakevdp.github.io/blog/2014/05/09/why-python-is-slow/) on why Python is slow for many of the things we care about as analysts / scientists.\n",
    "One reason is the overhead that comes from using python objects for integers, floats, etc. relative to the native versions.\n",
    "\n",
    "As a small demonstration, we'll take two series, one with python integers, and one with NumPy's `int64`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Two series of range(10000), different dtypes\n",
    "s1 = pd.Series(range(10000), dtype=object)\n",
    "s2 = pd.Series(range(10000), dtype=np.int64)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "604 µs ± 3.66 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit s1.sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "74.5 µs ± 759 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit s2.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NumPy can process the specialized `int64` dtype array faster than the python object version, even though they're equal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Typically you would never expecitly pass in `dtype=object` there, but occasionally object dtypes slip into pandas\n",
    "\n",
    "1. Strings\n",
    "\n",
    "    This is usually unavoidable. Pandas 2 will have a specialized string\n",
    "    type, but for now you're stuck with python objects. If you have few\n",
    "    *distinct* values (relative to the number of rows), you could use a\n",
    "    `Categorical`\n",
    "<br><br>\n",
    "2. Dates, Times\n",
    "\n",
    "    Pandas has implemented a specialized verion of `datetime.datime`,\n",
    "    and `datetime.timedelta`, but not `datetime.date` or `datetime.time`.\n",
    "    Depending on your application, you might be able to treat dates as `datetimes`s, at midnight.\n",
    "<br><br>\n",
    "3. Decimal types\n",
    "\n",
    "    Pandas uses floating-point arrays; there isn't a native arbitrary-precision Decimal type.\n",
    "<br><br>\n",
    "4. Reading messy Excel Files\n",
    "\n",
    "    `read_excel` will preserve the dtype of each cell in the spreadsheet. If you\n",
    "    have a single column with an int, a float, and a datetime, pandas will have to store all of those as `objects`. This dataset probably isn't tidy though.\n",
    "<br><br>\n",
    "\n",
    "5. Messy CSVs where pandas' usual inference fails\n",
    "<br><br>\n",
    "6. Integer NA\n",
    "\n",
    "    Unfortunately, pandas doesn't have real nullable types. To represent\n",
    "    missingness, pandas uses `NaN` (not a number) which is a special floating point value. If you *have* to represent nullable integers, you can use `object` dtype."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0    1.0\n",
       "1    2.0\n",
       "2    3.0\n",
       "3    NaN\n",
       "4    5.0\n",
       "5    6.0\n",
       "6    7.0\n",
       "7    8.0\n",
       "8    9.0\n",
       "dtype: float64"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = pd.Series([1, 2, 3, np.nan, 5, 6, 7, 8, 9])\n",
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "numpy.float64"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(s[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "int"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = pd.Series([1, 2, 3, np.nan, 5, 6, 7, 8, 9], dtype=object)\n",
    "type(s[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aside: Managing Dtypes\n",
    "\n",
    "Pandas provides some tools for converting arrays to their specialized dtype.\n",
    "\n",
    "0. IO operations (`read_csv` infers, but can use the `dtype` keyword)\n",
    "1. Object -> numeric: `pd.to_numeric`\n",
    "2. Object -> datetime: `pd.to_datetime`\n",
    "3. Object -> timedelta: `pd.to_timedelta`\n",
    "4. Object -> category: `pd.Categorical`\n",
    "5. `.astype(dtype)`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "They're pretty flexible what they accept."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  1.,   2.,   3.,  nan])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers = ['1', '2', '3.', 'nan']\n",
    "pd.to_numeric(numbers, errors='coerce')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "DatetimeIndex(['2016-01-01', '2016-02-01', '2016-03-01'], dtype='datetime64[ns]', freq=None)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dates = ['2016/01/01', '2016/02/01', '2016/03/01']\n",
    "pd.to_datetime(dates)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "TimedeltaIndex(['01:00:00', '00:00:30', NaT], dtype='timedelta64[ns]', freq=None)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# to_timedelta\n",
    "x = pd.to_timedelta(['1H', '30s', '20blah'], errors='coerce')\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "TimedeltaIndex(['00:10:00', '00:20:00', '00:30:00'], dtype='timedelta64[ns]', freq=None)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pd.to_timedelta([10, 20, 30], unit=\"T\")  # T = minutes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[a, a, c, b]\n",
       "Categories (3, object): [a < b < c]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pd.Categorical(['a', 'a', 'c', 'b'], categories=['a', 'b', 'c'],\n",
    "               ordered=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aside: Categoricals\n",
    "\n",
    "Pandas has a custom datatype, `Categorical`, for representing data that can come from a specified, generally fixed set of values.\n",
    "\n",
    "- `categories`: set of valid values\n",
    "- `ordered`: whether that set of values has an ordering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[a, b, c, a]\n",
       "Categories (4, object): [a, b, c, d]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c = pd.Categorical(['a', 'b', 'c', 'a'], categories=['a', 'b', 'c', 'd'])\n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Trying to insert a value that is outside the set of categories will cause an exception."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "Cannot setitem on a Categorical with a new category, set the categories first",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m-------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                        Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-15-0b47dac51aba>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mc\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m'f'\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m~/miniconda3/envs/ph2t2/lib/python3.6/site-packages/pandas/core/categorical.py\u001b[0m in \u001b[0;36m__setitem__\u001b[0;34m(self, key, value)\u001b[0m\n\u001b[1;32m   1868\u001b[0m         \u001b[0;31m# something to np.nan\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1869\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mto_add\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0misna\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mto_add\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mall\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1870\u001b[0;31m             raise ValueError(\"Cannot setitem on a Categorical with a new \"\n\u001b[0m\u001b[1;32m   1871\u001b[0m                              \"category, set the categories first\")\n\u001b[1;32m   1872\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mValueError\u001b[0m: Cannot setitem on a Categorical with a new category, set the categories first"
     ]
    }
   ],
   "source": [
    "c[0] = 'f'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Categoricals: Space Efficient\n",
    "\n",
    "Suppose you had to store a column with the home state for 321 million Americans.\n",
    "If you simply stored the text abbreviations like `['AL', 'AL', 'CA', 'IA', ...]` for all 321 million, you'd need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16.37 GB\n"
     ]
    }
   ],
   "source": [
    "N = 321_000_000\n",
    "bytes_per = sys.getsizeof(\"AL\")  # two characters per state\n",
    "print(f\"{N * bytes_per / 10**9:.2f} GB\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On the other hand, if you store\n",
    "\n",
    "1. Each of the 50 text abbreviations once\n",
    "2. An integer code for each of the 321 million people\n",
    "\n",
    "you'd need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.64 GB\n"
     ]
    }
   ],
   "source": [
    "character_bytes = 50 * sys.getsizeof(\"CA\")\n",
    "bytes_per_person = 2  # np.int16 = 2 bytes\n",
    "print(f\"{(character_bytes + N * bytes_per_person) / 10**9:.2f} GB\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's what Categoricals do internally. The set of categories [`'a', 'b', 'c', 'd']`, are stored *once*, and is availble with the `.categories` attribute.\n",
    "\n",
    "The values `['a', 'b', 'c', 'a']` aren't actually stored anywhere. Rather, an array of integer `codes` like `[0, 1, 2, 0]`, indiciating the position in `categories` is stored."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Index(['a', 'b', 'c', 'd'], dtype='object')"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c.categories"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 1, 2, 0], dtype=int8)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c.codes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[a, b, c, a]\n",
       "Categories (4, object): [a, b, c, d]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since an integer generally takes less memory to store than a string, these are an efficient way of representing data that has many repetitions. Categoricals can be stored in a DataFrame, Series, or index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0    a\n",
       "1    b\n",
       "2    c\n",
       "3    a\n",
       "dtype: category\n",
       "Categories (4, object): [a, b, c, d]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pd.Series(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pandas can take shortcuts when you use the proper dtypes.\n",
    "For example, the algorithms for `value_counts` and `groupby` are simplier, and thus faster, for Categoricals than for strings (object).\n",
    "We can time that:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mistake 3: Initialization\n",
    "\n",
    "When your collecting many different sources (say a bunch of separate CSVs) into\n",
    "a single DataFrame, you have two paths to the same goal:\n",
    "\n",
    "1. Make a single empty DataFrame, append to that\n",
    "2. Make a list of many DataFrames, concat at end\n",
    "\n",
    "Typically, in python we'd choose the first one if we were, for example, collecting things into a `list`. `list.append` is very fast. However `DataFrame.append` is *not* fast."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's make some fake datasets to work with"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "import string\n",
    "import random\n",
    "\n",
    "records = [[(random.choice(string.ascii_letters),\n",
    "             random.choice(string.ascii_letters),\n",
    "             random.choice(range(10)))\n",
    "            for i in range(50)]\n",
    "           for j in range(100)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we have 100 sets of 50 records each.\n",
    "This could represent any datasource, say 100 different CSVs, with any number of items in each.\n",
    "\n",
    "Each subset can be represented as a DataFrame"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('g', 'W', 6),\n",
       " ('i', 'o', 7),\n",
       " ('U', 'M', 9),\n",
       " ('n', 'j', 9),\n",
       " ('n', 'Z', 8),\n",
       " ('j', 'Q', 7),\n",
       " ('q', 'J', 0),\n",
       " ('E', 'b', 6),\n",
       " ('T', 'H', 4),\n",
       " ('r', 'r', 3)]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "records[0][:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>A</th>\n",
       "      <th>B</th>\n",
       "      <th>C</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>g</td>\n",
       "      <td>W</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>i</td>\n",
       "      <td>o</td>\n",
       "      <td>7</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>U</td>\n",
       "      <td>M</td>\n",
       "      <td>9</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>n</td>\n",
       "      <td>j</td>\n",
       "      <td>9</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>n</td>\n",
       "      <td>Z</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>45</th>\n",
       "      <td>Y</td>\n",
       "      <td>R</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>46</th>\n",
       "      <td>E</td>\n",
       "      <td>W</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>47</th>\n",
       "      <td>J</td>\n",
       "      <td>v</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>48</th>\n",
       "      <td>n</td>\n",
       "      <td>t</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>49</th>\n",
       "      <td>t</td>\n",
       "      <td>I</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>50 rows × 3 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "    A  B  C\n",
       "0   g  W  6\n",
       "1   i  o  7\n",
       "2   U  M  9\n",
       "3   n  j  9\n",
       "4   n  Z  8\n",
       ".. .. .. ..\n",
       "45  Y  R  6\n",
       "46  E  W  6\n",
       "47  J  v  5\n",
       "48  n  t  8\n",
       "49  t  I  0\n",
       "\n",
       "[50 rows x 3 columns]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pd.DataFrame(records[0], columns=['A', 'B', 'C'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The wrong way: DataFrame.append"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "110 ms ± 2.97 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "# Make an empty dataframe with the correct columns\n",
    "df = pd.DataFrame(columns=['A', 'B', 'C'])\n",
    "\n",
    "for set_ in records:\n",
    "    subdf = pd.DataFrame(set_, columns=['A', 'B', 'C'])\n",
    "    # append to that original df\n",
    "    # DataFrame.append is not inplace!\n",
    "    df = df.append(subdf, ignore_index=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-success\" data-title=\"Concat vs. Append\">\n",
    "  <h1><i class=\"fa fa-tasks\" aria-hidden=\"true\"></i> Exercise: Concat vs. Append</h1>\n",
    "</div>\n",
    "\n",
    "<p>Combine the set of records into a single DataFrame using `pd.concat`</p>\n",
    "\n",
    "Hints:\n",
    "\n",
    "- Make a list of dataframes using a list comprehension\n",
    "- Use `ignore_index=True` in `concat` to avoid duplicaes\n",
    "- add a `%%timeit` magic to time your solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>A</th>\n",
       "      <th>B</th>\n",
       "      <th>C</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>g</td>\n",
       "      <td>W</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>i</td>\n",
       "      <td>o</td>\n",
       "      <td>7</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>U</td>\n",
       "      <td>M</td>\n",
       "      <td>9</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>n</td>\n",
       "      <td>j</td>\n",
       "      <td>9</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>n</td>\n",
       "      <td>Z</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4995</th>\n",
       "      <td>r</td>\n",
       "      <td>r</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4996</th>\n",
       "      <td>F</td>\n",
       "      <td>Y</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4997</th>\n",
       "      <td>o</td>\n",
       "      <td>h</td>\n",
       "      <td>7</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4998</th>\n",
       "      <td>W</td>\n",
       "      <td>p</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4999</th>\n",
       "      <td>p</td>\n",
       "      <td>Y</td>\n",
       "      <td>7</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>5000 rows × 3 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "      A  B  C\n",
       "0     g  W  6\n",
       "1     i  o  7\n",
       "2     U  M  9\n",
       "3     n  j  9\n",
       "4     n  Z  8\n",
       "...  .. .. ..\n",
       "4995  r  r  6\n",
       "4996  F  Y  6\n",
       "4997  o  h  7\n",
       "4998  W  p  0\n",
       "4999  p  Y  7\n",
       "\n",
       "[5000 rows x 3 columns]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%load solutions/performance_concat.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mistake 4: Doing too much work\n",
    "\n",
    "This is more general purpose advice, rather than something you can just grep your code for.\n",
    "But look for places where you're doing a bunch of work, and then throwing some of it away."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0    14.0\n",
       "1    -3.0\n",
       "2     2.0\n",
       "3    -8.0\n",
       "4     2.0\n",
       "Name: dep_delay, dtype: float64"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# read in dep_delay column from flights\n",
    "delays = pd.read_parquet('data/ny-flights.parq')['dep_delay']\n",
    "delays.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose we wanted to find the 5 longest delays. One option is to sort the entire Series and then take the head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.34 ms ± 33.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit delays.sort_values(ascending=False).head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A better option is to use the `nlargest` method on `Series`, and then sort just those 5 elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "743 µs ± 23.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit delays.nlargest(5).sort_values(ascending=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In can be hard to remember all the methods or algorithms available to you though.\n",
    "I think this one just comes down to experience.\n",
    "\n",
    "For another example, let's suppose we wanted to find the nearest neighbor for a bunch of points.\n",
    "A naïve implementation would find the ~$N^2$ pairwise distances, and then go through finding the nearest neighbor for each.\n",
    "This becomes untenable for large $N$.\n",
    "Fortunately, we can be more efficient using [KDTrees](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html) instead of finding all pairwise distances.\n",
    "For very large $N$, various [probabilistic algorithms](https://github.com/ekzhu/datasketch) are available, but we won't talk about those today."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-success\" data-title=\"Nearest Neighbor\">\n",
    "  <h1><i class=\"fa fa-tasks\" aria-hidden=\"true\"></i> Exercise: Nearest Neighbor</h1>\n",
    "</div>\n",
    "\n",
    "<p>Find the nearest neighbor for all the airports with at least 500 departures.</p>\n",
    "\n",
    "The naïve way to do this is to compute a pairwise distance matrix of all 500 airports, and then lookup the closest neighbor for each airport.\n",
    "\n",
    "Let's avoid that unnescessary computation by using a `KDTree`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step 1: read in `data/flights_coord.csv`. Call the DataFrame coord\n",
    "coord = "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>AIRPORT_ID</th>\n",
       "      <th>AIRPORT</th>\n",
       "      <th>DISPLAY_AIRPORT_CITY_NAME_FULL</th>\n",
       "      <th>AIRPORT_STATE_CODE</th>\n",
       "      <th>LATITUDE</th>\n",
       "      <th>LONGITUDE</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>10001</td>\n",
       "      <td>01A</td>\n",
       "      <td>Afognak Lake, AK</td>\n",
       "      <td>AK</td>\n",
       "      <td>58.109444</td>\n",
       "      <td>-152.906667</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>10003</td>\n",
       "      <td>03A</td>\n",
       "      <td>Granite Mountain, AK</td>\n",
       "      <td>AK</td>\n",
       "      <td>65.548056</td>\n",
       "      <td>-161.071667</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>10004</td>\n",
       "      <td>04A</td>\n",
       "      <td>Lik, AK</td>\n",
       "      <td>AK</td>\n",
       "      <td>68.083333</td>\n",
       "      <td>-163.166667</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>10005</td>\n",
       "      <td>05A</td>\n",
       "      <td>Little Squaw, AK</td>\n",
       "      <td>AK</td>\n",
       "      <td>67.570000</td>\n",
       "      <td>-148.183889</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>10006</td>\n",
       "      <td>06A</td>\n",
       "      <td>Kizhuyak, AK</td>\n",
       "      <td>AK</td>\n",
       "      <td>57.745278</td>\n",
       "      <td>-152.882778</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   AIRPORT_ID AIRPORT DISPLAY_AIRPORT_CITY_NAME_FULL AIRPORT_STATE_CODE  \\\n",
       "0       10001     01A               Afognak Lake, AK                 AK   \n",
       "1       10003     03A           Granite Mountain, AK                 AK   \n",
       "2       10004     04A                        Lik, AK                 AK   \n",
       "3       10005     05A               Little Squaw, AK                 AK   \n",
       "4       10006     06A                   Kizhuyak, AK                 AK   \n",
       "\n",
       "    LATITUDE   LONGITUDE  \n",
       "0  58.109444 -152.906667  \n",
       "1  65.548056 -161.071667  \n",
       "2  68.083333 -163.166667  \n",
       "3  67.570000 -148.183889  \n",
       "4  57.745278 -152.882778  "
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%load solutions/performance_kd.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I don't know why, but apparently `AIRPORT_ID` isn't unique:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coord.AIRPORT.is_unique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can use `.groupby().first()` to arbitrarily select the first one per airport:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>LONGITUDE</th>\n",
       "      <th>LATITUDE</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>AIRPORT</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>01A</th>\n",
       "      <td>-152.906667</td>\n",
       "      <td>58.109444</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>03A</th>\n",
       "      <td>-161.071667</td>\n",
       "      <td>65.548056</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>04A</th>\n",
       "      <td>-163.166667</td>\n",
       "      <td>68.083333</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>05A</th>\n",
       "      <td>-148.183889</td>\n",
       "      <td>67.570000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>06A</th>\n",
       "      <td>-152.882778</td>\n",
       "      <td>57.745278</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          LONGITUDE   LATITUDE\n",
       "AIRPORT                       \n",
       "01A     -152.906667  58.109444\n",
       "03A     -161.071667  65.548056\n",
       "04A     -163.166667  68.083333\n",
       "05A     -148.183889  67.570000\n",
       "06A     -152.882778  57.745278"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "locs = coord.groupby('AIRPORT')[['LONGITUDE', 'LATITUDE']].first()\n",
    "locs.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Step 3: Use [`sklearn.neighbors.KDTree`](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html) to find the nearest neighbors.\n",
    "It's OK if you haven't used scikit-learn before; I've provided stubs of a solution below.\n",
    "I'd recommend making additional cell to check the intermediate values as you solve each step.\n",
    "\n",
    "And if you get stuck, the solution is provided afterwards.\n",
    "Feel free to read through it and the KDTree docs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.neighbors import KDTree\n",
    "\n",
    "tree = KDTree(...)  # see the docs (linked above) for KDTree\n",
    "\n",
    "# Now use `tree.query` to find the distances and\n",
    "# nearest neighbor. Make sure to pass a NumPy array to `.query`\n",
    "# and not a DataFrame; otherwise scikit-learn gets confused.\n",
    "# `locs.values` returns a NumPy array.\n",
    "\n",
    "# How many neighbors (k=...) do we need? Keep in mind that\n",
    "# we're searching on the same data as we built the tree on,\n",
    "# so what's the \"closest\" point for each observation?\n",
    "distances, indexes = tree.query(locs.values, k=...)\n",
    "\n",
    "# slice the NumPy arrays to just what we need\n",
    "# The array is shaped [n_observations, k] where `k` is\n",
    "# what you passed to query. Column 0 is the closest,\n",
    "# Column 1 is the second closest, etc...\n",
    "\n",
    "indexes = indexes[:, 1]\n",
    "distances = distances[:, 1]\n",
    "\n",
    "# the result of KDTree.query is a list of index\n",
    "# *positions*, we'll use id_map to go from \n",
    "# positions back to airport names\n",
    "id_map = dict(enumerate(locs.index))\n",
    "\n",
    "neighbors = pd.Series(indexes, index=locs.index).map(id_map)\n",
    "neighbors.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "AIRPORT\n",
       "01A    A75\n",
       "03A    GMT\n",
       "04A    UXA\n",
       "05A    AK4\n",
       "06A    ORI\n",
       "dtype: object"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%load solutions/performance_02.py\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mistake 5: Using `.apply` (with axis=1) (Avoid Iteration)\n",
    "\n",
    "I see this one a lot. I don't like absolutes, but you should never use `.apply(..., axis=1)` (probably).\n",
    "The root problem is using for loops instead of a vectorized solution.\n",
    "That is, something like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = range(10)\n",
    "b = range(10)\n",
    "c = [a_ + b_ for a_, b_ in zip(a, b)]\n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of the vectorized version:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0,  2,  4,  6,  8, 10, 12, 14, 16, 18])"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = np.arange(10)\n",
    "b = np.arange(10)\n",
    "c = a + b\n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "http://www.labri.fr/perso/nrougier/from-python-to-numpy/ is a great resource for learning about vectorized methods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a demonstration, let's dip into survival analysis.\n",
    "This is (roughly) the study of how much longer something will last (survive) given their current history.\n",
    "For example, how much longer will someone continue to be a customer, given their past purchases?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>frequency</th>\n",
       "      <th>recency</th>\n",
       "      <th>T</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>ID</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>30.43</td>\n",
       "      <td>38.86</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>1.71</td>\n",
       "      <td>38.86</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>0</td>\n",
       "      <td>0.00</td>\n",
       "      <td>38.86</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0</td>\n",
       "      <td>0.00</td>\n",
       "      <td>38.86</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>0</td>\n",
       "      <td>0.00</td>\n",
       "      <td>38.86</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    frequency  recency      T\n",
       "ID                           \n",
       "1           2    30.43  38.86\n",
       "2           1     1.71  38.86\n",
       "3           0     0.00  38.86\n",
       "4           0     0.00  38.86\n",
       "5           0     0.00  38.86"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from lifetimes.datasets import load_cdnow\n",
    "from lifetimes import BetaGeoFitter\n",
    "\n",
    "data = load_cdnow(index_col=[0])\n",
    "\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are all customer-level statistics:\n",
    "\n",
    "- frequency: number of repeat purchases\n",
    "- T: \"age\" of the customer (units since first purchase)\n",
    "- recency: age at time of last purchase\n",
    "\n",
    "The `lifetimes.BetaGeoFitter` model has a scikit-learn-like API to estimate several parameters and has several utility methods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/taugspurger/miniconda3/envs/ph2t2/lib/python3.6/site-packages/lifetimes/estimation.py:578: RuntimeWarning: invalid value encountered in log\n",
      "  A_4 = log(a) - log(b + freq - 1) - (r + freq) * log(rec + alpha)\n"
     ]
    }
   ],
   "source": [
    "# similar API to scikit-learn and lifelines.\n",
    "bgf = BetaGeoFitter(penalizer_coef=0.0)\n",
    "bgf.fit(data['frequency'], data['recency'], data['T']);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAApsAAAJkCAYAAABeVuqoAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAIABJREFUeJzs3Xm4JGV59/Hfr/tsMwyIwCDbIAbR\nSIyAGUGjeV0gCkQBjRpQFA2BeEUixiUur3HfX7eoaBwVwYVNFEWDwRWXiMigiCwS2RlAdmSZOUt3\n3+8fVQeak7P0dD/V1VP9/VxXX6e7uvqup6r79HnO/WyOCAEAAABFqJVdAAAAAFQXlU0AAAAUhsom\nAAAACkNlEwAAAIWhsgkAAIDCUNkEAABAYahsApsw22+3/eUuX/sy2z9b5Pnv2D5ivn1t32v7T7o5\nLjK232z7cwXEPcH2u/P7f2X78tTHAICNQWUT6DPb19jekFfYbrb9Bdsryi7XXBFxQEScuMBzKyLi\nKunBlZtu2X6R7bX5Nbkpr+g+pceYXVfE+yEi3hsR/9Dt622fY/tO2+OLHOOnEfHobo8BAClQ2QTK\n8ZyIWCHp8ZKeIOktc3dwpvK/o7ZfI+ljkt4r6WGSdpb0KUkHl1mulGyPJI63i6S/khSSDkoZGwBS\nq/wfMmCQRcQNkr4j6bHS/dmq99j+b0nrJf2J7R1sn2n7DttX2D5qTpgJ26favsf2r2zvMfuE7Tfa\nvjJ/7lLbz53zWtv+hO0/2v6d7X3bnjjH9ryZN9th+5G2j5b0Ykn/mmclv2X79ba/Nmf/T9j+2Dxx\nHiLpnZJeGRFfj4j7ImImIr4VEa/P93lQ5tT202yva3v8Bts35Od4ue19be8v6c2S/i4v12/yfRe8\nlnkm9Ku2v5zH+q3tR9l+k+1bbF9v+5ntZbf9+TwTe4Ptd9uu58+9zPZ/2/6o7TskvX2ec78/82p7\nIj/u7bbvsn2+7YfNd+1zL5X0C0knSDpioZ3ar1X+WTh9zvP/bvvjS50PAPSCyiZQIturJB0o6ddt\nm18i6WhJm0u6VtLJktZJ2kHS8yW9t71SqCwD+FVJW0k6SdI3bI/mz12pLAP2EEnvkPRl29u3vXYf\nSVdJ2kbS2yR93fZWnZY/ItZI+oqkD+ZN68+R9GVJ+9veMj/HEUl/J+lL84R4kqQJSWd0esx2th8t\n6RhJT4iIzSU9S9I1EfFfyjKlp+blmq2AL3Utn5OX86HK3pOzlX1P7qisUvyZtn1PlNSQ9EhJe0l6\npqT2yvnstd1W0nuWOJUjlL1HqyRtLekVkjYssv9LlV33r0h61hIV01knSzrQ9haSlFckX6jsM9PJ\n+QBAV6hsAuX4hu27JP1M0o+VVYxmnRARl0REQ9J2kp4i6Q0RMRkRF0r6nLIK6awLIuL0iJiR9BFl\nlbcnSlJEfDUiboyIVkScKun3kvZue+0tkj6WZxNPlXS5pL/p5cQi4iZJP5H0gnzT/pJui4gL5tl9\n6/y5RpeHa0oal7S77dGIuCYirpxvx7xiv9S1/GlEnJ2X56uSVkp6f35tT5G0i+0t88rdAZJenWdj\nb5H0UUmHtsW6MSI+ERGNiFis4ihJM8quxSMjohkRF0TE3Qucx1MkPVzSafk1vVLSi5aIr4i4VtKv\nJB2Sb3qGpPUR8YsOzwcAukJlEyjHIRGxZUQ8PCL+aU5l5Pq2+ztIuiMi7mnbdq2yTNv/2j8iWnog\ncyfbL7V9Yd40e5ey5vpt2l57Q0TEnNg79HRmmRMlHZ7fP1zzZzUl6XZJ23TbpzEirpD0amXN1LfY\nPsX2QuXv5Fre3HZ/g7KKcLPtsSStUFbZG5V0U9u1/YyyLOas9vdxKV9SlkU9xfaNtj/Ylp2e6whJ\n342I2/LHJ2mRpvQ5TpJ0WH7/RXogq9nJ+QBAV6hsAoOnvfJ3o6StbG/etm1nSTe0PV41e8fZgKKd\nJN1o++GSPqusmXnriNhS0sWS3PbaHW23P945P2a35Z31DUmPs/1YSc9W1tw7n3MlTeqBbNt87pO0\nvO3xdg86eMRJETGb7QtJH1igXJ1cy05dL2lK0jb5Pw1bRsQWEfFn7UXrNFieWX5HROwu6S+VXbOX\nzt3P9jJlTd9Ptf0H23+Q9C+S9mjvq7uIr0p6mu2dJD1XD1Q2OzkfAOgKlU1ggEXE9ZJ+Lul9+SCS\nx0k6Ug+uvP2F7efl2cFXK6s0/ELSZsoqPLdKku2XKx+I1GZbSa+yPWr7BZIeI+msjSzmzZIeNOdm\nRExKOl1ZZeaXEXHdAuf3R0lvlXSc7UNsL8/LcoDtD+a7Xaisr+FWtrfLz1H5OT3a9jOcTf8zqSz7\nOJuJvFlZs3ctP1Yn17IjeVeB70r6sO0tbNds72r7qRsbKz+Pp9v+87wf5d3KmtWb8+x6SL59d0l7\n5rfHSPqp5qmczlPuWyWdI+kLkq6OiMs6OR/buzgbFLZLN+cHYLhR2QQG32GSdlGWmTtD0tsi4ntt\nz39T2QCcO5X1P3xenim7VNKHlWUPb5b055L+e07s8yTtJuk2ZYNYnh8Rt29k+T6vrM/kXba/0bb9\nxPyYCzWhS5Ii4iOSXqNs+qdblWXZjlGWHVX++t9IukZZhejUtpePS3p/Xv4/KKs8vzl/7qv5z9tt\n/yq/v9S13BgvlTQm6VJl1/50Sdsv+oqFbZe//m5JlynrxzvfHKFHSPpCRFwXEX+YvUn6pKQXd9gd\n4SRJ++mBrOasxc5nlbIuB91kgQEMOT+4uxYApGF7Z0m/k7TdQoNdsGmw/RZJt0bEZ5bcGQDmoLIJ\nILm86fojkraIiL8vuzwAgPIkXdUCAGxvpqzZ/lpl0x4BAIYYmU0AAAAUhgFCAAAAKAyVTVSa7Wts\n71d2ObCwfEqdR5ZdjkGST+n0a2drtL+q7PIAQC+obAIdsP002y3b97bdvlV2uarO9jm2J/PrfZvt\nr89Z272q/lXSORGxeUR8vNdgtre3/XnbN+UV2N/Zfkfev7aXuPyjAGBJVDaBzt0YESvabs+Zb6du\nl17Ego6JiBWSHqlsqcgPlVyefni4pEtSBLK9lbK5VpdJelJEbC7pryVtKWnXFMcoG79zwGCjsolh\n8ATbl9q+0/YXbE9Iku2Lbd9fYcxXrrnN9p4bE9z2222fbvvLtu+W9LJ8BZY32r7S9u22T8v/6M++\n5iW2r82f+7/tzf22T7D97rZ9n2Z7XdvjHWx/zfattq9ub2bNy3Ka7S/mGaxLbK9ue35Vnh28NT/2\nJ22P277D9p+37bet7Q22V85zvrva/mH++ttsf8X2lm3PX2P7dbYvsv1H26fOXvP8+dfnGbYbbXc8\nLVJE3KVsovf7358OrvNTbP88n3D+etsvy7eP2/6Q7ets32z7P5wtBXn/9bb9Wtu35GV9eVvMZbY/\nnL9/f7T9s3zbf9r+5znX6iLb8y7Fafug/P25K8/gPibf/kNJT5f0yTyj+6h5Xvty25fl7/FVtv9x\nkUv3Gkn3SDo8Iq7Jr+X1EXFsRFzkB1YHur/ClpfnH/L7j7T94/xcb7N9ar79J/nuv8nL+Xf59qNs\nX5F/ps5021r1+XH+yfbv87K/K/88nWv77vz9G2vb/9m2L8yv0c+drfo0+9w1tt9g+yJJ95kKJzCw\nqGxiGLxY0rOUZXEepWylGkn6oqTD2/Y7UNJNEXFhF8c4WNmKK1sqW/7wVcqWFnyqpB2UrchynCTZ\n3l3Sp5Wt9rODpK2VrWe+JGfzV35L2Yo6O0raV9KrbT+rbbeDJJ2Sl+VMZavLyNlSiN9WNiXRLvnr\nT4mIqXz/9mtxmKTv58sb/q9iSHpfXvbHKFtd5u1z9nmhsmmPHiHpcZJelpdhf0mvU5ZZ203ZSjYd\nsb21pOdJuqJt82LXeWdJ35H0CUkrlVVSZ9/bDyj7LOypLGO6o7JlM2dtJ+kh+fYjlS2n+dD8uQ9J\n+gtla5hvpazJu6VsxaT7r6Gztcp31DzLf+YVyJOVLb25Mt/nW7bHIuIZypafPCbPoP/PPJfjFmXr\np28h6eWSPmr78fNfOe0n6esR0Vrg+aW8S9nKTQ9V9jn9hCRFxP/Jn98jL+eptp+h7LPxQmWrD12r\n7LPVbn9l1++Jyq7dGmW/o6uULad6mCTl53O8pH9U9jvyGUlnOluadNZhkv5G0pYR0ejy/AAULSK4\ncavsTdkSh69oe3ygpCvz+zsoy/hskT8+XdK/LhDnacoqFHe13V6YP/d2ST+Zs/9lkvZte7y9svWu\nR5RVak5pe24zSdOS9ssfnyDp3XOOvS6/v4+k6+Yc603KljCcLcv3257bXdKG/P6TlC0HOTLP+e2j\nbJnIWv547ez5dXCND5H06znX/PC2xx+U9B/5/eMlvb/tuUcpW7/9kQvEPkfSekl/zPe7UNLOHV7n\nN0k6Y56YlnSfpF3btj1J2Vrhs9d7Q/t1Ula5e6Kyf9A3KKtgzY07LukOSbvljz8k6VMLnNe/STqt\n7XFN2VKQT2s773/YiM/5NyQdu8Bzv1fb78A8z++SX9v2873/+Mr+KVsjaad5Xvug907Z0qUfbHu8\nIn8/dmnb/8ltz18g6Q1tjz8s6WP5/U9Letec410u6altn7O/7/QacePGrbwbmU0Mg+vb7l+rrJKp\niLhR2Vrhf5s3Ax+gLCu5kBsjYsu222kLHEPK+tydkTf/3aWsUtSU9LD8+PfvHxH3Sep0PfKHS9ph\nNm4e+8153Fl/aLu/XtJE3sS4StK1MU8GKCLOU1YBe6rtP1WW7TtzvgLkTeyn2L7BWbeBL0vaZs5u\nc8uwIr//oHNX9n4s5VUR8RBlGdLZ7Nqsxa7zKklXzhNvpaTlki5oe91/5dtn3T7nOs2ewzaSJuaL\nG1mG+DRJh+cZ6MO08LrwO6jt3CPLOl6vLBO6JNsH2P5F3lR9l7J/oua+B/efi7pfs13Kso+W9Mu8\n2X+xrg9zz+ve/Pjt53Vz2/0N8zye/aw8XNJr53zWV+XHmDX39w7AAKKyiWGwqu3+zpJubHs82/T5\nAknnRsQNXR5j7uoI10s6YE7ldCKPf1N7mWwvV9ZMOOs+ZZWhWdvNiXv1nLibR8SBHZTxekk7L9K3\nbfZavETS6RExucB+71N2vo+LiC3y17iD40tzzl3Z+9GRiPitpHcra9KePd5i1/l6zT8A5jZllZo/\na3vNQyIbhLSU2yRNLhBXyq7hi5V1b1gfEecusN+NyipTkqT8fFYpy24uKm9G/pqyzOnDImJLZc3w\nC70H35f03LwCPJ/78p/zfuYi4g8RcVRE7KCsSftTXngE+tzz2kzZZ7ub36vrJb1nznu7PCJObtuH\nVUmATQCVTQyDV9reydnAkTdLOrXtuW9IerykY5U1F6byH5LeY/vhkmR7pe2D8+dOl/RsZ4NXxiS9\nUw/+XbxQ0oG2t7K9nbJ+fbN+KenufGDEMtt124+1/YQOyvRLZZW999vezPaE7Se3Pf8lSc9VVnlc\n7FpsLuleSXfZ3lHS6zs49qzTlA2g2j2vZL9tI14rZZW5bZX1S5UWv85fkbSf7RfaHrG9te098yzi\nZ5X1c9w2f92Oc/q9zit/7fGSPuJsoFbd9pNm+xHmlcuWsubghbKaUnYd/sb2vrZHJb1W0pSkn3dw\nDcaUNdnfKqlh+wBJz1xk/48o69t5Ytt12tH2R2w/LrJ+uTcoy8jW88zl/ZVp2y+wPZtNvlNZBa+Z\nP75Z0p+0HeskSS+3vWd+Td4r6bzIByZtpM9KeoXtfZzZzPbf2N68i1gAOmD7eGcDIy9e4Hnb/riz\nQYAXLdJX/EGobGIYnKRsgMNV+e3+kd4RsUFZlugRkr6e8Jj/rqwZ+ru275H0C2X9IhURl0h6ZV6u\nm5T9AV/X9tovKRsAdE1e7vsrxxHRlPQcZQNbrlaWafucssEsi2p77SMlXZcf8+/anl8n6VfKKhM/\nXSTUO5RV0P8o6T+1EdctIr4j6WOSfqhsoM8PO31t/vppSR9X1udRWvw6X6esefm1yvpSXihpj/x1\nb8iP/4u8K8D3JT26w2K8TtJvJZ2fx/2AHvxd+kVJf66se8FC53G5skr9J5S9h8+R9Jz8/BYVEfco\nGxh1mrLPzou0QJeHfP87lA1mmpF0Xn6dfqDs/ZsdbHWUsn8abpf0Z3pwpfcJ+evuzY9zbERcnT/3\ndmWV2LtsvzAifqDsvfmass/2rpIOXeqcFij32rxcn8zP8wrlA80AFOYEZYP4FnKAssGdu0k6Wlnf\n6iWxNjqGnu23SnpURBy+5M7FleEaZQMyvl9WGfJyHK+sb+pbltwZ87L9UklHR8RTyi4LAGws27tI\n+nZEPHae5z6jbMGJk/PHlysb2HjTYjGZlwxDLW9aP1JZP8Whln/BPE/SXuWWZNOVdw34J0mfKrss\nAFCAHfXggXnr8m1UNoH52D5KWZPulyLiJ0vtX2W23yXpXyS9r62JFBsh7/P5dWVN8ieVXBwAm4hn\nPX2zuP2O5tI7JnDBRVOXKBvkOGtNRKzZiBDzDURcsomcZnQAAICSrN5jIn55dscTc/Skvv3vL4iI\n1YvtU0QzOgOEAAAA0IkzJb00H5X+REl/XKqiKdGMDgAAUJqQ1FK3q8mmZftkZauobWN7nbLp6UYl\nKSL+Q9mcvgcqmx1ivbLlcpe0SVQ2t9mqHrusGu05zv9csVWC0kjeMJUkDl0YAAAozz2687aIWLn0\nnsMhIg5b4vlQNnXfRtkkKpu7rBrVL89etfSOS9j/oDQz2/jiK5beqQOtyYUWaAEAAEX7fpzeyZK5\nBQs1YzAym0WhzyYAAAAKU0pl0/b+ti/Plzt6YxllAAAAKFvWZzP6citL3yubtuuSjlO25NHukg6z\nvXu/ywEAAIDildFnc29JV0TEVZJk+xRJB0u6tISyAAAAlGpQRqMXpYxm9IWWOgIAAEDFlJHZ7Gip\nI9tHSzpaknbecZMYNA8AALBRQqFmxadCLCOzuU5S+zxGO0m6ce5OEbEmIlZHxOqVW9f7VjgAAACk\nU0bK8HxJu9l+hKQbJB0q6UUllAMAAKB0ZY4U74e+VzYjomH7GElnS6pLOj4iLul3OQAAAFC8UjpD\nRsRZytbXBAAAQIUx8gYAAKAkIalZ8WZ0lqsEAABAYYYqs9lYMZYkzthYmjiamuo9RsWnSwAAoOqq\nPkCIzCYAAAAKM1SZTQAAgEESEpO6AwAAAN0iswkAAFCiVtkFKBiZTQAAABSGzCYAAEBJQsE8mwAA\nAEC3yGwCAACUJaRmtRObZDYBAABQHDKbAAAAJQkxGh0AAADoGplNAACA0lhNuexCFGqoKpuNZfUk\nccbGx5PE8fr1PceIRiNBSQAAAIpBMzoAAAAKM1SZTQAAgEESklpMfQQAAAB0h8wmAABAiao+QIjM\nJgAAAApDZhMAAKAkITKbAAAAQNfIbAIAAJSoFWQ2AQAAgK6Q2QQAACgJfTYBAACAHpDZBAAAKEnI\nalY891ftswMAAECphiqz2Viepm7t8bEkceQE5XGifh5R8YVZAQAYUIxGBwAAALo0VJlNAACAQcJo\ndAAAAKAHZDYBAABKYzWj2rm/ap8dAAAASkVlEwAAAIWhGR0AAKAkIalV8dxftc8OAAAApSKzCQAA\nUCKmPgIAAAC6RGYTAACgJBFMfQQAAAB0jcwmAABAiVoV77M5VJXNxkSaNzMmxpLE8Wjvlz8aMwlK\nAgAAUIyhqmwCAAAMkpDUrHivxmqfHQAAAEpFZhMAAKA0jEYHAAAAukZmEwAAoCSsjQ4AAAD0gMwm\nAABAiZpR7Xk2yWwCAACgMFQ2AQAAUBia0QEAAEoSMpO6AwAAAN0iswkAAFCiFpO6AwAAAN0Zqsxm\nYyLR1ALjY0nCeCTB5Xei/xeimSYOAADoWEj02QQAAAC6NVSZTQAAgEEScuUndS+lsmn7Gkn3SGpK\nakTE6jLKAQAAgGKVmdl8ekTcVuLxAQAASteqeK/Gap8dAAAASlVWZjMkfdd2SPpMRKwpqRwAAACl\niZCaFZ9ns6zK5pMj4kbb20r6nu3fRcRP2newfbSkoyVp5x0ZxwQAALApKqUqHRE35j9vkXSGpL3n\n2WdNRKyOiNUrt673u4gAAAB9YLX6dCtL3yubtjezvfnsfUnPlHRxv8sBAACA4pXRPv0wSWfYnj3+\nSRHxXyWUAwAAoFQh+mwmFxFXSdqj38cFAABA/1W7Kg0AAIBSDdUw7+Z4ms6xreVjSeLUxkZ7juF6\nmsFTEa0kcRSRJg4AAEOiWfHcX7XPDgAAAKUaqswmAADAIAlZrShvWqJ+ILMJAACAwpDZBAAAKBF9\nNgEAAIAukdkEAAAoSUhqVXxS92qfHQAAAEpFZhMAAKA0VlOMRgcAAAC6QmYTAACgJPTZBAAAAHpA\nZhMAAKBE9NkEAAAAujRUmc3WWJo4zYk0l60+OtpzDNfT/L8QzUT/d0QzTRwAAIZAhOmzCQAAAHSL\nyiYAAAAKM1TN6AAAAIOmSTM6AAAA0B0qmwAAACUJSS25L7dO2N7f9uW2r7D9xnme39n2j2z/2vZF\ntg9cKiaVTQAAAMh2XdJxkg6QtLukw2zvPme3t0g6LSL2knSopE8tFZc+mwAAAKXxIPXZ3FvSFRFx\nlSTZPkXSwZIubdsnJG2R33+IpBuXCkplEwAAAJK0o6Tr2x6vk7TPnH3eLum7tv9Z0maS9lsq6MBU\npQEAAIZNSGqF+3KTtI3ttW23o+cUZ76OnTHn8WGSToiInSQdKOlLthetT5LZBAAAGA63RcTqRZ5f\nJ2lV2+Od9L+byY+UtL8kRcS5tickbSPploWCktkEAAAoUVO1vtw6cL6k3Ww/wvaYsgFAZ87Z5zpJ\n+0qS7cdImpB062JBqWwCAABAEdGQdIyksyVdpmzU+SW232n7oHy310o6yvZvJJ0s6WURMbep/UFo\nRgcAAChJ6P7+lAMhIs6SdNacbW9tu3+ppCdvTMyhqmw2x9PEaSyvJ4kzNpGgQKOjvceQ5EYjSZxI\n9Quz+D9JAABgEzFUlU0AAIBB06p4r8Zqnx0AAABKRWYTAACgJBFSc4D6bBaBzCYAAAAKQ2UTAAAA\nhaEZHQAAoESDNPVREchsAgAAoDBkNgEAAEqSTepe7dxftc8OAAAApSKzCQAAUKKm6LMJAAAAdIXM\nJgAAQElCjEYHAAAAujZUmc3WaJo4zWVp6ugxMdZzDI+keQvDqf7vaCaKAwDAMGA0OgAAANC1ocps\nAgAADJoWo9EBAACA7pDZBAAAKEmE1GQ0OgAAANAdMpsAAAAlYjQ6AAAA0CUqmwAAACgMzegAAAAl\nCZnlKgEAAIBukdkEAAAoEZO6AwAAAF0aqsxmazRNnMZEmjp6jPdeII+lOSmPpvkoRLOZJI7UShMm\nIk0cAAAKEBJ9NgEAAIBuDVVmEwAAYNAwqXuXbB9v+xbbF7dt28r292z/Pv/50KKODwAAgPIVWZU+\nQdL+c7a9UdIPImI3ST/IHwMAAAynyObZ7MetLIVVNiPiJ5LumLP5YEkn5vdPlHRIUccHAABA+frd\nZ/NhEXGTJEXETba37fPxAQAABkaIeTZLY/to22ttr7319lTT6QAAAKCf+p3ZvNn29nlWc3tJtyy0\nY0SskbRGklbvMcFkiQAAoJKYZzOtMyUdkd8/QtI3+3x8AAAA9FFhmU3bJ0t6mqRtbK+T9DZJ75d0\nmu0jJV0n6QVFHR8AAGDQDcMKQoVVNiPisAWe2reoYwIAAGCwDOwAIQAAAGz6WK4SAACgRDSjV0hr\nLM2g9sZEmg9Fc/lozzFGx8YSlESKej1JHCeKE41WkjgAAKBcQ1XZBAAAGCShcpeS7Af6bAIAAKAw\nZDYBAABKxHKVAAAAQJfIbAIAAJQlqj8ancwmAAAACkNmEwAAoCTDsFwlmU0AAAAUhswmAABAichs\nAgAAAF0iswkAAFASVhACAAAAekBmEwAAoERR8czmUFU2W4nOtjmeKM6y3gs0MjGWoCSSx0aTxNHM\nTJIw0UyVdG+lCRORJg4AAEOGZnQAAAAUZqgymwAAAIOmpWo3o5PZBAAAQGHIbAIAAJQkgkndAQAA\ngK6R2QQAAChR1ac+IrMJAACAwpDZBAAAKA3LVQIAAABdI7MJAABQIvpsAgAAAF0iswkAAFCSEPNs\nAgAAAF0bqsxmjESSOI2JNHX0xrJ6zzHGlo0lKIlUG0sTJyanksRxvZUkTjTSxAEAoBCRrSJUZWQ2\nAQAAUJihymwCAAAMmpboswkAAAB0hcomAAAACkMzOgAAQElCTOoOAAAAdI3MJgAAQGnMpO4AAABA\nt8hsAgAAlIhJ3QEAAIAukdkEAAAoEaPRAQAAgC4NVWYzRtN0imhOJAmjxvLe6/qt5WMJSiLVxtPE\n8ViaOGo208SJepowycpT8Y45AICNEkFmEwAAAOjaUGU2AQAABg3zbAIAAABdIrMJAABQoqp35yez\nCQAAgMKQ2QQAACgRo9EBAACALlHZBAAAQGFoRgcAAChJyDSjAwAAAN0iswkAAFCiis98RGYTAAAA\nxSGzCQAAUJao/tRHQ1XZjJE0ierWWJIwmlnW+4eruSzNW1hfNp4kjienksSJRiNJHDVbaeI4VSNH\novJUfbkJAEBlDFVlEwAAYOBUPH9An00AAAAUprDKpu3jbd9i++K2bW+3fYPtC/PbgUUdHwAAYFMQ\n4b7cylJkZvMESfvPs/2jEbFnfjurwOMDAABgI9je3/bltq+w/cYF9nmh7UttX2L7pKViFtZnMyJ+\nYnuXouIDAABUwaCM+bRdl3ScpL+WtE7S+bbPjIhL2/bZTdKbJD05Iu60ve1Sccvos3mM7YvyZvaH\nlnB8AAAA/G97S7oiIq6KiGlJp0g6eM4+R0k6LiLulKSIuGWpoP2ubH5a0q6S9pR0k6QPL7Sj7aNt\nr7W99tbbm/0qHwAAQN+EBqrP5o6Srm97vC7f1u5Rkh5l+79t/8L2fF0mH6Svlc2IuDkimhHRkvRZ\nZTXohfZdExGrI2L1yq3r/SskAABANW0zm8jLb0fPeX6+GuncRv4RSbtJepqkwyR9zvaWix20r/Ns\n2t4+Im7KHz5X0sWL7Q8AAFBpIal/I8Vvi4jVizy/TtKqtsc7Sbpxnn1+EREzkq62fbmyyuf5CwUt\ncuqjkyWdK+nRttfZPlLSB23yEwaMAAAgAElEQVT/1vZFkp4u6V+KOj4AAAA2yvmSdrP9CNtjkg6V\ndOacfb6hrA4n29soa1a/arGgRY5GP2yezZ8v6ngAAACbokEZjR4RDdvHSDpbUl3S8RFxie13Slob\nEWfmzz3T9qWSmpJeHxG3LxZ3ycpmftCvzI46AgAAQDXlc6CfNWfbW9vuh6TX5LeOdNKMvp2yeZZO\nyyf6LG8KegAAAGxSlsxsRsRbbP+bpGdKermkT9o+TdLnI+LKoguYVD1Nnro5niZOY1nvMWY2S9MT\nYmT5WJI49fVp4nhqOkkcjSaaNitaicKk6iadoDyD0m4DAMOu4l/HHf3ly1Omf8hvDUkPlXS67Q8W\nWDYAAABs4jrps/kqSUdIuk3S55R1BJ2xXZP0e0n/WmwRAQAAqqrjCdc3WZ20wW4j6XkRcW37xoho\n2X52McUCAABAFXTSjH6WpDtmH9je3PY+khQRlxVVMAAAgKEQfbqVpJPK5qcl3dv2+L58GwAAALCo\nTprRnQ8QknR/83lfl7kEAACopFDl+2x2ktm8yvarbI/mt2O1xLJEAAAAgNRZZfMVkv5S0g3KFl/f\nR9LRRRYKAABgaFS8z2Ynk7rfomwhdgAAAGCjdDLP5kpJR0napX3/iPj74ooFAAAwLKrdZ7OTgT7f\nlPRTSd+XlGjtPwAAAAyDTiqbyyPiDYWXBAAAYBixNrq+bfvAwksCAACAyukks3mspDfbnpY0raxj\nQUTEFoWWrAgjrSRhWmNJwqi5rPc+GjObdfL/wtLGlqc5qdrEeJI4nppOEkfNND0/IlEcJ+qJEinC\nOFEfoaj4v+QAULSKf412Mhp9834UBAAAANWzZFrMmcNt/1v+eJXtvYsvGgAAADZ1nbTBfkrSkyS9\nKH98r6TjCisRAADAsAhJ4f7cStJJn819IuLxtn8tSRFxp+1EvRYBAABQZZ1UNmds15V3X80neU8z\n0gYAAGDIVX2cZSfN6B+XdIakbW2/R9LPJL230FIBAACgEjoZjf4V2xdI2lfZtEeHRMRlhZcMAABg\nGFQ8s9nJ2uhPlHRJRByXP97c9j4RcV7hpQMAAMAmrZNm9E8rG4E+6758GwAAAHpV8dHonVQ2HfFA\n19WIaKmzgUUAAAAYcp1UNq+y/Srbo/ntWElXFV0wAACAYeDoz60snVQ2XyHpLyXdIGmdpH0kHV1k\noQAAAFANnYxGv0XSoX0oS+FcT1Otb46nidOY6L3/xMzyNH0wGpul6RlRXzGeJs70TJI4ajSShHGz\nmSROqn8sU7zrkeicAAA9CFV+NHona6M/yvYPbF+cP36c7bcUXzQAAABs6jppRv+spDdJmpGkiLhI\nFcl0AgAAlKtPI9EHfDT68oj45ZxtadomAQAAUGmddNS7zfauemBt9OdLuqnQUgEAAAyLivfZ7KSy\n+UpJayT9qe0bJF0t6fBCSwUAAIBK6GQ0+lWS9rO9maRaRNxTfLEAAABQBYv22bRdt72NJEXEfZKm\nbB9l+7K+lA4AAKDqok+3kixY2bR9qKQ7JF1k+8e2n65s5aADJb24T+UDAADAJmyxZvS3SPqLiLjC\n9uMlnSvp0Ig4oz9FAwAAGAIVHyC0WDP6dERcIUkR8StJV1PRBAAAwMZYLLO5re3XtD1e0f44Ij5S\nXLEAAACGQKjUCdf7YbHK5mclbb7IYwAAAGBRC1Y2I+Id/SwIAADAMHLF+2x2Mql7ZdRGWkniNMcS\nxVnWe9q8sTxN6n1mRScrly5t5L6xJHFqkxNJ4ngm0cqqkeibYDJNmGglKE+yb7c0vw/JpHqvAABJ\nDFVlEwAAYOBU/H/kNOksAAAAYB5LVjZtH2t7C2c+b/tXtp/Zj8IBAABg09ZJZvPvI+JuSc+UtFLS\nyyW9v9BSAQAAoBI66bM5OwLlQElfiIjf2K72hFAAAAB9UvXR6J1kNi+w/V1llc2zbW+ugRt+CgAA\ngEHUSWbzSEl7SroqItbb3lpZUzoAAAB6NawrCNneOb/bzNdGlyRFxO2Sbi+6YAAAANj0LZbZPDH/\nebuk5/ehLAAAAKiYxZarfLrtmqQn9rE8AAAAwyM03JO6R0RL0of7VBYAAABUTCej0b9r+2+Z7ggA\nAKAA0adbSToZjf4aSZtJatreoGzezYiILQotGQAAADZ5S1Y2I2LzfhSkH2q1NNODNkcTxZmo9xyj\nsVmCgkiaXtFJkntpI+s7+f9labWpsSRx6jMTSeK42UwSR61E/1rGAHXwSTRlR6S6xqkaYQbpGgOo\ntKGf1D1fE/1w2/+WP15le+/iiwYAAIBNXSfprE9JepKkF+WP75V0XGElAgAAGCYV77PZSWVzn4h4\npaRJSYqIOyUt2caZZ0B/ZPsy25fYPjbfvpXt79n+ff7zoT2dAQAAAAZWJ5XNGdt15XVi2yvV2dro\nDUmvjYjHKJur85W2d5f0Rkk/iIjdJP0gfwwAADCcyGzq45LOkLSt7fdI+pmk9y71ooi4aXaZy4i4\nR9JlknaUdLAeWJ3oREmHdFFuAAAAbAI6GY3+FdsXSNpX2bRHh0TEZRtzENu7SNpL0nmSHhYRN+Wx\nb7K97cYWGgAAoAocjEafdbOkn0r6uaRlth/f6QFsr5D0NUmvjoi7N+J1R9tea3vtrbcnmhIFAAAA\nfbVkZtP2uyS9TNKVeqDFPyQ9o4PXjiqraH4lIr6eb77Z9vZ5VnN7SbfM99qIWCNpjSSt3mOi4nV+\nAAAwtBLNVzyoOpmB+4WSdo2I6Y0JnC9v+XlJl0XER9qeOlPSEZLen//85sbEBQAAwKajk8rmxZK2\n1AIZyEU8WdJLJP3W9oX5tjcrq2SeZvtISddJesFGxgUAAKiOirffdlLZfJ+kX9u+WNLU7MaIOGix\nF0XEz5QNKJrPvh2XEAAAAJusTiqbJ0r6gKTfqrP5NQEAAABJnVU2b4uIjxdeEgAAgCFU9amPOqls\nXmD7fcoG9rQ3o/+qsFIVpF5P8242RtMkeJsTvcdpLK8nKIk0syLNSLjpDWnKU59ackXUjriZ5r2q\ntdLEqeJ4w2immZos1bWJVqpv7UQNOVHxvyIAsIROKpt75T+f2Lato6mPAAAAsISK/0/ayQpCT+9H\nQQAAAFA9nUzq/hBJb5P0f/JNP5b0zoj4Y5EFAwAAqDyWq5QkHS/pHmWTu79Q0t2SvlBkoQAAAFAN\nnfTZ3DUi/rbt8TvaJmkHAABAL8hsaoPtp8w+sP1kSRuKKxIAAACqopPM5iskfTHvuylJdypb0xwA\nAAC9qnhms5PK5t0RsYftLSQpIu62/YiCywUAAIAK6KQZ/WtSVsmMiLvzbacXVyQAAIDh4ejPrSwL\nZjZt/6mkP5P0ENvPa3tqC0kTRRcMAAAAm77FmtEfLenZkraU9Jy27fdIOqrIQgEAAKAaFqxsRsQ3\nJX3T9pMi4tw+lgkAAAAV0ckAoefavkTZdEf/JWkPSa+OiC8XWrIC1OutNHFG08RpjPcep7Gsk263\nS5tZ4SRx6pOJ4sx08tFcmpvjSeKMNtN0dnErUZwkURKZnk4SJlV3IquZJE600vxuSWm+L5KIig95\nBTZVFf/V7OTb9Jn5wKBnS1on6VGSXl9oqQAAAFAJnVQ2R/OfB0o6OSLuKLA8AAAAqJBO2iq/Zft3\nyprR/8n2SkmTxRYLAABgCJQ8LVE/LJnZjIg3SnqSpNURMSPpPkkHF10wAAAAbPqWzGzafmnb/fan\nvlhEgQAAAIZKxTObnTSjP6Ht/oSkfSX9SlQ2AQAAsIQlK5sR8c/tj20/RNKXCisRAADAMKl4ZrOb\nieTWS9otdUEAAABQPZ302fyWHqhz1yTtLum0IgsFAAAwDKzqj0bvpM/mh9ruNyRdGxHrCioPAAAA\nKmTByqbtR0p6WET8eM72v7I9HhFXFl46AACAqqt4ZnOxPpsfk3TPPNs35M8BAAAAi1qsGX2XiLho\n7saIWGt7l8JKBAAAMCyGYAWhxSqbE4s8tyx1QfqhVmsliTMy2kwSpznRzWQAc2Is7z2GJM1Mp4lT\nm/bSO3USp5GmPG520i25gzgxniROmtJIrvV+nV1Lc42VoCySpESfQc3MpInTTPN9oUhzfaKV4q9R\nonNKJSr+FxaApMWb0c+3fdTcjbaPlHRBcUUCAAAYItGnW0kWS7S8WtIZtl+sByqXqyWNSXpu0QUD\nAABAf9neX9K/S6pL+lxEvH+B/Z4v6auSnhARaxeLuWBlMyJulvSXtp8u6bH55v+MiB92U3gAAADM\nY0B6lNiuSzpO0l9LWqeslfvMiLh0zn6bS3qVpPM6idvJcpU/kvSjjS4xAAAANiV7S7oiIq6SJNun\nSDpY0qVz9nuXpA9Kel0nQRP1yAcAAMAmbkdJ17c9Xpdvu5/tvSStiohvdxo01eBYAAAAdKGPUx9t\nY7u9f+WaiFjTXpR5XnN/6WzXJH1U0ss25qBUNgEAAIbDbRGxepHn10la1fZ4J0k3tj3eXNk4nnNs\nS9J2ks60fdBig4SobAIAAJRpQAYISTpf0m62HyHpBkmHSnrR7JMR8UdJ28w+tn2OpNctNRqdPpsA\nAABQRDQkHSPpbEmXSTotIi6x/U7bB3Ubl8wmAABAWUqecH2uiDhL0llztr11gX2f1klMMpsAAAAo\nDJlNAACAEvVxNHopyGwCAACgMEOV2RyptdIEGm0kCdMc672uP7Mszf8LjZn5ptbaeLVGmjhuJorT\nqieJk0o4zXmNJIhTq6X57DhRHNWm0sSpJyrPTJrf82ikieMEqY9oJihIUom+k1OJiqeXMLgq/tEj\nswkAAIDCDFVmEwAAYNDQZxMAAADoEplNAACAMpHZBAAAALpDZhMAAKAsA7aCUBHIbAIAAKAwVDYB\nAABQGJrRAQAASuL8VmVkNgEAAFAYMpsAAABlYoAQAAAA0B0ymwAAACWq+nKVQ1XZrNfSvJt2M0mc\n1nij9xitNMnpZjNN9+SZRHHcStVdOk2cqNUTxUlUnnrvcUZG03x26qNpvkY8kuYaazJRnPp0kjCe\nSfTZafT+faFEnz+1Ev1ljES/D6nKo1aiOIlExWsgGBpDVdkEAAAYOBX/v6KwPpu2V9n+ke3LbF9i\n+9h8+9tt32D7wvx2YFFlAAAAQLmKzGw2JL02In5le3NJF9j+Xv7cRyPiQwUeGwAAYNNQ8cxmYZXN\niLhJ0k35/XtsXyZpx6KOBwAAgMHTl6mPbO8iaS9J5+WbjrF9ke3jbT+0H2UAAAAYOJGNRu/HrSyF\nVzZtr5D0NUmvjoi7JX1a0q6S9lSW+fzwAq872vZa22tvvT3N6G8AAAD0V6GVTdujyiqaX4mIr0tS\nRNwcEc2IaEn6rKS953ttRKyJiNURsXrl1ommMgEAABg00adbSYocjW5Jn5d0WUR8pG379m27PVfS\nxUWVAQAAAOUqcjT6kyW9RNJvbV+Yb3uzpMNs76msjn2NpH8ssAwAAAADjRWEuhQRP9P8y7ecVdQx\nAQAAMFj6MhodAAAAw4nlKgEAAMpEM3p1jNTTTKFUG6DOFZGoKJOJ4jRjvp4TG2/aaZLuUUuUvK+l\nOa9WPU15WqOjPccYHUtTltGxNLNF1MfSfB3V1vd+bSTJU9NJ4mhyKk2cmZmeQ3imkaAgUjTSxFGr\nlSZOM1GcRN9f0Ur1NyLReQ2SVH+0sEkZqsomAADAoBmgHFYh6LMJAACAwpDZBAAAKEvJE673A5lN\nAAAAFIbMJgAAQJnIbAIAAADdIbMJAABQEovR6AAAAEDXyGwCAACUicwmAAAA0B0ymwAAACVyxZfx\nJLMJAACAwpDZBAAAKMsQrCA0VJXNeqK5BUbrzSRxnCBGLUWQhCYTxWnW0nw0o54kjFojaS50cyxR\nnPHe44wliCFJzWVpGkhG703zno8kilNfP5YkjjckijM13XuQFDEkaWYmTZxGI02cZitRnDTf7cni\ntBLVQKL36xOpyqJE71UqFa/kDQqa0QEAAFCYocpsAgAADBomdQcAAAC6RGYTAACgTGQ2AQAAgO6Q\n2QQAACgRfTYBAACALpHZBAAAKBOZTQAAAKA7ZDYBAADKEvTZBAAAALpGZhMAAKBMZDYBAACA7gxV\nZnOk1koSZ6zWHJg4qc6pnihOrZbm37OpepryzIyMpokzWk8SpzWW5v+75rh7j7Gs9xiSNHNfmnMa\n3SxNnLEVad6rkfvSfHZG1o8niVPfMNNzjFqCGJKkqekkYTyVpjyeSRMnGo0kcZwoTjTTfA+qmeBv\nVooYktRKlMKLRNcmUZheWPTZBAAAALo2VJlNAACAgRPVTm2S2QQAAEBhyGwCAACUiD6bAAAAQJeo\nbAIAAKAwNKMDAACUJcSk7gAAAEC3yGwCAACUyAMwuXyRyGwCAACgMGQ2AQAAykSfTQAAAKA7ZDYB\nAABKVPVJ3YeqslmvpemBOz7SSBKnliBvPlpvJihJujgjia7xhkTXeMNomvOaHh9NEqcxUU8Sp7m8\n9ziNzdI0bIysd5I4M+uThNH0+jTXeGR9muszuj7N1+zo+t4/g/UNiX7PE8WpTc4kipPm+0LTacrj\nmTTlSRUnEpyXW2nec6U6p2aq8qQJg8UNVWUTAABgoISkqHZqkz6bAAAAKAyZTQAAgBJVvc8mmU0A\nAAAUhswmAABAmchsAgAAAN0hswkAAFASiz6bAAAAQNeobAIAAKAwNKMDAACUJYJJ3QEAAIBukdkE\nAAAoUdUHCA1VZXPErSRxxmqNRHGaPcdoyQlKIk3UZ5LEWTaSJs7UaJqP5oaxNOW5b3w0SZzJiTRx\nppf3Hqexop6gJFJjMk2c2oY0DS31yTS/EyPr08RJV57er8/IhjTv1chkmr+MI5PjaeJsSPPdXp/s\n/TtZkmpTieJMpvlbU5tOEGc6zXepZ9KckxtprrHuTRMGixuqyiYAAMDAqXhmkz6bAAAAKExhlU3b\nE7Z/afs3ti+x/Y58+yNsn2f797ZPtT1WVBkAAAAGnaM/t7IUmdmckvSMiNhD0p6S9rf9REkfkPTR\niNhN0p2SjiywDAAAAChRYZXNyMx2vR3NbyHpGZJOz7efKOmQosoAAAAw0EJSK/pzK0mhfTZt121f\nKOkWSd+TdKWkuyJidjjaOkk7FlkGAAAAlKfQymZENCNiT0k7Sdpb0mPm222+19o+2vZa22tvvT3R\nFAcAAACDJvp0K0lfRqNHxF2SzpH0RElb2p6dcmknSTcu8Jo1EbE6Ilav3DrN3HAAAADoryJHo6+0\nvWV+f5mk/SRdJulHkp6f73aEpG8WVQYAAIBBV/XR6EVO6r69pBNt15VVak+LiG/bvlTSKbbfLenX\nkj5fYBkAAABQosIqmxFxkaS95tl+lbL+mwAAAIhqLyHECkIAAAAoDJVNAAAAFKbIPpsDp15rJYkz\nUW8svVMHxmu9x6mV2eN3Ho1I8//L1Eiaj+Z0K81MBpPjo0nibGikiTPZ6P36bJhOU5apmUTv1VSa\n8sxMpXnPU8XxVJrfifqkByJG0jhTScKoPpnmvRqZTPNZHplM871cn0oTZ2Sy9799tak0fz/rieLU\nZhJNiXh9mjC9GrA/5cmR2QQAAIAkyfb+ti+3fYXtN87z/GtsX2r7Its/sP3wpWJS2QQAAChLvyZ0\n7yB7ms8gdJykAyTtLukw27vP2e3XklZHxOOULT/+waXiUtkEAACAlM0WdEVEXBUR05JOkXRw+w4R\n8aOIWJ8//IWyBXoWNVR9NgEAAAaJJXlwpj7aUQ/uybpO0j6L7H+kpO8sFZTKJgAAwHDYxvbatsdr\nImJN2+P5Rv/NWxO2fbik1ZKeutRBqWwCAACUKc0g/U7cFhGrF3l+naRVbY93knTj3J1s7yfp/0p6\nakQsOa8EfTYBAAAgSedL2s32I2yPSTpU0pntO9jeS9JnJB0UEbd0EpTMJgAAQIkGpc9mRDRsHyPp\nbEl1ScdHxCW23ylpbUScKen/SVoh6au2Jem6iDhosbhUNgEAACBJioizJJ01Z9tb2+7vt7ExqWwC\nAACUpcM5MDdl9NkEAABAYchsAgAAlCakAemzWRQymwAAACjMUGU2R2ppJrIarzWSxFlWn+k5xnit\n9xiDqDma5v+gRqueJM5MpCnPdCvNr9yG5mjPMaabaa7NZIKySNKGRpo4k40013hqZrDizEz3Hmd6\nOs17HonieDrN75Wn5puHeuPVp9PEqU2lOa/6krMXdqaW4P1KVZb6VJoMXqry6NxEcXrkaic2yWwC\nAACgOFQ2AQAAUJihakYHAAAYOAwQAgAAALpDZhMAAKAsITnN+OWBRWYTAAAAhSGzCQAAUCb6bAIA\nAADdIbMJAABQpmonNslsAgAAoDhkNgEAAEpk+mwCAAAA3SGzCQAAUKaKZzaHqrI54maaOLU0cZbV\np3uOMV5rJCiJNJro2tQrOjNtM9I0AsxEfWDiNFqDdU5TrTRfR9OJ4kw1U5UnzfWZbI72HCPVOU01\n0sSZTBRnppHmGk8nijMzneq80vyOtmYSnNd0mrJ4xkni1KbTxEF/DFVlEwAAYKCEpGrmae5Hn00A\nAAAUhswmAABASaxgNDoAAADQLSqbAAAAKAzN6AAAAGWiGR0AAADoDplNAACAMpHZBAAAALpDZhMA\nAKAsTOoOAAAAdI/MJgAAQImqPqn7UFU2a07zZo7XGkniLK9P9x6j1nsMSRqvzSSJU1eaa1xzmjaF\n+oC1TTQHqDGhFWnK0pSTxBm08sy00nw9zkQ9SZxWgvOabI0mKInUaKV5r1Jdm6lE71WjNVjlmU5U\nnulm7+WZTBBDkmZSXeNGmvJcnSQKljJUlU0AAICBU/HM5uCkWQAAAFA5ZDYBAABKE2Q2AQAAgG6R\n2QQAAChLiMwmAAAA0C0ymwAAAGUarFn6kiOzCQAAgMJQ2QQAAEBhaEYHAAAoUdWXqySzCQAAgMKQ\n2QQAACgTmU0AAACgO0OV2RyppZlbYLzWSBPHvcdZXptOUBJpvDaTJM6E05Sn7jT/5dUTzSdRc5o4\ndVX7v9cqacplF+FBWtF7bqA5YPmFZqS5xq1E59VMcI2ldNd5JupJ4qT57KR5rwbpnCTp3CRRehSS\nWtX+2zBY3zwAAAColKHKbAIAAAyWoM9mt2xP2P6l7d/YvsT2O/LtJ9i+2vaF+W3PosoAAACAchWZ\n2ZyS9IyIuNf2qKSf2f5O/tzrI+L0Ao8NAACwaah4ZrOwymZEhKR784ej+a3aVxMAAAAPUugAIdt1\n2xdKukXS9yLivPyp99i+yPZHbY8XWQYAAICBFtGfW0kKrWxGRDMi9pS0k6S9bT9W0psk/amkJ0ja\nStIb5nut7aNtr7W99tbbm0UWEwAAAAXpy9RHEXGXpHMk7R8RN0VmStIXJO29wGvWRMTqiFi9cus0\n83IBAAAMlNl5NvtxK0mRo9FX2t4yv79M0n6Sfmd7+3ybJR0i6eKiygAAAIByFTkafXtJJ9quK6vU\nnhYR37b9Q9srJVnShZJeUWAZAAAABlhIkWaVukFV5Gj0iyTtNc/2ZxR1TAAAAAwWlqsEAABAYViu\nEgAAoExM6l4dI07TJ2LUaaZimqjN9BxjeW0qQUnSlEX/v717j9a8qus4/v6c4wCCpFzECBFzMi/Z\nchLSBETyllopFYqmCWapKykvkaVlTawsSpNI0kS8gAvzwoCxgCV4idsyEYERZqAScfCCQchdFwgz\n3/747WOPp3POnHnm98zznDPv11qzzvPsZ//23s/+7Vnne/bev98P2Cn9lLMi9/dSzg49nasp+hk7\n0z2Nwekeno8w1VNb+jLdUx8vV32c8+VqIxl3E5a9jS6EaitsV8GmJEnSRJm59dEy5p8qkiRJGhln\nNiVJksZpme/ZdGZTkiRJI+PMpiRJ0jg5sylJkiQNx5lNSZKksSlnNiVJkqRhObMpSZI0LgVsWt4P\ntXBmU5IkSSPjzKYkSdI4uWdTkiRJGs52NbM5lX72RKyY2thLOTtO3bfVZezUQxkAu0zd20s5O6Wf\n9vRVzorc30s50/TzV+eK9DN2+mjPVPr5Tn31TV+mJqw90z31cx8m7Vz1xVmT0ZvOuFuwzDmzKUmS\nJA3HYFOSJEkjs10to0uSJE2Wgk0uo0uSJElDcWZTkiRpXAqqvKm7JEmSNBRnNiVJksbJPZuSJEnS\ncJzZlCRJGidv6i5JkiQNx5lNSZKkcamCTV6NLkmSJA3FmU1JkqRxWuZ7NrerYHM6/ZzMFdnYSzk7\n5b6JKKPPcnaeureXcnagrz6+v5dypvoaO/SzVNLHWJ6mn+/U1/LIdPopZ9KWa6bH3YAB0+mpk3sy\naeeqL9NMVj/3YWrCxo6Wlu0q2JQkSZo05Z5NSZIkaTjObEqSJI1NLfs9m85sSpIkaWQMNiVJkjQy\nLqNLkiSNSwGbXEaXJEmShuLMpiRJ0jiVtz6SJEmShuLMpiRJ0pgUUO7ZlCRJkobjzKYkSdK4VLln\nU5IkSRrWkpjZvPyqe2+Z3vu6GzaTbU/gloWzXNdXk7ZXi+hjbSX7eNuwn0fPPh49+3jr7TfuBsBk\n7dlM8lzgBGAaOLmqjpv1+Y7AqcD+wHeBI6pqw0JlLolgs6oeurk8Sb5cVQdsi/Zsr+zj0bOPtw37\nefTs49Gzj9W3JNPAPwHPBr4FXJbkrKq6ZiDbq4DbquqnkrwE+FvgiIXKdRldkiRpnGrTtvm3eU8G\nrquq66vqB8DHgBfOyvNC4JT2+nTgmUmyUKEGm5IkSQLYB/jmwPtvtbQ581TV/cAdwB4LFbokltEX\n6aRxN2A7YB+Pnn28bdjPo2cfj559vAzcxW3nfbZO33MbVbdTki8PvD+pqgbH0VwzlLM3lC4mz48e\nUDU5m1IlSZI0HkmeCqyuql9q798CUFV/M5DnvJbn35M8APhv4KG1QEDpMrokSZIALgMeneQnk+wA\nvAQ4a1aes4Aj2+vDgc8vFGjCMgg2kzw3yX8muS7Jn4y7PctVkg1Jrk6ydtYUvIaU5INJbk6ybiBt\n9ySfSfLV9nO3cbZxqSCOxEoAAAjQSURBVJunj1cn+XYby2uTPH+cbVzqkuyb5N+SXJtkfZLXt3TH\nco8W6GfHs3rT9mAeDZwHXAt8oqrWJzk2yQtatg8AeyS5DngTsNnYa0kvo7dL9P+LgUv0gZfOukRf\nPUiyATigqrynW0+SHALcDZxaVU9oaX8H3FpVx7U/nnarqj8eZzuXsnn6eDVwd1W9c5xtWy6S7A3s\nXVVXJNkVuBw4DDgKx3JvFujnF+N41oRb6jObi7lEX5pIVXURcOus5MFbSpxC98tEQ5qnj9WjqvpO\nVV3RXt9FNxuyD47lXi3Qz9LEW+rB5mIu0Vc/Cjg/yeVJXj3uxixjD6uq70D3ywXYa8ztWa6OTnJV\nW2Z3ebcnSR4J/BxwKY7lkZnVz+B41oRb6sHmFl9+r6EdVFVPAp4HvK4tT0pL0XuBlcAq4DvA34+3\nOctDkgcBa4A3VNWd427PcjVHPzueNfGWerD5LWDfgfcPB24cU1uWtaq6sf28GTiTbguD+ndT25s1\ns0fr5jG3Z9mpqpuqamNVbQLej2N5qyVZQRcAnVZVZ7Rkx3LP5upnx7OWgqUebC7mEn1tpSS7tA3p\nJNkFeA6wbuGjNKTBW0ocCfzrGNuyLM0EQM2v4VjeKu0xdR8Arq2qdw185Fju0Xz97HjWUrCkr0YH\naLd5+AdgGvhgVb19zE1adpI8im42E7qnTn3Uft56Sf4FOBTYE7gJ+AvgU8AngEcA3wBeVFVe4DKk\nefr4ULolxwI2AK+Z2VuoLZfkYOBi4Gpg5uHLb6XbT+hY7skC/fxSHM+acEs+2JQkSdLkWurL6JIk\nSZpgBpuSJEkaGYNNSZIkjYzBpiRJkkbGYFOSJEkjY7ApTZgkP57kY0m+luSaJOcm+ekhyjksyeNH\n0cbN1HtBe5zeYvKuTnLMrLQNSfZsr7+wmePfOmQbz03ykCGOOyrJifOk/0+Ste3fqcO0S5KWI4NN\naYK0GzefCVxQVSur6vF099J72BDFHQZs02AzyXSf5VXVgZvJskXBZjpTVfX8qrp9K5o2l49X1ar2\n7xVz1P2AnuuTpCXBYFOaLL8I3FdV/zyTUFVrq+riJIcmOXsmPcmJSY5qr49rs6BXJXlnkgOBFwDv\naDNtK5OsSvLFlufMJLu1Yy9IcnySi5Jcm+Tnk5yR5KtJ/mqgvpcn+VIr730zgWWSu5Mcm+RS4KnA\nrcDGJNNJPpxkXZKrk7xxSzsjyd3t596tfWtbeU9LchzwwJZ2Wsv3pvb5uiRvaGmPbN/rPcAVwL6z\nZk9f0frkK0k+0tJ+NcmlSa5M8tkkwwT7M33710kuBF6f5KFJ1iS5rP07qOXbI8n5rb73JbkhyZ6t\n7esGyjsmyer2emWSTye5PMnFSR7b0j+c5B+TfCHJ9UkOHzj+ze1cfKWNmZVJrhj4/NFJLh/mu0rS\nfPxLW5osTwC26Jd9kt3pHlP32KqqJA+pqtuTnAWcXVWnt3xXAb9fVRcmOZbuaTpvaMX8oKoOSfJ6\nuscK7k8XNH4tyfHAXsARwEFVdV8L3F4GnArsAqyrqj9vZV3S6tsf2KeqntDez7ds/cYkLx94/xNz\n5PlN4LyqensLcnduAfjRVbVqoL5XAk8BAlzagrzbgMcAr6yq32t5Z/ruZ4A/bd/rltaXM9/hF1p/\n/g7wZuAP52n/jCPSPeUF4ISq+lB7/ZCqenqr76PA8VV1SZJHAOcBj6M7F5dU1bFJfhl49WbqAjgJ\neG1VfTXJU4D3AM9on+0NHAw8lu6xkacneR7dbPdTqur7SXavqluT3JFkVVWtbf334UXULUmLZrAp\nLX13AvcAJyc5Bzh7doYkD6YLei5sSacAnxzIclb7eTWwfuZxd0muB/alC1z2By5rgdoDgZvbMRuB\nNXO063rgUUneDZwDnD9P+4+vqncOtHXDHHkuAz6YZAXwqRYYzXYwcGZVfa+VcwbwtPbdbqiqL85x\nzDOA06vqFoCBxyk+HPh4uudO7wB8fZ62D/p4VR09V/rA62cBj58JdoEfS7IrcAjw660N5yS5baGK\nkjwIOBD45EBZOw5k+VRVbQKuGZiVfRbwoar6fqtn5rueDLwyyZvo/qB48ma/qSRtAZfRpcmyni6o\nm8v9/Oj/2Z0Aqup+ugBhDd3M1aeHqPfe9nPTwOuZ9w+gmyk8ZWBP4mOqanXLc09VbZxdYFXdBjwR\nuAB4HV1QM5SquoguIPs28JEk/29PZGvjfL43T3ronik927uBE6vqZ4HX0Pp6SIN1TwFPHejHfarq\nrvbZXO2Y85y3tNsHyllVVY8byDd4DjPwc6461gDPA34FuLyqvru4ryVJi2OwKU2WzwM7JvndmYR0\neyifDtxANyu2Y5upfGb7/EHAg6vqXLpl8VXt0LuAXQGq6g7gtiRPa5/9FjAzy7kYnwMOT7JXq3P3\nJPstdEDbEzlVVWuAtwFP2oL6Zpe1H3BzVb0f+MBAWfe12U6Ai4DDkuycZBe6rQUXb6bozwEvTrJH\nq2dmGf3BdIEtwJHDtnsO5wM/nP1MMnOuLqLblkBb7t6tpd8E7NX2dO5IFxBSVXcCX0/yonZMkjxx\nEXX/dpKd2zG7t7LuoVvOfy/wofkPl6ThGGxKE6Sqii5Iena6Wx+tB1YDN1bVN4FPAFcBpwFXtsN2\nBc5uezIvBGYuxPkY8EftopOVdEHTO1q+VcCxW9Cua4A/A85vx3+Gbl/gQvYBLkiylm4f4FsWW98c\nDgXWJrkS+A3ghJZ+EnBVktOq6opWz5eAS4GTq+rKOcr6oapaD7wduDDJV4B3tY9W0y1RXwzcshXt\nnu0PgAPSXZB0DfDalv6XwCHtYp3nAN9o7buP7jxdSrc94j8GynoZ8KrW7vXACxequKo+Tbel4Mvt\nnAzecuo0ulnP+bY6SNLQ0v1ukyRNirZv9YCZvaTboL5j6GbH37Yt6pO0ffECIUnajiU5E1jJ/13J\nLkm9cmZTkiRJI+OeTUmSJI2MwaYkSZJGxmBTkiRJI2OwKUmSpJEx2JQkSdLIGGxKkiRpZP4XGsDM\nyyvyKskAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1a10b07080>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from lifetimes.plotting import plot_probability_alive_matrix\n",
    "plt.figure(figsize=(12, 10))\n",
    "plot_probability_alive_matrix(bgf, cmap='viridis');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Apparently](http://mktg.uni-svishtov.bg/ivm/resources/Counting_Your_Customers.pdf), we can calculate the expected number of purchases over the next $t$ periods with\n",
    "\n",
    "\\begin{align*}\n",
    "    E\\left(X(t) \\vert \\lambda, p\\right) &= \\lambda t \\cdot P(\\tau > t) + \\int_0^t \\lambda \\tau g(\\tau \\vert \\lambda, p)  \\tau \\\\\n",
    "    &= \\frac{1}{p} - \\frac{1}{p} e^{-\\lambda pt}\n",
    "\\end{align*}\n",
    "\n",
    "With some fancy math and substitutions, the following calculation does that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.242592689807 4.413541294 0.792885943367 2.42572909204\n"
     ]
    }
   ],
   "source": [
    "from scipy import special\n",
    "\n",
    "r, α, a, b = bgf._unload_params('r', 'alpha', 'a', 'b')\n",
    "print(r, α, a, b)\n",
    "\n",
    "def conditional_n_purchases(t, frequency, recency, T):\n",
    "    x = frequency\n",
    "\n",
    "    hyp_term = special.hyp2f1(r + x, b + x, a + b + x - 1, t / (α + T + t))\n",
    "    first_term = (a + b + x - 1) / (a - 1)\n",
    "    second_term = (1 - hyp_term * ((α + T) / (α + t + T)) ** (r + x))\n",
    "    numerator = first_term * second_term\n",
    "\n",
    "    denominator = 1 + (x > 0) * (a / (b + x - 1)) * ((α + T) / (α + recency)) ** (r + x)\n",
    "\n",
    "    return numerator / denominator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.18315716386398942"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "conditional_n_purchases(t=5, frequency=2, recency=30.43, T=38.86)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Originally, `lifetimes`' documentation had code similar to the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ID\n",
       "1       0.183157\n",
       "2       0.029758\n",
       "3       0.027552\n",
       "4       0.027552\n",
       "5       0.027552\n",
       "          ...   \n",
       "2353    0.037717\n",
       "2354    0.665432\n",
       "2355    0.037717\n",
       "2356    0.559679\n",
       "2357    0.037717\n",
       "Length: 2357, dtype: float64"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data.apply(lambda row: conditional_n_purchases(5,\n",
    "                                               row['frequency'],\n",
    "                                               row['recency'],\n",
    "                                               row['T']),\n",
    "           axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that's doing a `.apply(..., axis=1)`. Let's time it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "88 ms ± 1.69 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "t = 5\n",
    "# Using .apply(λ row:, axis=1)\n",
    "data.apply(lambda row: conditional_n_purchases(5,\n",
    "                                               row['frequency'],\n",
    "                                               row['recency'],\n",
    "                                               row['T']),\n",
    "           axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You almost never want to use `.apply` with axis=1. `.apply` It's probably doing way more work that you actually want, including:\n",
    "\n",
    "- A bunch of type inference\n",
    "- Some \"helpful\" reductions of output shape\n",
    "- Is essentially a for loop internally\n",
    "\n",
    "If you *have* to use an interative solution (instead of vectorized), use `.itertuples` which returns an iterator of `namedtuples`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Pandas(Index=1, frequency=2, recency=30.43, T=38.86)"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(data.itertuples())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exercise: Use `.itertuples` to call `conditional_n_purchases` on each row in `data`.\n",
    "\n",
    "- Make sure to wrap the list of results in a in a `Series`\n",
    "- Time your solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "29.7 ms ± 592 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "t = 5\n",
    "pd.Series([\n",
    "    conditional_n_purchases(t, row.frequency, row.recency, row.T)\n",
    "    for row in data.itertuples()\n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-success\" data-title=\"Vectorized\">\n",
    "  <h1><i class=\"fa fa-tasks\" aria-hidden=\"true\"></i> Exercise: Vectorized Solution</h1>\n",
    "</div>\n",
    "\n",
    "\n",
    "Can we improve on that? Look at the functions we use in `conditional_n_purchases`. Do they take scalars, arrays, or either?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = 5\n",
    "conditional_n_purchases(t, ...)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.59 ms ± 235 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%load solutions/performance_vectorized.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's quite natural to say \"I have this complicated function `f` to apply to each \n",
    "row, I'll just just use `.apply(f, axis=1)`\". Avoid that temptation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "- Get good performance by avoiding antipattern\n",
    "- Avoid `object` dtype where possible\n",
    "- Avoid iteration where possible"
   ]
  }
 ],
 "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}