04_lista_e_deque.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "Estrutura de Dados - Listas e deques\n",
    "==========================================\n",
    "\n",
    "Capítulo 10 do livro texto sugerido:\n",
    "Introduction to Algorithms, Fourth Edition\n",
    "By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein\n",
    "https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/\n",
    "\n",
    "Conteúdo\n",
    "========\n",
    "\n",
    "## Listas\n",
    "Como mostrado na Seção de introdução, listas são implementadas de maneira bastante semelhante com pilhas e filas.\n",
    "\n",
    "São compostas por elementos de lista contendo um valor e uma referência para o elemento, a sua frente, enquanto a fila contém a referência para o primeiro elemento.\n",
    "\n",
    "Diferente da pilha e fila, porém, a posição de inserção e remoção dos dados não é pré-determinada, aumentando a complexidade da gerência dos dados nesta estrutura.\n",
    "\n",
    "A implementação de uma lista é mostrada abaixo"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class ElementoLista():\n",
    "    def __init__(self, valorInicial):\n",
    "        # Cria um elemento de lista\n",
    "        # contendo o valor enfileirado\n",
    "        self.valor = valorInicial\n",
    "        # e a referência para o elemento seguinte a ele na lista\n",
    "        self.proximo = None\n",
    "\n",
    "class Lista():\n",
    "    def __init__(self):\n",
    "        # Cria uma lista vazia\n",
    "        self.primeiroElementoLista = None\n",
    "\n",
    "    def buscaElementoPosicao(self, posicao):\n",
    "        # Procure o elemento atualmente na posição\n",
    "        elementoPosicao = self.primeiroElementoLista\n",
    "        posicaoBuscada = 0\n",
    "        while posicaoBuscada != posicao:\n",
    "            if elementoPosicao is None:\n",
    "                raise Exception(f\"Posição não existente na lista: {posicao}\")\n",
    "            if elementoPosicao.proximo is None and posicao == -1:\n",
    "                return elementoPosicao\n",
    "            elementoPosicao = elementoPosicao.proximo\n",
    "            posicaoBuscada += 1\n",
    "        return elementoPosicao\n",
    "\n",
    "    def insereValor(self, valor, posicao=0):\n",
    "        # Cria um elemento para a lista\n",
    "        novoElementoLista = ElementoLista(valorInicial=valor)\n",
    "\n",
    "        if posicao == -1 and self.primeiroElementoLista is None:\n",
    "                self.primeiroElementoLista = novoElementoLista\n",
    "                return None\n",
    "\n",
    "        # E a posição de inserção seja a primeira posição\n",
    "        if posicao == 0:\n",
    "            if self.primeiroElementoLista is not None:\n",
    "                novoElementoLista.proximo = self.primeiroElementoLista\n",
    "            self.primeiroElementoLista = novoElementoLista\n",
    "        # Se a lista não estiver vazia\n",
    "        else:\n",
    "            posicao += 0 if posicao != -1 else 1\n",
    "            # Busca elemento anterior a posição\n",
    "            elementoPosicao = self.buscaElementoPosicao(posicao-1)\n",
    "            # Salva a referência para o elemento na\n",
    "            # posição como próximo do novo elemento\n",
    "            novoElementoLista.proximo = elementoPosicao.proximo\n",
    "            # Substitui elemento na posição pelo novo elemento\n",
    "            elementoPosicao.proximo = novoElementoLista\n",
    "        return None\n",
    "\n",
    "    def removerValor(self, posicao=0):\n",
    "        if posicao == 0:\n",
    "            if self.primeiroElementoLista is None:\n",
    "                return None\n",
    "            else:\n",
    "                elementoRemovido = self.primeiroElementoLista\n",
    "                self.primeiroElementoLista = self.primeiroElementoLista.proximo\n",
    "                return elementoRemovido.valor\n",
    "        else:\n",
    "            elementoPosicao = self.buscaElementoPosicao(posicao-1)\n",
    "            if elementoPosicao.proximo is not None:\n",
    "                elementoRemovido = elementoPosicao.proximo\n",
    "                elementoPosicao.proximo = elementoRemovido.proximo\n",
    "                return elementoRemovido.valor\n",
    "            return None"
   ]
  },
  {
   "cell_type": "markdown",
   "source": [
    "Quando inserimos um elemento na primeira posição, temos complexidade superior assintótica $O(1)$ para gravar a referência/ponteiro para o próximo elemento do novo elemento (`novoElementoLista.proximo = self.primeiroElementoLista`) e substituir as referências/ponteiros do início da lista pelo novo elemento (`self.primeiroElementoLista = novoElementoLista`).\n",
    "\n",
    "Para mostrar que de fato estas operações são rápidas, utilizaremos as seguintes funções."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "outputs": [],
   "source": [
    "import time\n",
    "from functools import partial\n",
    "import statistics\n",
    "from matplotlib import pyplot as plt\n",
    "\n",
    "# Função decoradora que envelopa chamada original\n",
    "# e calcula o tempo passado\n",
    "def marcaTempo(func):\n",
    "    def funcWrapper(*args, **kwargs):\n",
    "        inicio = time.time()\n",
    "        resultado = func(*args, **kwargs)\n",
    "        fim = time.time()\n",
    "        #print(f\"Tempo gasto em {func.__name__}: {fim-inicio}s\")\n",
    "        return resultado, fim-inicio\n",
    "    return funcWrapper\n",
    "\n",
    "# Função de benchmark\n",
    "def benchmark(func, itens=10000, pulaImpressao=False):\n",
    "    tempos = []\n",
    "    for i in range(itens):\n",
    "        resultado, tempo = func(valor=i)\n",
    "        tempos.append(tempo)\n",
    "    if not pulaImpressao:\n",
    "        print(f\"Benchmark levou {sum(tempos):.2E}s no total, e {statistics.mean(tempos):.2E}±{statistics.stdev(tempos):.2E}s por iteração\")\n",
    "        plt.scatter(list(range(itens)), tempos)\n",
    "        plt.ylabel(\"Tempo (s)\")\n",
    "        plt.show()"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Com as funções de benchmark prontas, podemos executar nossos testes.\n",
    "\n",
    "Primeiro inserindo 10 mil elementos no início da lista."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Benchmark levou 2.58E-02s no total, e 2.58E-06±2.04E-05s por iteração\n"
     ]
    },
    {
     "data": {
      "text/plain": "<Figure size 432x288 with 1 Axes>",
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZsAAAD4CAYAAAA6j0u4AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8qNh9FAAAACXBIWXMAAAsTAAALEwEAmpwYAAAfvElEQVR4nO3df5QdZZ3n8feHTojtONL86MOQDpggEU8jSvAOA+uPg+CYoK7JOlntjKPRiYfVgbM7425mkuOcwWVnDyCzw44jiMwkA7JIwiAT+yBOVglHXXcIdAySBGltEoQ0KG0gwZFeSDff/eM+jTc3t7vrJvfpm775vM6pk6qnnuep57nVqe+tqudWKSIwMzPL6ZhmN8DMzFqfg42ZmWXnYGNmZtk52JiZWXYONmZmlt2MZjfgSHTSSSfF3Llzm90MM7NpZcuWLb+IiM5a6xxsapg7dy59fX3NboaZ2bQi6afjrfNlNDMzy87BxszMsnOwMTOz7BxszMwsOwcbMzPLzqPRbFrZsHWQazf289TeYWZ3tLNy4ZksWdDV7GaZ2SSyntlIWiSpX9KApFU11s+StD6t3yxpbsW61Sm9X9LCivS1kp6RtL2qrvWSHkrT45IeSulzJQ1XrLsxX48tpw1bB1l91zYG9w4TwODeYVbftY0NWweb3TQzm0S2YCOpDbgeuAToBpZJ6q7KtgJ4LiLOAK4Drkllu4Ee4CxgEXBDqg/g5pR2gIj4cEScExHnAF8D7qpY/djYuoj4VIO6aFPs2o39DO8fPSBteP8o127sb1KLzKyonGc25wEDEbEzIl4C1gGLq/IsBm5J83cCF0tSSl8XES9GxC5gINVHRHwXeHa8jabyHwJub2RnrPme2jtcV7qZHTlyBpsu4MmK5d0prWaeiBgB9gEnFiw7nncAP4+In1SkzZO0VdJ3JL2jeBfsSDK7o72udDM7crTiaLRlHHhW8zRwWkQsAD4DfFXSa6sLSbpUUp+kvqGhoSlqqtVj5cIzaZ/ZdkBa+8w2Vi48s0ktMrOicgabQeDUiuU5Ka1mHkkzgOOAPQXLHiTV8UFg/VhauhS3J81vAR4D3lBdNiJuiohSRJQ6O2s+R86abMmCLq764Nl0dbQjoKujnas+eLZHo5lNAzmHPj8IzJc0j3Kg6AF+vypPL7Ac+BdgKbApIkJSL+UzkL8GZgPzgQcKbPPdwKMRsXssQVIn8GxEjEo6PdW18/C6Zs2yZEGXg4vZNJQt2ETEiKTLgY1AG7A2InZIuhLoi4heYA1wq6QByjf9e1LZHZLuAB4BRoDLImIUQNLtwIXASZJ2A1dExJq02R4OHhjwTuBKSfuBl4FPRcS4AwzMzKzxFBHNbsMRp1QqhV8xYGZWH0lbIqJUa10rDhAwM7MjjIONmZll52BjZmbZOdiYmVl2DjZmZpadg42ZmWXnYGNmZtk52JiZWXYONmZmlp2DjZmZZedgY2Zm2TnYmJlZdg42ZmaWnYONmZll52BjZmbZOdiYmVl2DjZmZpadg42ZmWXnYGNmZtllDTaSFknqlzQgaVWN9bMkrU/rN0uaW7FudUrvl7SwIn2tpGckba+q63OSBiU9lKb3TlaXmZlNjWzBRlIbcD1wCdANLJPUXZVtBfBcRJwBXAdck8p2Az3AWcAi4IZUH8DNKa2W6yLinDTdU6AuMzObAjnPbM4DBiJiZ0S8BKwDFlflWQzckubvBC6WpJS+LiJejIhdwECqj4j4LvBsHe0Yty4zM5saOYNNF/BkxfLulFYzT0SMAPuAEwuWreVySQ+nS23H19EOMzPLqJUGCHwJeD1wDvA08D/qKSzpUkl9kvqGhoYyNM/M7OiVM9gMAqdWLM9JaTXzSJoBHAfsKVj2ABHx84gYjYiXgb/j15fKCtUVETdFRCkiSp2dnZN0zczM6pEz2DwIzJc0T9KxlG/S91bl6QWWp/mlwKaIiJTek0arzQPmAw9MtDFJp1Qs/jtgbLRa3XWZmVljzchVcUSMSLoc2Ai0AWsjYoekK4G+iOgF1gC3ShqgfNO/J5XdIekO4BFgBLgsIkYBJN0OXAicJGk3cEVErAE+L+kcIIDHgf8wWV1mZjY1VD6RsEqlUin6+vqa3Qwzs2lF0paIKNVa10oDBMzM7AjlYGNmZtk52JiZWXYONmZmlp2DjZmZZedgY2Zm2TnYmJlZdg42ZmaWnYONmZll52BjZmbZOdiYmVl2DjZmZpadg42ZmWXnYGNmZtk52JiZWXYONmZmlp2DjZmZZedgY2Zm2TnYmJlZdg42ZmaWXdZgI2mRpH5JA5JW1Vg/S9L6tH6zpLkV61an9H5JCyvS10p6RtL2qrqulfSopIcl/ZOkjpQ+V9KwpIfSdGO+HpuZWS3Zgo2kNuB64BKgG1gmqbsq2wrguYg4A7gOuCaV7QZ6gLOARcANqT6Am1NatW8Bb4qINwM/BlZXrHssIs5J06ca0T8zMysu55nNecBAROyMiJeAdcDiqjyLgVvS/J3AxZKU0tdFxIsRsQsYSPUREd8Fnq3eWET874gYSYv3A3Ma3SEzMzs0OYNNF/BkxfLulFYzTwoU+4ATC5adyB8C36xYnidpq6TvSHpHrQKSLpXUJ6lvaGiojk2ZmdlkWm6AgKTPAiPAbSnpaeC0iFgAfAb4qqTXVpeLiJsiohQRpc7OzqlrsJnZUSBnsBkETq1YnpPSauaRNAM4DthTsOxBJH0ceD/wkYgIgHQpbk+a3wI8Bryh/u6YmdmhyhlsHgTmS5on6VjKN/x7q/L0AsvT/FJgUwoSvUBPGq02D5gPPDDRxiQtAv4U+EBEvFCR3jk2uEDS6amunYfdOzMzK2xGroojYkTS5cBGoA1YGxE7JF0J9EVEL7AGuFXSAOWb/j2p7A5JdwCPUL4kdllEjAJIuh24EDhJ0m7giohYA3wRmAV8qzzGgPvTyLN3AldK2g+8DHwqIg4aYGBmZvkoXW2yCqVSKfr6+prdDDOzaUXSlogo1VrXcgMEzMzsyONgY2Zm2TnYmJlZdg42ZmaWnYONmZll52BjZmbZOdiYmVl2DjZmZpadg42ZmWXnYGNmZtk52JiZWXYONmZmlp2DjZmZZTfpKwYklYB3ALOBYWA78K2IeC5z28zMrEWMe2Yj6ROSfgCsBtqBfuAZ4O3AtyXdIum0qWmmmZlNZxOd2bwaeFtEDNdaKekcym+9fCJDu8zMrIWMG2wi4vqJCkbEQw1vjZmZtaRJBwhI+ryk10qaKeleSUOS/mAqGmdmZq2hyGi090TE88D7gceBM4CVORtlZmatpUiwGbvU9j7gHyNiX9HKJS2S1C9pQNKqGutnSVqf1m+WNLdi3eqU3i9pYUX6WknPSNpeVdcJkr4l6Sfp3+NTuiR9IdX1sKRzi7bfzMwao0iwuVvSo8BbgXsldQL/b7JCktqA64FLgG5gmaTuqmwrgOci4gzgOuCaVLYb6AHOAhYBN6T6AG5OadVWAfdGxHzg3rRM2v78NF0KfKlAn83MrIEmDTYRsQr4N0ApIvYDLwCLC9R9HjAQETsj4iVgXY1yi4Fb0vydwMWSlNLXRcSLEbELGEj1ERHfBZ6tsb3Kum4BllSkfyXK7gc6JJ1SoP1mZtYgE/3O5u1j8xHxbESMpvlfRcTP0qCBN01QdxfwZMXy7pRWM09EjAD7gBMLlq12ckQ8neZ/BpxcRzuQdKmkPkl9Q0NDk2zKzMzqMdHvbH5P0ueBfwa2AEPAqygPEHgX8DrgP2dv4SGIiJAUdZa5CbgJoFQq1VXWzMwmNtHvbP5E0gnA7wH/HjiF8uNqfgR8OSL+zyR1DwKnVizPSWm18uyWNAM4DthTsGy1n0s6JSKeTpfJnqmjHWZmltGE92zS5bO/i4iPR8TCiFgSEasLBBqAB4H5kuZJOpbyDf/eqjy9wPI0vxTYFBGR0nvSaLV5lG/uPzDJ9irrWg58vSL9Y2lU2vnAvorLbWZmNgUmfRDnoYqIEUmXAxuBNmBtROyQdCXQFxG9wBrgVkkDlG/696SyOyTdATwCjACXjd0zknQ7cCFwkqTdwBURsQa4GrhD0grgp8CHUlPuAd5LeZDBC8AncvXZzMxqU/lEwiqVSqXo6+trdjPMzKYVSVsiolRrnd9nY2Zm2RV5n81M4NPAO1PSd4Ab029uzMzMJlXkns2XgJnADWn5oyntk7kaZWZmraVIsPntiHhLxfImST/M1SAzM2s9Re7ZjEp6/diCpNOB0XxNMjOzVlPkzGYlcJ+knYAoPznAw4fNzKywSYNNRNwraT5wZkrqj4gX8zbLzMxaSZHRaK8C/gh4OxDA9yTdGBGTvmbAzKyRNmwd5NqN/Ty1d5jZHe2sXHgmSxZM9oxeOxIUuYz2FeCXwN+m5d8HbqX8vDQzsymxYesgq+/axvD+8i3jwb3DrL5rG4ADzjRQJNi8KSIqX3p2n6RHcjXIzKyWazf2vxJoxgzvH+Xajf0ONtNAkdFoP0gPsARA0u8AfpaLmU2pp/YO15VuR5YiZzZvBf6vpCfS8mlAv6RtlF8d8+ZsrTMzS2Z3tDNYI7DM7mhvQmusXkWCzaLsrTAzm8TKhWcecM8GoH1mGysXnjlBKTtSFBn6/FNJx1N+AdmMivQf5GyYmVmlsfsyHo02PRUZ+vzfgI8Dj1Ee+kz696J8zTIzO9iSBV0OLtNUkctoHwJeHxEv5W6MmZm1piKj0bYDHZnbYWZmLazImc1VwFZJ24FXHlMTER/I1iozM2spRYLNLcA1wDbg5bzNMTOzVlTkMtoLEfGFiLgvIr4zNhWpXNIiSf2SBiStqrF+lqT1af1mSXMr1q1O6f2SFk5Wp6TvSXooTU9J2pDSL5S0r2LdXxRpu5mZNU6RM5vvSboK6OXAy2gTDn2W1AZcD/wusBt4UFJvRFQ+6mYF8FxEnCGph/IZ1IcldQM9wFnAbODbkt6QytSsMyLeUbHtrwFfr+xDRLy/QF/NzCyDIsFmQfr3/Iq0IkOfzwMGImIngKR1wGKgMtgsBj6X5u8EvihJKX1depXBLkkDqT4mq1PSa1Pb/M4dM7MjRJEfdb7rEOvuAp6sWN4N/M54eSJiRNI+4MSUfn9V2bHB9ZPVuQS4NyKer0i7IL3K+ingv0TEjurGSroUuBTgtNNOm6xvZmZWh0nv2Ug6WdIaSd9My92SVuRv2iFbBtxesfwD4HUR8RbKr0nYUKtQRNwUEaWIKHV2duZvpZnZUaTIAIGbgY2U750A/Bj44wLlBik/4mbMnJRWM4+kGcBxwJ4Jyk5Yp6STKF9u+8ZYWkQ8HxH/mubvAWamfGZmNkXGDTbp4A9wUkTcQRr2HBEjwOh45So8CMyXNE/SsZRv+PdW5ekFlqf5pcCmiIiU3pNGq80D5gMPFKhzKXB35VtEJf1Wug+EpPNSn/cUaL+ZmTXIRPdsHgDOBX4l6UTSc9HSu232TVZxugdzOeWzojZgbUTskHQl0BcRvcAa4NY0AOBZysGDlO8Oyjf+R4DLImI0bf+gOis22wNcXdWUpcCnJY0Aw0BPCmhmZjZFNN5xV9LWiFgg6VzK9zreRPnRNZ3A0oh4eOqaObVKpVL09fn9cGZm9ZC0JSJKtdZNdGbTKekzaf6fgHsAUf6tzbuBlg02ZmbWWBMFmzbgNZQDTKVX52uOmZm1oomCzdMRceWUtcTMzFrWREOfq89ozMzMDslEwebiKWuFmZm1tHGDTUQ8O5UNMTOz1lXkCQJmZmaHxcHGzMyyc7AxM7PsHGzMzCw7BxszM8vOwcbMzLJzsDEzs+wcbMzMLDsHGzMzy87BxszMsnOwMTOz7BxszMwsOwcbMzPLLmuwkbRIUr+kAUmraqyfJWl9Wr9Z0tyKdatTer+khZPVKelmSbskPZSmc1K6JH0h5X9Y0rk5+2xmZgfLFmwktQHXA5cA3cAySd1V2VYAz0XEGcB1wDWpbDfQA5wFLAJukNRWoM6VEXFOmh5KaZcA89N0KfClhnfWzMwmlPPM5jxgICJ2RsRLwDpgcVWexcAtaf5O4GJJSunrIuLFiNgFDKT6itRZbTHwlSi7H+iQdEojOmhmZsXkDDZdwJMVy7tTWs08ETEC7ANOnKDsZHX+93Sp7DpJs+poB5IuldQnqW9oaKhYD83MrJBWGiCwGngj8NvACcCf1VM4Im6KiFJElDo7O3O0z8zsqJUz2AwCp1Ysz0lpNfNImgEcB+yZoOy4dUbE0+lS2YvAP1C+5Fa0HWZmllHOYPMgMF/SPEnHUr7h31uVpxdYnuaXApsiIlJ6TxqtNo/yzf0HJqpz7D5MuuezBNhesY2PpVFp5wP7IuLpLD02M7OaZuSqOCJGJF0ObATagLURsUPSlUBfRPQCa4BbJQ0Az1IOHqR8dwCPACPAZRExClCrzrTJ2yR1AgIeAj6V0u8B3kt5kMELwCdy9dnMzGpT+UTCKpVKpejr62t2M8zMphVJWyKiVGtdKw0QMDOzI5SDjZmZZedgY2Zm2TnYmJlZdg42ZmaWnYONmZll52BjZmbZOdiYmVl2DjZmZpadg42ZmWXnYGNmZtk52JiZWXbZnvps9duwdZBrN/bz1N5hZne0s3LhmSxZcNBLRc3Mph0HmyPEhq2DrL5rG8P7RwEY3DvM6ru2ATjgmNm052CTSb1nKddu7H8l0IwZ3j/KtRv7HWzMbNpzsMngUM5Snto7XFe6mdl04gECGUx0ljKe2R3tdaWbmU0nDjYZHMpZysqFZ9I+s+2AtPaZbaxceGZD22Zm1gwONhkcylnKkgVdXPXBs+nqaEdAV0c7V33wbN+vMbOWkDXYSFokqV/SgKRVNdbPkrQ+rd8saW7FutUpvV/SwsnqlHRbSt8uaa2kmSn9Qkn7JD2Upr/I2Wc49LOUJQu6+P6qi9h19fv4/qqLHGjMrGVkCzaS2oDrgUuAbmCZpO6qbCuA5yLiDOA64JpUthvoAc4CFgE3SGqbpM7bgDcCZwPtwCcrtvO9iDgnTVc2vrcH8lmKmdmBco5GOw8YiIidAJLWAYuBRyryLAY+l+bvBL4oSSl9XUS8COySNJDqY7w6I+KesUolPQDMydWxIpYs6HJwMTNLcl5G6wKerFjendJq5omIEWAfcOIEZSetM10++yjwzxXJF0j6oaRvSjqrVmMlXSqpT1Lf0NBQsR6amVkhrThA4AbguxHxvbT8A+B1EfEW4G+BDbUKRcRNEVGKiFJnZ+fUtNTM7CiRM9gMAqdWLM9JaTXzSJoBHAfsmaDshHVKugLoBD4zlhYRz0fEv6b5e4CZkk46nI6ZmVl9cgabB4H5kuZJOpbyDf/eqjy9wPI0vxTYFBGR0nvSaLV5wHzggYnqlPRJYCGwLCJeHtuApN9K94GQdB7lPu/J0mMzM6sp2wCBiBiRdDmwEWgD1kbEDklXAn0R0QusAW5NAwCepRw8SPnuoDyYYAS4LCJGAWrVmTZ5I/BT4F9SbLkrjTxbCnxa0ggwDPSkgGZmZlNEPu4erFQqRV9fX7ObYWY2rUjaEhGlWuv8IE6zJvN7jOxo4GBjdfGBsbH8HiM7WrTi0GfLZOzAOLh3mODXB8YNW6sHGVpRh/KEcLPpyMHGCvOBsfH8HiM7WjjYWGE+MDae32NkRwsHGyvMB8bG83uM7GjhYGOF+cDYeH5CuB0tPBrNChs7AHo0WmP5CeF2NHCwsbr4wGhmh8LBZprx71zMbDpysJlGmvkDQAc5MzscDjZHgKIH8ol+51Kdv5HBYbr+yt0B0uzI4WDTZPUcyIv+zqXe4DDZQbmeIFe0zkPNW1SuAJmjX7mCYq7PdboE8Gb3v9n7/0jjYNNk9RzIZ3e0M1gj4FT/zqXeM6DJDsr1/pizngN9rqCQ4ywwR78a/cXgUNtapM4/37CN2+5/grHnxDeyrc38stGK+7/efk1FsPPvbJqsngN50d+51FNnkUfQ1Ptjznoea5PrETj1ngUWed5bjn7VU2eOthatc8PWwQMCTaPamut5e43ufz111pM31/5v9udfi4NNk9VzIC/6A8B66ixyUK73x5z1BLtcj8Ap+hnU8589R78a/cWg3nrrOSiO9+arw2lrs79stOr+b/bnX4uDTQNt2DrI267exLxV3+BtV28q9O2g3gP5kgVdfH/VRey6+n18f9VFNU9366mzyEG53l+51xPscj0CJ8dZYI5+NfqLQb31Hu5Bcbxt5TjY1qPR/a+nznry5tr/zf78a3GwaZBDPR3N8biSeuoselAuEuTqrbPevPXIcRZYq60zjxEvvDRy0BeMov1q9BeDsS88g3uHUVW+WvUe7kFRqQ+H0tZ68tWr6Od6uPv/cP+uG73/6807lc879GuhaziU10KP/Qev1tXRzvdXXVSojmbd0Gv2TcdD7c945erdduUN2mrHv3om73vzKdz9w6fZO7x/0jYJ+Mj5p/GXS84+qB3vemMn9z06dFC7/nzDNm7f/CSjFf8X2yRGI175t6N9Ji+NjPLC/pcP2F77zLZXgmj1Dfzx+nPFvz0LKF9CqfU3W9mHMX++YRv/6/4nDsr7B1X5oPyZfq53x0GfV2VbK/OuvPOH7B89sNXHCF4O6Gifya9e3M9Yt48RXHD6Cex46pev1P/qmccwa2Ybe1/Yf8DnPBZwx2oe25eV++Bdb+zka1sGa+7/ro52RkZH+fkvX3ol7eTfPJYXR+KAbQMH7Jdan3FlO2r1s7qdleWf2jvMcQX3/9jfkYBjjhGjL/96qzOPEa951Qyee2H/uO2B2vu/qIleC5012EhaBPwN0Ab8fURcXbV+FvAV4K3AHuDDEfF4WrcaWAGMAv8xIjZOVKekecA64ERgC/DRiHhpom2M51CCzbxV35jwP7mZ2XTz+NXvqyv/RMEm22U0SW3A9cAlQDewTFJ3VbYVwHMRcQZwHXBNKtsN9ABnAYuAGyS1TVLnNcB1qa7nUt3jbqPRHGjMrNXMXfWNhtWV857NecBAROyMiJcon3UsrsqzGLglzd8JXCxJKX1dRLwYEbuAgVRfzTpTmYtSHaQ6l0yyDTMzmyI5g00X8GTF8u6UVjNPRIwA+yhfBhuv7HjpJwJ7Ux3V2xpvGweQdKmkPkl9Q0NDdXXUzMwm5tFoSUTcFBGliCh1dnY2uzlmZi0lZ7AZBE6tWJ6T0mrmkTQDOI7yTfzxyo6XvgfoSHVUb2u8bZiZ2RTJGWweBOZLmifpWMo3/Hur8vQCy9P8UmBTlIfH9QI9kmalUWbzgQfGqzOVuS/VQarz65Nso6HqHbVhZnaka+RxLduDOCNiRNLlwEbKw5TXRsQOSVcCfRHRC6wBbpU0ADxLOXiQ8t0BPAKMAJdFxChArTrTJv8MWCfpL4GtqW7G20YODjhmZrX5R501HMrvbMzMjnZN+Z2NmZnZGAcbMzPLzsHGzMyyc7AxM7PsPECgBklDwE8Po4qTgF80qDnTwdHWX3Cfjxbuc31eFxE1fxXvYJOBpL7xRmS0oqOtv+A+Hy3c58bxZTQzM8vOwcbMzLJzsMnjpmY3YIodbf0F9/lo4T43iO/ZmJlZdj6zMTOz7BxszMwsOwebBpK0SFK/pAFJq5rdnsMh6VRJ90l6RNIOSf8ppZ8g6VuSfpL+PT6lS9IXUt8flnRuRV3LU/6fSFo+3jaPBJLaJG2VdHdanidpc+rX+vRqC9LrL9an9M2S5lbUsTql90ta2KSuFCKpQ9Kdkh6V9CNJFxwF+/hP0t/0dkm3S3pVq+1nSWslPSNpe0Vaw/arpLdK2pbKfEGSJm1URHhqwET5lQePAacDxwI/BLqb3a7D6M8pwLlp/jeBHwPdwOeBVSl9FXBNmn8v8E1AwPnA5pR+ArAz/Xt8mj++2f2boN+fAb4K3J2W7wB60vyNwKfT/B8BN6b5HmB9mu9O+34WMC/9TbQ1u18T9PcW4JNp/ligo5X3MeXXxO8C2iv278dbbT8D7wTOBbZXpDVsv1J+v9j5qcw3gUsmbVOzP5RWmYALgI0Vy6uB1c1uVwP793Xgd4F+4JSUdgrQn+a/DCyryN+f1i8DvlyRfkC+I2mi/IbXe4GLgLvTf6RfADOq9zHldypdkOZnpHyq3u+V+Y60ifJba3eRBgpV77sW3cddwJPpADoj7eeFrbifgblVwaYh+zWte7Qi/YB8402+jNY4Y3/EY3antGkvXTpYAGwGTo6Ip9OqnwEnp/nx+j+dPpf/Cfwp8HJaPhHYGxEjabmy7a/0K63fl/JPp/7OA4aAf0iXDv9e0m/Qwvs4IgaBvwKeAJ6mvN+20Nr7eUyj9mtXmq9On5CDjU1I0muArwF/HBHPV66L8tealhg7L+n9wDMRsaXZbZlCMyhfavlSRCwAfkX58sorWmkfA6T7FIspB9rZwG8Ai5raqCZoxn51sGmcQeDUiuU5KW3akjSTcqC5LSLuSsk/l3RKWn8K8ExKH6//0+VzeRvwAUmPA+soX0r7G6BD0tjr0yvb/kq/0vrjgD1Mn/5C+Rvp7ojYnJbvpBx8WnUfA7wb2BURQxGxH7iL8r5v5f08plH7dTDNV6dPyMGmcR4E5qdRLcdSvpnY2+Q2HbI0umQN8KOI+OuKVb3A2KiU5ZTv5YylfyyNbDkf2JdO2TcC75F0fPpW+Z6UdkSJiNURMSci5lLed5si4iPAfcDSlK26v2Ofw9KUP1J6TxrFNA+YT/lm6hEnIn4GPCnpzJR0MfAILbqPkyeA8yW9Ov2Nj/W5ZfdzhYbs17TueUnnp8/wYxV1ja/ZN7FaaaI8quPHlEemfLbZ7TnMvryd8mn2w8BDaXov5evV9wI/Ab4NnJDyC7g+9X0bUKqo6w+BgTR9otl9K9D3C/n1aLTTKR9EBoB/BGal9Fel5YG0/vSK8p9Nn0M/BUbpNLmv5wB9aT9voDzqqKX3MfBfgUeB7cCtlEeUtdR+Bm6nfE9qP+Uz2BWN3K9AKX1+jwFfpGqQSa3Jj6sxM7PsfBnNzMyyc7AxM7PsHGzMzCw7BxszM8vOwcbMzLJzsDEzs+wcbMzMLLv/D7PK+kYaskVWAAAAAElFTkSuQmCC\n"
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "listaTeste = Lista()\n",
    "\n",
    "# Cria uma função a partir de outra função e\n",
    "# parte dos seus parâmetros.\n",
    "# Para executá-la, basta chamar func(),\n",
    "# assim como feito pelo benchmark\n",
    "func = partial(marcaTempo(listaTeste.insereValor), posicao=0)\n",
    "benchmark(func)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Muito rápido, exceto por alguns outliers.\n",
    "\n",
    "Agora tentemos colocar sempre no final da lista.\n",
    "\n",
    "Como a lista vai crescendo, temos que buscar a última posição cada vez mais distante do início ($O(n)$)."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Benchmark levou 5.12E+00s no total, e 5.12E-04±6.20E-04s por iteração\n"
     ]
    },
    {
     "data": {
      "text/plain": "<Figure size 432x288 with 1 Axes>",
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAD4CAYAAAD2FnFTAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8qNh9FAAAACXBIWXMAAAsTAAALEwEAmpwYAAAWVklEQVR4nO3df5RndX3f8efLXX6sWllYpx5YwF1kQ86atqITxGo8NUTBmLjmhNTF5kgsLSexNDU0tMuxtUr+iEiOJFYSpYGWcKKA1NJVsXsS4fSkaUqYdUFYdHX4oeygdQUWK6ywu7z7x/fO+mW4M/tddu5858fzcc73zL2fz+f7nfedOzOv7/31vakqJEma6kXDLkCSND8ZEJKkVgaEJKmVASFJamVASJJaLR92AbPl5S9/ea1Zs2bYZUjSgrJ169YfVNVIW9+iCYg1a9YwNjY27DIkaUFJ8u3p+tzFJElqZUBIkloZEJKkVgaEJKmVASFJarVozmKSpK7dsm2CK7bs4JHdezhh5QouOfs03nX66mGX1RkDQpIGcMu2CS79/D3s2bsfgInde7j08/cALNqQcBeTJA3gii07DoTDpD1793PFlh1Dqqh7BoQkDeCR3XsOqX0xMCAkaQAnrFxxSO2LgQEhSQO45OzTWHHEsue0rThiGZecfdqQKuqeB6klaQCTB6I9i0mS9DzvOn31og6EqdzFJElqZUBIkloZEJKkVgaEJKmVASFJamVASJJaGRCSpFYGhCSplQEhSWplQEiSWhkQkqRWnQZEknOS7EgynmRTS/9RSW5s+u9IsqZpX5NkT5K7msenuqxTkvR8nX1YX5JlwFXAW4GdwJ1JNlfVfX3DLgAer6pTk2wELgfe3fTdX1Wv6ao+SdLMutyCOAMYr6oHquoZ4AZgw5QxG4DrmumbgbOSpMOaJEkD6jIgVgMP983vbNpax1TVPuAJYFXTtzbJtiT/M8nPtX2DJBcmGUsytmvXrtmtXpKWuPl6kPq7wMlVdTpwMfCZJC+bOqiqrq6q0aoaHRkZmfMiJWkx6zIgJoCT+uZPbNpaxyRZDhwDPFpVT1fVowBVtRW4H/ipDmuVJE3RZUDcCaxLsjbJkcBGYPOUMZuB85vpc4HbqqqSjDQHuUlyCrAOeKDDWiVJU3R2FlNV7UtyEbAFWAZcW1Xbk1wGjFXVZuAa4Pok48Bj9EIE4M3AZUn2As8Cv1lVj3VVqyTp+VJVw65hVoyOjtbY2Niwy5CkBSXJ1qoabeubrwepJUlDZkBIkloZEJKkVgaEJKmVASFJamVASJJaGRCSpFYGhCSplQEhSWplQEiSWhkQkqRWBoQkqZUBIUlqZUBIkloZEJKkVgaEJKmVASFJamVASJJaGRCSpFYGhCSplQEhSWplQEiSWhkQkqRWBoQkqZUBIUlqZUBIkloZEJKkVp0GRJJzkuxIMp5kU0v/UUlubPrvSLJmSv/JSX6U5He7rFOS9HydBUSSZcBVwNuB9cB5SdZPGXYB8HhVnQpcCVw+pf/jwJe7qlGSNL0utyDOAMar6oGqega4AdgwZcwG4Lpm+mbgrCQBSPIu4EFge4c1SpKm0WVArAYe7pvf2bS1jqmqfcATwKokLwX+LfCRmb5BkguTjCUZ27Vr16wVLkmavwepPwxcWVU/mmlQVV1dVaNVNToyMjI3lUnSErG8w9eeAE7qmz+xaWsbszPJcuAY4FHg9cC5ST4GrASeTfLjqvpkh/VKkvp0GRB3AuuSrKUXBBuB90wZsxk4H/gb4Fzgtqoq4OcmByT5MPAjw0GS5lZnAVFV+5JcBGwBlgHXVtX2JJcBY1W1GbgGuD7JOPAYvRCRJM0D6b1hX/hGR0drbGxs2GVI0oKSZGtVjbb1zdeD1JKkITMgJEmtDAhJUisDQpLUyoCQJLUyICRJrQwISVIrA0KS1MqAkCS1MiAkSa0MCElSKwNCktTKgJAktTIgJEmtDAhJUisDQpLU6qB3lEsySu8WoCcAe4B7gb+oqsc7rk2SNETTbkEkeV+SrwKXAiuAHcD3gTcBf5nkuiQnz02ZkqS5NtMWxIuBN1bVnrbOJK8B1gHf6aAuSdKQTRsQVXXVTE+sqrtmvRpJ0rxx0IPUST6W5GVJjkjylSS7kvz6XBQnSRqeQc5ieltV/RD4JeAh4FTgki6LkiQN3yABMbkb6h3A56rqiQ7rkSTNEwc9zRX4YpJv0DvF9beSjAA/7rYsSdKwHXQLoqo2Af8QGK2qvcBTwIauC5MkDddM10G8aXK6qh6rqv3N9JNV9b3mwPXPzEWRkqS5N9Mupl9N8jHgfwBbgV3A0fQOUr8FeCXwrzuvUJI0FNNuQVTV79A7c+m7wK8BvwdcTO/iuE9X1Zur6s6ZXjzJOUl2JBlPsqml/6gkNzb9dyRZ07SfkeSu5nF3kl954YsoSXohZjxIXVWPAf+peRySJMuAq4C3AjuBO5Nsrqr7+oZdADxeVacm2QhcDryb3uc9jVbVviTHA3cn+UJV7TvUOiRJL0yXn+Z6BjBeVQ9U1TPADTz/4PYG4Lpm+mbgrCSpqqf6wuBooDqsU5LUosuAWA083De/s2lrHdMEwhPAKoAkr0+yHbgH+M22rYckFyYZSzK2a9euDhZBkpaueXs/iKq6o6peDfwscGmSo1vGXF1Vo1U1OjIyMvdFStIiNshnMR2R5LeT3Nw8/mWSIwZ47QngpL75E5u21jFJlgPHAI/2D6iqrwM/AjylVpLm0CBbEH8CvA744+bx2qbtYO4E1iVZm+RIYCOwecqYzcD5zfS5wG1VVc1zlgMkeSXw0/Q+B0qSNEcG+aiNn62qf9A3f1uSuw/2pOYMpIuALcAy4Nqq2p7kMmCsqjYD1wDXJxkHHqMXItC7KdGmJHuBZ4H3V9UPBl8sSdLhGiQg9id5VVXdD5DkFGD/IC9eVbcCt05p+1Df9I/pXWMx9XnXA9cP8j0kSd0YJCAuAW5P8gAQeldQv6/TqiRJQ3fQgKiqryRZB5zWNO2oqqe7LUuSNGwHDYjm9NL30zsuUMBfJflUs3tIkrRIDbKL6c+A/wf8x2b+PfSODzzv2IEkafEYJCB+pqrW983fnuS+aUdLkhaFQa6D+GqSMydnkrweGOuuJEnSfDDIFsTrgP+d5DvN/MnAjiT3AFVVf7+z6iRJQzNIQJzTeRWSpHlnkNNcv53kWHqfmbS8r/2rXRYmSRquQU5z/T3gN4D7+cl9GQr4+e7KkiQN2yC7mP4x8Krmpj+SpCVikLOY7gVWdlyHJGmeGWQL4veBbUnuBQ58xEZVvbOzqiRJQzdIQFwHXE7v1p/PdluOJGm+GCQgnqqqT3ReiSRpXhkkIP4qye/Tu/tb/y4mT3OVpEVskIA4vfl6Zl+bp7lK0iI3yIVyb5mLQiRJ88tBT3NN8ook1yT5cjO/PskF3ZcmSRqmQa6D+C/AFuCEZv6bwAc6qkeSNE9MGxBJJnc/vbyqbqI5xbWq9gH756A2SdIQzbQF8bfN1yeTrKL5HKbm3hBPdF2YJGm4ZjpInebrxfROcX1Vkr8GRoBzuy5MkjRcMwXESJKLm+n/BtxKLzSeBn4B+FrHtUmShmimgFgGvJSfbElMenF35UiS5ouZAuK7VXXZnFUiSZpXZjpIPXXL4ZAlOSfJjiTjSTa19B+V5Mam/44ka5r2tybZmuSe5qtXbUvSHJspIM46nBdOsgy4Cng7sB44L8n6KcMuAB6vqlOBK+l9aizAD4Bfrqq/B5wPXH84tUiSDt20AVFVjx3ma58BjFfVA83d6G4ANkwZs4Hex4kD3AyclSRVta2qHmnatwMrkhx1mPVIkg7BIFdSv1CrgYf75nc2ba1jmgvwngBWTRnzq8BXq+ppJElzZpBPcx2aJK+mt9vpbdP0XwhcCHDyySfPYWWStPh1uQUxAZzUN39i09Y6pvloj2OAR5v5E+ldf/Heqrq/7RtU1dVVNVpVoyMjI7NcviQtbV0GxJ3AuiRrkxwJbKR3RXa/zfQOQkPv6uzbqqqSrAS+BGyqqr/usEZJ0jQ6C4jmmMJF9D4J9uvATVW1PcllSd7ZDLsGWJVknN5HekyeCnsRcCrwoSR3NY+/21WtkqTnS1UNu4ZZMTo6WmNjY8MuQ5IWlCRbq2q0ra/LXUySpAXMgJAktTIgJEmtDAhJUisDQpLUyoCQJLUyICRJrQwISVIrA0KS1MqAkCS1MiAkSa0MCElSKwNCktTKgJAktTIgJEmtDAhJUisDQpLUyoCQJLUyICRJrQwISVIrA0KS1MqAkCS1MiAkSa0MCElSKwNCktTKgJAktTIgJEmtOg2IJOck2ZFkPMmmlv6jktzY9N+RZE3TvirJ7Ul+lOSTXdYoSWrXWUAkWQZcBbwdWA+cl2T9lGEXAI9X1anAlcDlTfuPgX8P/G5X9UmSZtblFsQZwHhVPVBVzwA3ABumjNkAXNdM3wyclSRV9WRV/S96QSFJGoIuA2I18HDf/M6mrXVMVe0DngBWDfoNklyYZCzJ2K5duw6zXElSvwV9kLqqrq6q0aoaHRkZGXY5krSodBkQE8BJffMnNm2tY5IsB44BHu2wJknSgLoMiDuBdUnWJjkS2AhsnjJmM3B+M30ucFtVVYc1SZIGtLyrF66qfUkuArYAy4Brq2p7ksuAsaraDFwDXJ9kHHiMXogAkOQh4GXAkUneBbytqu7rql5J0nN1FhAAVXUrcOuUtg/1Tf8Y+LVpnrumy9okSTNb0AepJUndMSAkSa0MCElSKwNCktTKgJAktTIgJEmtDAhJUisDQpLUyoCQJLUyICRJrQwISVIrA0KS1MqAkCS1MiAkSa0MCElSKwNCktSq0xsGSQvFLdsm+PDm7ezesxeAY198BP/hl1/Nu05fPeTKpOExILTk3bJtgks+dzd7n/3J7dAff2ovl9x8N4AhoSXLXUxa8q7YsuM54TBp7/7iii07hlCRND+4BaElb2L3nmn7HpmhT4fnlm0TXLFlB4/s3sMJK1dwydmnubU2zxgQWvKWJeyv529BAByz4og5rmZpuGXbBJfcfDd79/d+7hO797hLbx4yIDRU8+Fd5HThAPDk03vnsJKl4yNf2H4gHCbt3V985AvbDYh5xIDQ0NyybYIP3HjXgfmJ3XsOzM/lP4nVK1dMu5tp77ODv858CLuF4vGn2oN3unYNhwGhoekPh7b2ufrnumbV9AExqFu2TXDxTXcxeax7YvceLr7pLsBdJodq7aYvHQhY6J1EMLF7z4FdgVO/rlxxBAnsfmovxzTTjz+190B/gMltlRcFni1a+6aaOrZtV+QbX3Ucf/7P3/CClvPf3XIPn73j4QOvfcrIi3lg11MH5kOxb/qN22k99NF3vKB62qRm2LxeSEZHR2tsbGzYZWgAk++0D/ZP+XD++Ab5/o/s3sMxK444cO3DdP7w3a856DUSP/XBW3lmf/vf0q+feTKjrzzuoFsXbVsgMP0/yNUrV/CWnx7h9m/sOrAsTz6998BWz4sCbzjlOL76nd3s6dsUesmRy/iV164+8Lyjj3jRc/qXpfdPs+XELi0QhxISSbZW1WhrnwGhLkzdfSRp7sxWQLiLaRozvZubfLc2uVl7sP6p79COXJZp321OmunMGkmaC51uQSQ5B/gjYBnwp1X10Sn9RwF/BrwOeBR4d1U91PRdClwA7Ad+u6q2zPS9XugWxJpNXzrk50jSfDZbWxCdXUmdZBlwFfB2YD1wXpL1U4ZdADxeVacCVwKXN89dD2wEXg2cA/xx83qzynCQpOl1+VEbZwDjVfVAVT0D3ABsmDJmA3BdM30zcFaSNO03VNXTVfUgMN68niRpBrN5FlOXxyBWAw/3ze8EXj/dmKral+QJYFXT/n+mPPd55womuRC4EODkk0+etcIlaSEI8OAsBsJUC/ogdVVdDVwNvWMQQy5HUp/ZfCer4egyICaAk/rmT2za2sbsTLIcOIbewepBnivNiq7fhUkLVZcBcSewLslaev/cNwLvmTJmM3A+8DfAucBtVVVJNgOfSfJx4ARgHfC3s13gQx99x4I7UO27MklzpbOAaI4pXARsoXea67VVtT3JZcBYVW0GrgGuTzIOPEYvRGjG3QTcB+wD/kVV7e+iTv/hSlI7r6SWpCVsKNdBSJIWNgNCktTKgJAktTIgJEmtFs1B6iS7gG8fxku8HPjBLJWzECy15QWXealwmQ/NK6tqpK1j0QTE4UoyNt2R/MVoqS0vuMxLhcs8e9zFJElqZUBIkloZED9x9bALmGNLbXnBZV4qXOZZ4jEISVIrtyAkSa0MCElSqyUfEEnOSbIjyXiSTcOu53AkOSnJ7UnuS7I9yb9q2o9L8hdJvtV8PbZpT5JPNMv+tSSv7Xut85vx30py/rCWaRBJliXZluSLzfzaJHc0y3VjkiOb9qOa+fGmf03fa1zatO9IcvaQFmUgSVYmuTnJN5J8PckblsA6/p3md/reJJ9NcvRiW89Jrk3y/ST39rXN2npN8rok9zTP+USSHLSoqlqyD3ofQ34/cApwJHA3sH7YdR3G8hwPvLaZ/jvAN4H1wMeATU37JuDyZvoXgS/Tu2fOmcAdTftxwAPN12Ob6WOHvXwzLPfFwGeALzbzNwEbm+lPAb/VTL8f+FQzvRG4sZle36z7o4C1ze/EsmEv1wzLex3wz5rpI4GVi3kd07vd8IPAir71+xuLbT0DbwZeC9zb1zZr65XePXXObJ7zZeDtB61p2D+UIa+QNwBb+uYvBS4ddl2zuHz/HXgrsAM4vmk7HtjRTH8aOK9v/I6m/zzg033tzxk3nx707jb4FeDngS82v/w/AJZPXcf07k3yhmZ6eTMuU9d7/7j59qB318UHaU4wmbruFuk6nrx3/XHNevsicPZiXM/AmikBMSvrten7Rl/7c8ZN91jqu5gmf/Em7WzaFrxms/p04A7gFVX13abre8Armunpln8h/Vz+EPg3wLPN/Cpgd1Xta+b7az+wXE3/E834hbS8a4FdwH9udqv9aZKXsIjXcVVNAH8AfAf4Lr31tpXFvZ4nzdZ6Xd1MT22f0VIPiEUpyUuB/wp8oKp+2N9XvbcPi+Lc5iS/BHy/qrYOu5Y5tJzebog/qarTgSfp7Xo4YDGtY4Bmv/sGeuF4AvAS4JyhFjUEw1ivSz0gJoCT+uZPbNoWrCRH0AuHP6+qzzfN/zfJ8U3/8cD3m/bpln+h/FzeCLwzyUPADfR2M/0RsDLJ5O10+2s/sFxN/zHAoyyc5YXeO7+dVXVHM38zvcBYrOsY4BeAB6tqV1XtBT5Pb90v5vU8abbW60QzPbV9Rks9IO4E1jVnQxxJ74DW5iHX9II1ZyVcA3y9qj7e17UZmDyb4Xx6xyYm29/bnBFxJvBEszm7BXhbkmObd29va9rmlaq6tKpOrKo19NbdbVX1T4DbgXObYVOXd/LncG4zvpr2jc3ZL2uBdfQO6M07VfU94OEkpzVNZ9G7d/uiXMeN7wBnJnlx8zs+ucyLdj33mZX12vT9MMmZzc/wvX2vNb1hH5QZ9oPe2QDfpHdGwweHXc9hLsub6G2Cfg24q3n8Ir39r18BvgX8JXBcMz7AVc2y3wOM9r3WPwXGm8f7hr1sAyz7P+InZzGdQu8Pfxz4HHBU0350Mz/e9J/S9/wPNj+HHQxwdseQl/U1wFiznm+hd7bKol7HwEeAbwD3AtfTOxNpUa1n4LP0jrHspbeleMFsrldgtPn53Q98kiknOrQ9/KgNSVKrpb6LSZI0DQNCktTKgJAktTIgJEmtDAhJUisDQpLUyoCQJLX6/21Us7+jS2yOAAAAAElFTkSuQmCC\n"
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "listaTeste = Lista()\n",
    "\n",
    "# Cria uma função a partir de outra função e\n",
    "# parte dos seus parâmetros.\n",
    "# Para executá-la, basta chamar func(),\n",
    "# assim como feito pelo benchmark\n",
    "func = partial(marcaTempo(listaTeste.insereValor), posicao=-1)\n",
    "benchmark(func)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Pelos resultados (olhe as diferentes escalas e ignore os outliers), adicionar sempre no final da lista foi bem mais lento.\n",
    "\n",
    "Graficamente, também vemos que o tempo levado por iteração é menos regular.\n",
    "\n",
    "Uma das possíveis melhorias para permitir inserção mais rápida também na última posição, é modificando a implementação da nossa lista."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "outputs": [],
   "source": [
    "class ListaComElementoFinal():\n",
    "    def __init__(self):\n",
    "        # Cria uma lista vazia\n",
    "        self.primeiroElementoLista = None\n",
    "        self.ultimoElementoLista = None\n",
    "\n",
    "    def buscaElementoPosicao(self, posicao):\n",
    "        # Procure o elemento atualmente na posição\n",
    "        elementoPosicao = self.primeiroElementoLista\n",
    "        posicaoBuscada = 0\n",
    "        while posicaoBuscada != posicao:\n",
    "            if elementoPosicao is None:\n",
    "                raise Exception(f\"Posição não existente na lista: {posicao}\")\n",
    "            if elementoPosicao.proximo is None and posicao == -1:\n",
    "                return elementoPosicao\n",
    "            if elementoPosicao.proximo.proximo is None and posicao == -2:\n",
    "                return elementoPosicao\n",
    "            elementoPosicao = elementoPosicao.proximo\n",
    "            posicaoBuscada += 1\n",
    "        return elementoPosicao\n",
    "\n",
    "    def insereValor(self, valor, posicao=0):\n",
    "        # Cria um elemento para a lista\n",
    "        novoElementoLista = ElementoLista(valorInicial=valor)\n",
    "\n",
    "        if posicao == -1 and self.primeiroElementoLista is None:\n",
    "                self.primeiroElementoLista = novoElementoLista\n",
    "                self.ultimoElementoLista = novoElementoLista\n",
    "                return None\n",
    "\n",
    "        # E a posição de inserção seja a primeira posição\n",
    "        if posicao == 0:\n",
    "            if self.primeiroElementoLista is not None:\n",
    "                novoElementoLista.proximo = self.primeiroElementoLista\n",
    "            else:\n",
    "                self.ultimoElementoLista = novoElementoLista\n",
    "            self.primeiroElementoLista = novoElementoLista\n",
    "        elif posicao == -1:\n",
    "            # Muda referência para próximo elemento colocado ao final da lista\n",
    "            self.ultimoElementoLista.proximo = novoElementoLista\n",
    "            # Atualiza novo ultimo elemento\n",
    "            self.ultimoElementoLista = novoElementoLista\n",
    "        # Se a lista não estiver vazia\n",
    "        else:\n",
    "            # Busca elemento anterior a posição\n",
    "            elementoPosicao = self.buscaElementoPosicao(posicao-1)\n",
    "            # Salva a referência para o elemento na\n",
    "            # posição como próximo do novo elemento\n",
    "            novoElementoLista.proximo = elementoPosicao.proximo\n",
    "            # Substitui elemento na posição pelo novo elemento\n",
    "            elementoPosicao.proximo = novoElementoLista\n",
    "        return None\n",
    "\n",
    "    def removerValor(self, posicao=0):\n",
    "        if posicao == 0:\n",
    "            if self.primeiroElementoLista is None:\n",
    "                return None\n",
    "            else:\n",
    "                elementoRemovido = self.primeiroElementoLista\n",
    "                self.primeiroElementoLista = self.primeiroElementoLista.proximo\n",
    "                if self.primeiroElementoLista is None:\n",
    "                    self.ultimoElementoLista = None\n",
    "                return elementoRemovido.valor\n",
    "        else:\n",
    "            if posicao == -1 and self.primeiroElementoLista == self.ultimoElementoLista:\n",
    "                elementoRemovido = self.primeiroElementoLista\n",
    "                self.primeiroElementoLista = None\n",
    "                self.ultimoElementoLista = None\n",
    "                return elementoRemovido\n",
    "            elementoPosicao = self.buscaElementoPosicao(posicao-1)\n",
    "            if elementoPosicao.proximo is not None:\n",
    "                elementoRemovido = elementoPosicao.proximo\n",
    "                elementoPosicao.proximo = elementoRemovido.proximo\n",
    "                if self.ultimoElementoLista == elementoRemovido:\n",
    "                    self.ultimoElementoLista = elementoPosicao\n",
    "                return elementoRemovido.valor\n",
    "            return None"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Agora o desempenho deve ser similar inserindo elementos em ambos os lados"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Benchmark levou 1.08E-02s no total, e 1.08E-06±7.79E-06s por iteração\n"
     ]
    },
    {
     "data": {
      "text/plain": "<Figure size 432x288 with 1 Axes>",
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZUAAAD6CAYAAABpjtoAAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8qNh9FAAAACXBIWXMAAAsTAAALEwEAmpwYAAAb8UlEQVR4nO3dcZRc5Xnf8e/PKyEvccOC2LpowZEwsnxEiC08Ibh22xiMV9ippUPkItwmsisfTh1U16ZHjvbkj6S0OYDVYxrXEJtYOJTiSLKiKHtM7D2xRU9d1xUaWYBAsHiNwGjBZQ1IbuyNkJanf9x3YVjNzM5I9+7szP4+5+zRve9977vPO3c1z9z7vnOvIgIzM7M8vKHVAZiZWedwUjEzs9w4qZiZWW6cVMzMLDdOKmZmlhsnFTMzy02hSUXSSknDkkYkbaqyfYGkbWn7HkmLK7YNpPJhSf3TtanMH0t6QtJjkj5VZN/MzOxk84pqWFIXcDtwFXAY2CtpMCIOVlRbD7wUERdJWgvcClwraTmwFrgYWAR8W9Lb0j612vwYcAHw9oh4RdI/nC7Gc889NxYvXpxDb83M5o59+/b9NCJ6q20rLKkAlwEjEfEkgKStwCqgMqmsAv4oLe8AvihJqXxrRBwDDkkaSe1Rp81PAh+NiFcAIuL56QJcvHgx5XL5tDppZjbXSHq61rYiL3/1Ac9UrB9OZVXrRMQJ4CiwsM6+9dp8K9lZTlnSNyUtrRaUpOtTnfLY2NgpdczMzKrrpIH6BcDfR0QJ+DPgrmqVIuLOiChFRKm3t+rZm5mZnaIik8oo2RjHpPNTWdU6kuYBZwEv1Nm3XpuHgZ1p+a+AXzvtHpiZWVOKTCp7gaWSlkg6g2zgfXBKnUFgXVpeA+yO7A6Xg8DaNDtsCbAUeGCaNncB70vL/wx4ophumZlZLYUN1EfECUkbgCGgC7grIh6VdBNQjohBYAtwTxqIf5EsSZDqbScbgD8B3BAREwDV2ky/8hbgXkmfAf4O+ERRfTMzs+o0l299XyqVwrO/zDrXrv2jbB4a5tkj4yzq6WZj/zJWr5g6X8iaJWlfGr8+SZFTis3MWmbX/lEGdh5g/PgEAKNHxhnYeQDAiaVAnTT7y8zsVZuHhl9NKJPGj0+weWi4RRHNDU4qZtaRnj0y3lS55cNJxcw60qKe7qbKLR9OKmbWkTb2L6N7ftfryrrnd7Gxf1mLIpobPFBvZh1pcjDes79mlpOKmXWs1Sv6nERmmC9/mZlZbpxUzMwsN04qZmaWGycVMzPLjZOKmZnlxknFzMxy46RiZma5cVIxM7PcOKmYmVlunFTMzCw3TipmZpYbJxUzM8uNk4qZmeXGScXMzHLjpGJmZrlxUjEzs9w4qZiZWW6cVMzMLDeFJhVJKyUNSxqRtKnK9gWStqXteyQtrtg2kMqHJfVP16akP5d0SNKD6eedRfbNzMxOVtgz6iV1AbcDVwGHgb2SBiPiYEW19cBLEXGRpLXArcC1kpYDa4GLgUXAtyW9Le1Tr82NEbGjqD6ZmVl9RZ6pXAaMRMSTEfEysBVYNaXOKuDutLwDuFKSUvnWiDgWEYeAkdReI22amVmLFJlU+oBnKtYPp7KqdSLiBHAUWFhn3+na/GNJD0u6TdKCPDphZmaN66SB+gHg7cCvA+cAv1+tkqTrJZUllcfGxmYyPjOzjldkUhkFLqhYPz+VVa0jaR5wFvBCnX1rthkRz0XmGPBVsktlJ4mIOyOiFBGl3t7eU+yamZlVU2RS2QsslbRE0hlkA++DU+oMAuvS8hpgd0REKl+bZoctAZYCD9RrU9J56V8Bq4FHCuybmZlVUdjsr4g4IWkDMAR0AXdFxKOSbgLKETEIbAHukTQCvEiWJEj1tgMHgRPADRExAVCtzfQr75XUCwh4EPg3RfXNzMyqU3ZiMDeVSqUol8utDsPMrK1I2hcRpWrbOmmg3szMWsxJxczMcuOkYmZmuXFSMTOz3DipmJlZbpxUzMwsN04qZmaWGycVMzPLjZOKmZnlxknFzMxy46RiZma5cVIxM7PcOKmYmVlunFTMzCw3TipmZpYbJxUzM8uNk4qZmeXGScXMzHLjpGJmZrlxUjEzs9zMa3UAZkXatX+UzUPDPHtknEU93WzsX8bqFX2tDsusYzmpWMfatX+UgZ0HGD8+AcDokXEGdh4AcGIxK4gvf1nH2jw0/GpCmTR+fILNQ8Mtisis8zmpWMd69sh4U+VmdvqcVKxjLerpbqrczE6fk4p1rI39y+ie3/W6su75XWzsX9aiiMw6X6FJRdJKScOSRiRtqrJ9gaRtafseSYsrtg2k8mFJ/U20+QVJf1dYp6xtrF7Rx83XXEJfTzcC+nq6ufmaSzxIb1agwmZ/SeoCbgeuAg4DeyUNRsTBimrrgZci4iJJa4FbgWslLQfWAhcDi4BvS3pb2qdmm5JKwNlF9cnaz+oVfU4iZjOoyDOVy4CRiHgyIl4GtgKrptRZBdydlncAV0pSKt8aEcci4hAwktqr2WZKYpuBzxbYJzMzq6PIpNIHPFOxfjiVVa0TESeAo8DCOvvWa3MDMBgRz9ULStL1ksqSymNjY011yMzM6uuIgXpJi4CPAP91uroRcWdElCKi1NvbW3xwZmZzSJFJZRS4oGL9/FRWtY6kecBZwAt19q1VvgK4CBiR9BRwpqSRvDpiZmaNKTKp7AWWSloi6QyygffBKXUGgXVpeQ2wOyIila9Ns8OWAEuBB2q1GRH3RcQ/iojFEbEY+EVEXFRg38zMrIrCZn9FxAlJG4AhoAu4KyIelXQTUI6IQWALcE86q3iRLEmQ6m0HDgIngBsiYgKgWptF9cHMzJqj7MRgbiqVSlEul1sdhplZW5G0LyJK1bZ1xEC9mZnNDk4qZmaWGycVMzPLjZOKmZnlxknFzMxy46RiZma5cVIxM7PcOKmYmVlunFTMzCw3TipmZpabae/9lZ6m+E/InsA4DjwC/G1EvFRwbGZm1mZqnqlI+rikHwADQDcwDDwPvJfs8b53S3rLzIRpZmbtoN6ZypnAeyJivNpGSe8kuyX9jwuIy8zM2lDNpBIRt9fbMSIezD0aMzNra9MO1Ev6nKRfljRf0nckjUn6VzMRnJmZtZdGZn99ICJ+BvwW8BTZY3s3FhmUmZm1p0aSyuQlsg8BX4+IowXGY2ZmbayRxwl/Q9LjZNOJPympF/j7YsMyM7N2NO2ZSkRsAv4xUIqI48AvgFVFB2ZmZu2n3vdU3ju5HBEvRsREWv55RPwkDd7/6kwEaWZm7aHe5a/flvQ54FvAPmAMeCPZQP37gF8B/n3hEZqZWduo9z2Vz0g6B/ht4CPAeWTjKo8BX46I/zUzIZqZWbuoO1AfES8Cf5Z+zMzM6vJdis3MLDdOKmZmlptCk4qklZKGJY1I2lRl+wJJ29L2PZIWV2wbSOXDkvqna1PSFkkPSXpY0g5Jbyqyb2ZmdrJG7v01X9Kn0hv1Dkn/VtL8BvbrAm4HrgaWA9dJWj6l2nrgpYi4CLgNuDXtuxxYC1wMrATukNQ1TZufiYh3RMSvkd05ecO0vTczs1w1cqbyp8C7gDvSz6WpbDqXASMR8WREvAxs5eQvTa4C7k7LO4ArJSmVb42IYxFxCBhJ7dVsM92fjLR/NxANxGhmZjlq5DYtvx4R76hY3y3poQb26wOeqVg/DPxGrToRcULSUWBhKv8/U/btS8s125T0VeCDwEFqfIdG0vXA9QBveYufMWZmlqdGzlQmJL11ckXShcBEcSGduoj4ONljjx8Drq1R586IKEVEqbe3d0bjMzPrdI2cqWwE7pf0JCCyb9J/vIH9RoELKtbPT2XV6hyWNA84C3hhmn3rthkRE5K2Ap8FvtpAnGZmlpNpk0pEfEfSUmBZKhqOiGMNtL0XWCppCdkb/1rgo1PqDALrgO8Da4DdERGSBoGvSfo82ZnHUuABsqR2UptpHOWtETGSlj8MPN5AjGZmlqNpk4qkNwK/B7yXbPD7u5K+FBF1b3+fxkg2AENAF3BXRDwq6SagHBGDwBbgHkkjwItkSYJUbzvZ2MgJ4IbJG1rWaPMNwN2Sfpks8TwEfLLZF8PMzE6PIupPkkpv7v8P+O+p6KNAT0R8pODYClcqlaJcLrc6DDOztiJpX0SUqm1rZEzlVyOi8vsl90s6mE9oZmbWSRqZ/fUDSZdPrkj6DcAf783M7CSNnKm8C/jfkn6c1t8CDEs6AET6BruZmVlDSWVl4VGYmVlHaGRK8dOSzib7fsi8ivIfFBmYmZm1n0amFP9H4GPAj3jtfloBXFFcWGZm1o4aufz1L8i+WPhy0cGYmVl7a2T21yNAT8FxmJlZB2jkTOVmYL+kR4BXb88SER8uLCozM2tLjSSVu8kennUAeKXYcKyVdu0fZfPQMM8eGWdRTzcb+5exekXf9DuamSWNJJVfRMQXCo/EWmrX/lEGdh5g/Hj2VIPRI+MM7DwA4MRiZg1rZEzlu5JulvRuSZdO/hQemc2ozUPDryaUSePHJ9g8NNyiiMysHTVyprIi/Xt5RZmnFHeYZ4+MN1VuZlZNI19+fN9MBGKttainm9EqCWRRT3cLojGzdjXt5S9Jb5a0RdI30/pySeuLD81m0sb+ZXTP73pdWff8Ljb2L6uxh5nZyRoZU/lzsodiLUrrTwCfLigea5HVK/q4+ZpL6OvpRkBfTzc3X3OJB+nNrCk1L39JmhcRJ4BzI2K7pAF49YmOE7X2s/a1ekWfk4iZnZZ6ZyoPpH9/Lmkh6b5f6dkqR4sOzMzM2k+9gXqlf28EBoG3Svoe0AusKTowMzNrP/WSSq+kG9PyXwF/Q5ZojgHvBx4uODYzM2sz9ZJKF/AmXjtjmXRmceGYmVk7q5dUnouIm2YsEjMza3v1BuqnnqGYmZnVVS+pXDljUZiZWUeomVQi4sWZDMTMzNpfI9+oP2WSVkoaljQiaVOV7QskbUvb90haXLFtIJUPS+qfrk1J96byRyTdJWl+kX0zM7OTFZZUJHUBtwNXA8uB6yQtn1JtPfBSRFwE3Eb2MDBSvbXAxcBK4A5JXdO0eS/wduASoBv4RFF9MzOz6oo8U7kMGImIJyPiZWArsGpKnVVkT5YE2AFcKUmpfGtEHIuIQ8BIaq9mmxHxN5GQ3Q3g/AL7ZmZmVRSZVPqAZyrWD6eyqnXSfcaOAgvr7Dttm+my1+8A3zrtHpiZWVMKHVNpkTuA/xkR3622UdL1ksqSymNjYzMcmplZZysyqYwCF1Ssn5/KqtaRNA84C3ihzr5125T0h2T3JruRGiLizogoRUSpt7e3yS6ZmVk9RSaVvcBSSUsknUE28D44pc4gsC4trwF2pzGRQWBtmh22BFhKNk5Ss01JnwD6gesi4pUC+2VmZjU08oz6U5Keu7KB7AFfXcBdEfGopJuAckQMAluAeySNAC+SJQlSve3AQeAEcENETABUazP9yi8BTwPfz8b62enbzJiZzSxlJwZzU6lUinK53OowzMzaiqR9EVGqtq0TB+rNzKxFnFTMzCw3TipmZpYbJxUzM8uNk4qZmeXGScXMzHLjpGJmZrlxUjEzs9w4qZiZWW6cVMzMLDdOKmZmlhsnFTMzy42TipmZ5cZJxczMcuOkYmZmuXFSMTOz3DipmJlZbpxUzMwsN04qZmaWGycVMzPLjZOKmZnlxknFzMxy46RiZma5cVIxM7PcOKmYmVlu5rU6ADOb3q79o2weGubZI+Ms6ulmY/8yVq/oa3VYZicp9ExF0kpJw5JGJG2qsn2BpG1p+x5Jiyu2DaTyYUn907UpaUMqC0nnFtkvs5m0a/8oAzsPMHpknABGj4wzsPMAu/aPtjo0s5MUllQkdQG3A1cDy4HrJC2fUm098FJEXATcBtya9l0OrAUuBlYCd0jqmqbN7wHvB54uqk9mrbB5aJjx4xOvKxs/PsHmoeEWRWRWW5GXvy4DRiLiSQBJW4FVwMGKOquAP0rLO4AvSlIq3xoRx4BDkkZSe9RqMyL2p7ICu9Q8X7aw0/XskfGmys1aqcjLX33AMxXrh1NZ1ToRcQI4Ciyss28jbdYl6XpJZUnlsbGxZnZtmi9bWB4W9XQ3VW7WSnNu9ldE3BkRpYgo9fb2Fvq7fNnC8rCxfxnd87teV9Y9v4uN/ctaFJFZbUVe/hoFLqhYPz+VVatzWNI84CzghWn2na7NWcOXLSwPk5dLfRnV2kGRSWUvsFTSErI3/rXAR6fUGQTWAd8H1gC7IyIkDQJfk/R5YBGwFHgAUANtzhqLeroZrZJAfNnCmrV6RZ+TiLWFwi5/pTGSDcAQ8BiwPSIelXSTpA+naluAhWkg/kZgU9r3UWA72aD+t4AbImKiVpsAkj4l6TDZ2cvDkr5SVN8a5csWZjbXKCJaHUPLlEqlKJfLhf4Oz/4ys04jaV9ElKpt8zfqC+bLFmY2l8y52V9mZlYcJxUzM8uNk4qZmeXGScXMzHLjgXozszo8g7M5TipmZjVM3r9v8nZLk/fvA5xYavDlLzOzGnz/vuY5qZiZ1eD79zXPScXMrAY/dqB5TipmZjX4/n3N80C9mVkNfuxA85xUzMzq8P37muOkYk3zvH3rRP67zoeTijXF8/atE/nvOj8eqLemNDtvf9f+Ud5zy26WbLqP99yym137Z+3Tn20O8/dR8uMzlVmimVPvIuo2Wq+ZefvNfvrLO9Zmtcvlj3aJE9on1mb/rtuhT63ipDILNPPmW0TdZtpc1NPNaJX/aNXm7df79DcTsVbuM92bQLOva6s+ABSVqJup20y9dvlQ0ejfdTu9/s3WzYsvf80CzZx6F1G3mTabmbffzKe/ImKF194ERo+ME7z2JjD1Mlyj7TbaXlF1m+l/Eb+/mTaLiLWZ39+MRv+u2+n1L+q1mo6TyizQzJtvEXWbaXP1ij5uvuYS+nq6EdDX083N11xS9dNPM99GLiJWaPxNoNF2W/0BoIhE3UzdZtqcDR8qGtXo33U7vf6tGify5a9ZoJlLSkXUbaZNaHze/sb+Za+7VAC1z2qKirXRN4FG2231B4Bm+t/qDyBFxFrkvbga+btup9e/Vfct85nKLNDMJaUi6hZ1K4pmzmqKirXRs6VG223m7KuIus30v4jf30ybRcTaqntxXfX5/8HiTfdVTSiz9fVv1WvlpDILNPPmW0TdZto8lb59b9MVHLrlQ3xv0xU12ywq1kbf2Bptt9UfAIpI1M3UbbTe5ADx+PEJuiTIKdaZvhfXrv2jXLjpPn74/M+rbp+tr3+zdfOkiCj0F8xmpVIpyuVyq8PoSLNp2mXesbR6+nerY51a731v7+X+x8det/6X+0ZPuuw53QeVPGY/5fkaTp3pVc1Tt3xo2jY6cfaXpH0RUaq6zUmluaTS7EGaTW+u08kr1l37R9n49Yc4/sprf1vz3yA2f+Qds7bvdmoaeeOtNN2b8OlYvOm+puqfOT+7UPOL468AcPaZ8/nDf34xkA1yV7vUNdXp9qed3h8qtSypSFoJ/AnQBXwlIm6Zsn0B8N+AdwEvANdGxFNp2wCwHpgAPhURQ/XalLQE2AosBPYBvxMRL9eLr9mksmv/KJ/e9mDD9c3MZrtTSYz1kkphYyqSuoDbgauB5cB1kpZPqbYeeCkiLgJuA25N+y4H1gIXAyuBOyR1TdPmrcBtqa2XUtu5ckIxs07T7BnedIocqL8MGImIJ9MZw1Zg1ZQ6q4C70/IO4EpJSuVbI+JYRBwCRlJ7VdtM+1yR2iC1ubq4rpmZWTVFJpU+4JmK9cOprGqdiDgBHCW7fFVr31rlC4EjqY1avwsASddLKksqj42NnUK3zMysljk3pTgi7oyIUkSUent7Wx2OmVlHKTKpjAIXVKyfn8qq1pE0DziLbMC+1r61yl8AelIbtX6XmZkVrMikshdYKmmJpDPIBt4Hp9QZBNal5TXA7simow0CayUtSLO6lgIP1Goz7XN/aoPU5l/n3aEip0OambVC3u9rhd37KyJOSNoADJFN/70rIh6VdBNQjohBYAtwj6QR4EWyJEGqtx04CJwAboiICYBqbaZf+fvAVkn/Cdif2s6dE4uZWW3+8qO/UW9m1pSWfE/FzMzmHicVMzPLjZOKmZnlxknFzMxyM6cH6iWNAU+f4u7nAj/NMZx24D7PDe5z5zvd/v5KRFT99vicTiqnQ1K51uyHTuU+zw3uc+crsr++/GVmZrlxUjEzs9w4qZy6O1sdQAu4z3OD+9z5Cuuvx1TMzCw3PlMxM7PcOKmYmVlunFROgaSVkoYljUja1Op4TpWkCyTdL+mgpEcl/btUfo6kv5X0w/Tv2alckr6Q+v2wpEsr2lqX6v9Q0rpav3O2kNQlab+kb6T1JZL2pL5tS49WID1+YVsq3yNpcUUbA6l8WFJ/i7rSEEk9knZIelzSY5Le3enHWdJn0t/1I5L+QtIbO+04S7pL0vOSHqkoy+24SnqXpANpny9I0rRBRYR/mvghu+X+j4ALgTOAh4DlrY7rFPtyHnBpWv4HwBPAcuBzwKZUvgm4NS1/EPgmIOByYE8qPwd4Mv17dlo+u9X9m6bvNwJfA76R1rcDa9Pyl4BPpuXfA76UltcC29Ly8nTsFwBL0t9EV6v7Vae/dwOfSMtnAD2dfJzJHid+COiuOL4f67TjDPxT4FLgkYqy3I4r2XOsLk/7fBO4etqYWv2itNsP8G5gqGJ9ABhodVw59e2vgauAYeC8VHYeMJyWvwxcV1F/OG2/DvhyRfnr6s22H7Ing34HuAL4RvoP81Ng3tRjTPbsnnen5XmpnqYe98p6s+2H7Imqh0gTc6Yev048zimpPJPeKOel49zficcZWDwlqeRyXNO2xyvKX1ev1o8vfzVv8o910uFU1tbS6f4KYA/w5oh4Lm36CfDmtFyr7+32mvwX4LPAK2l9IXAkIk6k9cr4X+1b2n401W+nPi8BxoCvpkt+X5H0S3TwcY6IUeA/Az8GniM7bvvo7OM8Ka/j2peWp5bX5aRiSHoT8JfApyPiZ5XbIvuI0jHzziX9FvB8ROxrdSwzaB7ZJZI/jYgVwM/JLou8qgOP89nAKrKEugj4JWBlS4NqgVYcVyeV5o0CF1Ssn5/K2pKk+WQJ5d6I2JmK/6+k89L284DnU3mtvrfTa/Ie4MOSngK2kl0C+xOgR9Lk47Ur43+1b2n7WcALtFefDwOHI2JPWt9BlmQ6+Ti/HzgUEWMRcRzYSXbsO/k4T8rruI6m5anldTmpNG8vsDTNIjmDbFBvsMUxnZI0k2ML8FhEfL5i0yAwOQNkHdlYy2T576ZZJJcDR9Np9hDwAUlnp0+IH0hls05EDETE+RGxmOzY7Y6IfwncD6xJ1ab2efK1WJPqRypfm2YNLQGWkg1qzjoR8RPgGUnLUtGVwEE6+DiTXfa6XNKZ6e98ss8de5wr5HJc07afSbo8vYa/W9FWba0eZGrHH7JZFE+QzQT5g1bHcxr9eC/ZqfHDwIPp54Nk15K/A/wQ+DZwTqov4PbU7wNAqaKtfw2MpJ+Pt7pvDfb/N3lt9teFZG8WI8DXgQWp/I1pfSRtv7Bi/z9Ir8UwDcyKaXFf3wmU07HeRTbLp6OPM/AfgMeBR4B7yGZwddRxBv6CbMzoONkZ6fo8jytQSq/fj4AvMmWyR7Uf36bFzMxy48tfZmaWGycVMzPLjZOKmZnlxknFzMxy46RiZma5cVIxM7PcOKmYmVlu/j/PnDiVr/Qh3gAAAABJRU5ErkJggg==\n"
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "listaTeste = ListaComElementoFinal()\n",
    "func = partial(marcaTempo(listaTeste.insereValor), posicao=-1)\n",
    "benchmark(func)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "E agora para tirar estes elementos? Como será o comportamento"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Benchmark levou 4.99E-03s no total, e 4.99E-07±1.22E-06s por iteração\n"
     ]
    },
    {
     "data": {
      "text/plain": "<Figure size 432x288 with 1 Axes>",
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZsAAAD4CAYAAAA6j0u4AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8qNh9FAAAACXBIWXMAAAsTAAALEwEAmpwYAAAa8ElEQVR4nO3df5TVd33n8eerAySk2hBhjk0gETRsthO1TXo34sZta8gKpN3AWbM9UK3oYnOOTWqrPRg4ursac44ie2TXXVCxZEvT6oBslkxtUk4baLerhuQiNQTMxBGSwEQ3I7/cYyhhxvf+8f0MuVzuzL1D7mcuXF6Pc+6Z7/f9/Xzf389nvmTe+X7v596vIgIzM7Ocfq7VHTAzs/bnYmNmZtm52JiZWXYuNmZmlp2LjZmZZTeh1R04H02bNi1mzpzZ6m6YmV1Qdu3a9eOI6Ky1zcWmhpkzZ1Iul1vdDTOzC4qk50ba5ttoZmaWnYuNmZll52JjZmbZudiYmVl2LjZmZpadZ6NZFlt397N6Wy8vHDvBVVMms3zedSy6YXqru2VmLZL1ykbSfEm9kvokraix/RJJm9L2nZJmVmxbmeK9kubVyynp7hQLSdMq4u+R9KSkPZK+JemXMw7ZKArNygf30H/sBAH0HzvBygf3sHV3f6u7ZmYtkq3YSOoA1gILgC5giaSuqmbLgKMRcS2wBliV9u0CFgPXA/OBdZI66uT8JnArUD3P+wDw6xHxFuDTwPqmDtTOsnpbLydODZ0RO3FqiNXbelvUIzNrtZxXNjcBfRGxPyJeBrqBhVVtFgIb0/IWYK4kpXh3RJyMiANAX8o3Ys6I2B0Rz1Z3IiK+FRFH0+pjwIxmDtLO9sKxE2OKm1n7y1lspgMHK9YPpVjNNhExCBwHpo6ybyM5R7MMeKTWBkl3SipLKg8MDIwhpVW7asrkMcXNrP1dNLPRJL2TotjcU2t7RKyPiFJElDo7a361jzVo+bzrmDyx44zY5IkdLJ93XYt6ZGatlnM2Wj9wdcX6jBSr1eaQpAnA5cDhOvvWy3kWSW8F/gRYEBGHxzAGOwfDs848G83MhuUsNk8AsyXNoigIi4HfqWrTAywFvg3cAWyPiJDUA3xV0ueBq4DZwOOAGsh5BknXAA8CvxsRzzRrcDa6RTdMd3Exs9OyFZuIGJR0N7AN6ADuj4i9ku4FyhHRA2wAHpDUBxyhKB6kdpuBfcAgcFdEDEExxbk6Z4p/GPgY8IvAk5IejogPAv+R4n2gdcXcAwYjopRr3GZmdjZFRKv7cN4plUrhRwyYmY2NpF0j/c/8RTNBwMzMWsfFxszMsnOxMTOz7FxszMwsOxcbMzPLzsXGzMyyc7ExM7PsXGzMzCw7FxszM8vOxcbMzLJzsTEzs+xcbMzMLDsXGzMzy87FxszMsnOxMTOz7FxszMwsOxcbMzPLzsXGzMyyc7ExM7PsXGzMzCw7FxszM8vOxcbMzLJzsTEzs+xcbMzMLLusxUbSfEm9kvokraix/RJJm9L2nZJmVmxbmeK9kubVyynp7hQLSdMq4pL0hbTtSUk3ZhyymZnVkK3YSOoA1gILgC5giaSuqmbLgKMRcS2wBliV9u0CFgPXA/OBdZI66uT8JnAr8FzVMRYAs9PrTuCLzRynmZnVl/PK5iagLyL2R8TLQDewsKrNQmBjWt4CzJWkFO+OiJMRcQDoS/lGzBkRuyPi2Rr9WAj8WRQeA6ZIurKpIzUzs1HlLDbTgYMV64dSrGabiBgEjgNTR9m3kZzn0g8k3SmpLKk8MDBQJ6WZmY2FJwgkEbE+IkoRUers7Gx1d8zM2krOYtMPXF2xPiPFaraRNAG4HDg8yr6N5DyXfpiZWUY5i80TwGxJsyRNonjDv6eqTQ+wNC3fAWyPiEjxxWm22iyKN/cfbzBntR7gfWlW2hzgeET8sBkDNDOzxkzIlTgiBiXdDWwDOoD7I2KvpHuBckT0ABuAByT1AUcoigep3WZgHzAI3BURQ1BMca7OmeIfBj4G/CLwpKSHI+KDwMPAbRSTDF4CPpBrzGZmVpuKCwmrVCqVolwut7obZmYXFEm7IqJUa5snCJiZWXYuNmZmlp2LjZmZZediY2Zm2bnYmJlZdi42ZmaWnYuNmZll52JjZmbZudiYmVl2LjZmZpadi42ZmWXnYmNmZtm52JiZWXYuNmZmlp2LjZmZZediY2Zm2bnYmJlZdi42ZmaWnYuNmZll52JjZmbZudiYmVl2LjZmZpadi42ZmWXnYmNmZtllLTaS5kvqldQnaUWN7ZdI2pS275Q0s2LbyhTvlTSvXk5Js1KOvpRzUopfI2mHpN2SnpR0W84xm5nZ2bIVG0kdwFpgAdAFLJHUVdVsGXA0Iq4F1gCr0r5dwGLgemA+sE5SR52cq4A1KdfRlBvgE8DmiLgh5VyXY7xmZjaynFc2NwF9EbE/Il4GuoGFVW0WAhvT8hZgriSleHdEnIyIA0BfylczZ9rnlpSDlHNRWg7gF9Ly5cALzR2mmZnVk7PYTAcOVqwfSrGabSJiEDgOTB1l35HiU4FjKUf1sT4JvFfSIeBh4A9qdVbSnZLKksoDAwONj9LMzOq6GCYILAH+NCJmALcBD0g6a9wRsT4iShFR6uzsHPdOmpm1s5zFph+4umJ9RorVbCNpAsVtrsOj7DtS/DAwJeWoPtYyYDNARHwbuBSY9irGZWZmY5Sz2DwBzE6zxCZRvDnfU9WmB1ialu8AtkdEpPjiNFttFjAbeHyknGmfHSkHKedDafl5YC6ApF+iKDa+T2ZmNo4m1G9ybiJiUNLdwDagA7g/IvZKuhcoR0QPsIHitlYfcISieJDabQb2AYPAXRExBFArZzrkPUC3pPuA3Sk3wB8DX5H0EYrJAu9PxcnMzMaJ/Hf3bKVSKcrlcqu7YWZ2QZG0KyJKtbZdDBMEzMysxVxszMwsOxcbMzPLzsXGzMyyqzsbTVIJ+FfAVcAJ4CngbyLiaOa+mZlZmxjxykbSByR9B1gJTAZ6gReBdwB/K2mjpGvGp5tmZnYhG+3K5jLg5og4UWujpF+h+LDl8xn6ZWZmbWTEYhMRa0fbMSL+sem9MTOztlR3goCkz0n6BUkTJT0qaUDSe8ejc2Zm1h4amY32roj4CfBbwLPAtcDynJ0yM7P20kixGb7V9pvA1yPieMb+mJlZG2rkizi/IelpimnPH5LUCfxT3m6ZmVk7qXtlExErgH8JlCLiFPASZz/e2czMbESjfc7mHcPLEXFk+Cv+I+KnEfGjNGngzePRSTMzu7CNdhvt3ZI+B/w1sIvigWOXUkwQeCfwBopnxZiZmY1qtM/ZfETS64B3A/8OuJLifZvvAV+OiP8zPl00M7ML3agTBCLiCPCV9DIzMzsn/tZnMzPLzsXGzMyyc7ExM7PsGnmezUTgQ8CvpdDfA19Kn7kxMzOrq5FvEPgiMBFYl9Z/N8U+mKtTZmbWXhopNv8iIn65Yn27pO/m6pCZmbWfRt6zGZL0puEVSW8EhhpJLmm+pF5JfZJW1Nh+iaRNaftOSTMrtq1M8V5J8+rllDQr5ehLOSdVbPttSfsk7ZX01Ub6bmZmzdNIsVkO7JD0d5L+HthOA98cIKkDWAssALqAJZK6qpotA45GxLXAGmBV2rcLWAxcD8wH1knqqJNzFbAm5TqaciNpNsWjrW+OiOuBP2pgzGZm1kSNfBHnoxSPf/4w8AfAdRGxo4HcNwF9EbE/Il4Gujn7CzwXAhvT8hZgriSleHdEnIyIA0BfylczZ9rnlpSDlHNRWv49YG1EHE3jebGBvpuZWRM1MhvtUuD3gXcAAfyDpC9FRL3HDEwHDlasHwLeNlKbiBiUdByYmuKPVe07PS3XyjkVOBYRgzXa/7M0jm8CHcAnI+Kv6/TdzMyaqJEJAn8G/D/gv6X13wEeoPi+tAvBBIors98AZgD/W9JbIuJYZSNJdwJ3AlxzzTXj3EUzs/bWSLF5c0RUvteyQ9K+BvbrB66uWJ+RYrXaHJI0AbgcOFxn31rxw8AUSRPS1U1l+0PAzvS5oAOSnqEoPk9UdiQi1gPrAUqlUjQwPjMza1AjEwS+I2nO8IqktwHlBvZ7ApidZolNonjDv6eqTQ+wNC3fAWyPiEjxxWm22iyK4vD4SDnTPjtSDlLOh9LyVoqrGiRNo7ittr+B/puZWZM0cmXzq8C3JD2f1q8BeiXtASIi3lprp/QezN3ANor3Su6PiL2S7gXKEdEDbAAekNQHHKEoHqR2m4F9wCBw1/DD22rlTIe8B+iWdB+wO+UmtX1XuhobApZHxOGGfjtmZtYUKi4KRmkgvWG07RHxXFN7dB4olUpRLjdy8WZmZsMk7YqIUq1tda9sIuI5SVdQvFcyoSL+neZ10czM2lkjU58/Dbwf+AHF1GfSz1vydcvMzNpJI+/Z/DbwpvQhSjMzszFrZDbaU8CUzP0wM7M21siVzWeA3ZKeAk4OByPi9my9MjOzttJIsdlI8SWXe4Cf5e2OmZm1o0aKzUsR8YXsPTEzs7bVSLH5B0mfofhUf+VtNE99NjOzhjRSbG5IP+dUxDz12czMGtbIhzrfOR4dMTOz9lV36rOk10vaIOmRtN4laVn+rpmZWbto5HM2f0rxZZZXpfVn8KOVzcxsDEYsNun5MgDTImIzadpzel7M0Dj0zczM2sRoVzaPp58/lTSV9L1o6dk2x3N3zMzM2sdoEwSUfn6UYtrzmyR9E+jklYeUmZmZ1TVasemU9NG0/L+AhykK0EngVuDJzH0zM7M2MVqx6QBewytXOMMuy9cdMzNrR6MVmx9GxL3j1hMzM2tbo00QqL6iMTMzOyejFZu549YLMzNrayMWm4g4Mp4dMTOz9tXINwiYmZm9Ki42ZmaWnYuNmZlll7XYSJovqVdSn6QVNbZfImlT2r5T0syKbStTvFfSvHo5Jc1KOfpSzklVx3q3pJBUyjRcMzMbQbZiI6kDWAssALqAJZK6qpotA45GxLXAGmBV2rcLWAxcD8wH1knqqJNzFbAm5Tqacg/35bXAHwI7c4zVzMxGl/PK5iagLyL2R8TLQDewsKrNQmBjWt4CzJWkFO+OiJMRcQDoS/lq5kz73JJykHIuqjjOpymK0T81eYxmZtaAnMVmOnCwYv1QitVskx5dcByYOsq+I8WnAsdSjjOOJelG4OqI+KtXPyQzMzsXbT1BQNLPAZ8H/riBtndKKksqDwwM5O+cmdlFJGex6QeurlifkWI126SHtV0OHB5l35Hih4EpFQ98G46/Fngz8HeSngXmAD21JglExPqIKEVEqbOzc8yDNTOzkeUsNk8As9MssUkUb/j3VLXpAZam5TuA7RERKb44zVabBcymeJhbzZxpnx288pydpcBDEXE8IqZFxMyImAk8BtweEeVcgzYzs7ON9q3Pr0pEDEq6G9hG8biC+yNir6R7gXJE9AAbgAck9QFHKIoHqd1mYB8wCNwVEUMAtXKmQ94DdEu6D9idcpuZ2XlAxUWBVSqVSlEu++LHzGwsJO2KiJqfZWzrCQJmZnZ+cLExM7PsXGzMzCw7FxszM8vOxcbMzLJzsTEzs+xcbMzMLDsXGzMzy87FxszMsnOxMTOz7FxszMwsOxcbMzPLzsXGzMyyc7ExM7PsXGzMzCw7FxszM8vOxcbMzLJzsTEzs+xcbMzMLDsXGzMzy87FxszMsnOxMTOz7FxszMwsOxcbMzPLLmuxkTRfUq+kPkkramy/RNKmtH2npJkV21ameK+kefVySpqVcvSlnJNS/KOS9kl6UtKjkt6Qc8xmZna2bMVGUgewFlgAdAFLJHVVNVsGHI2Ia4E1wKq0bxewGLgemA+sk9RRJ+cqYE3KdTTlBtgNlCLircAW4HM5xmtmZiPLeWVzE9AXEfsj4mWgG1hY1WYhsDEtbwHmSlKKd0fEyYg4APSlfDVzpn1uSTlIORcBRMSOiHgpxR8DZjR/qGZmNpqcxWY6cLBi/VCK1WwTEYPAcWDqKPuOFJ8KHEs5RjoWFFc7j9TqrKQ7JZUllQcGBuoOzszMGnfRTBCQ9F6gBKyutT0i1kdEKSJKnZ2d49s5M7M2NyFj7n7g6or1GSlWq80hSROAy4HDdfatFT8MTJE0IV3dnHEsSbcCHwd+PSJOvspxmZnZGOW8snkCmJ1miU2ieMO/p6pND7A0Ld8BbI+ISPHFabbaLGA28PhIOdM+O1IOUs6HACTdAHwZuD0iXsw0VjMzG0W2K5uIGJR0N7AN6ADuj4i9ku4FyhHRA2wAHpDUBxyhKB6kdpuBfcAgcFdEDAHUypkOeQ/QLek+ihloG1J8NfAa4OvFPAKej4jbc43bzGrburuf1dt6eeHYCa6aMpnl865j0Q213lq1dqTiosAqlUqlKJfLre6GWdvYuruflQ/u4cSpodOxyRM7+My/fYsLThuRtCsiSrW2XTQTBMysdVZv6z2j0ACcODXE6m29LeqRjTcXGzPL7oVjJ8YUt/bjYmNm2V01ZfKY4tZ+XGzMLLvl865j8sSOM2KTJ3awfN51LeqRjbecn7MxMwM4PQnAs9EuXi42ZjYuFt0w3cXlIubbaGZmlp2LjZmZZediY2Zm2bnYmJlZdi42ZmaWnYuNmZll52JjZmbZudiYmVl2LjZmZpadi42ZmWXnYmNmZtm52JiZWXYuNmZmlp2/9blJtu7u99enX6B87szyc7Fpgq27+1n54J7Tz1jvP3aClQ/uAfAfrfPc1t39LN/yXU4NBVCcu+Vbvgv43Jk1k2+jNcHqbb2nC82wE6eGWL2tt0U9skZ96i/3ni40w04NBZ/6y70t6pGNl627+7n5s9uZteKvuPmz29m6u7/VXWprvrJpgheOnagZ7z92gvd85dv8xe+9/XSskVs2n9i6h6/tPMhQvPJHcHpqC0Vx6z92gg6JoQimT5nMzKmTeWz/UYYiEHDZpA5eennojGOMduzhbdV53/nPO9nx9MCI/W1kv8snT+TlwSFeOvUzAK64bCL/6d9cf3oslbkBPtmzl2MnTp3Rtt5VRq2x1cpfnefoS6dq5hspbmN3Pt6mPNe7EefjWC4Uioj6rS4ypVIpyuVyw+1/6T88won0h9TM7EIn4D1zruG+RW8Z237Srogo1dqW9TaapPmSeiX1SVpRY/slkjal7TslzazYtjLFeyXNq5dT0qyUoy/lnFTvGM1yctCFxszaRwB//tjzfGLrnqblzFZsJHUAa4EFQBewRFJXVbNlwNGIuBZYA6xK+3YBi4HrgfnAOkkddXKuAtakXEdT7hGP0Uw/88WhmbWhP3/s+ablynllcxPQFxH7I+JloBtYWNVmIbAxLW8B5kpSindHxMmIOAD0pXw1c6Z9bkk5SDkX1TlG03Q0N52ZWdvJWWymAwcr1g+lWM02ETEIHAemjrLvSPGpwLGUo/pYIx3jDJLulFSWVB4YGBjTQJe87eoxtTczu9h46nMSEesjohQRpc7OzjHtO9Y30czMLjY5i00/UPm//DNSrGYbSROAy4HDo+w7UvwwMCXlqD7WSMcwM7NRTGjiOwQ5i80TwOw0S2wSxRv+PVVteoClafkOYHsUc7F7gMVpJtksYDbw+Eg50z47Ug5SzofqHKOpnv3sbzY7pZlZy0wQ9H2meX/Xsn2oMyIGJd0NbAM6gPsjYq+ke4FyRPQAG4AHJPUBRyiKB6ndZmAfMAjcFRFDALVypkPeA3RLug/YnXIz0jFycMExM6vNH+qsYawf6jQzsxZ+qNPMzAxcbMzMbBy42JiZWXYuNmZmlp0nCNQgaQB47hx3nwb8uInduRB4zBcHj/ni8GrG/IaIqPmpeBebJpNUHmk2RrvymC8OHvPFIdeYfRvNzMyyc7ExM7PsXGyab32rO9ACHvPFwWO+OGQZs9+zMTOz7HxlY2Zm2bnYmJlZdi42TSRpvqReSX2SVrS6P+dK0tWSdkjaJ2mvpD9M8ddJ+htJ308/r0hxSfpCGveTkm6syLU0tf++pKUjHfN8IalD0m5J30jrsyTtTGPblB5tQXr8xaYU3ylpZkWOlSneK2lei4bSEElTJG2R9LSk70l6e7ufZ0kfSf+un5L0NUmXttt5lnS/pBclPVURa9p5lfSrkvakfb4gqf6TbyLCrya8KB558APgjcAk4LtAV6v7dY5juRK4MS2/FngG6AI+B6xI8RXAqrR8G/AIIGAOsDPFXwfsTz+vSMtXtHp8dcb+UeCrwDfS+mZgcVr+EvChtPz7wJfS8mJgU1ruSuf+EmBW+jfR0epxjTLejcAH0/IkYEo7n2eKx8QfACZXnN/3t9t5Bn4NuBF4qiLWtPNK8XyxOWmfR4AFdfvU6l9Ku7yAtwPbKtZXAitb3a8mje0h4F8DvcCVKXYl0JuWvwwsqWjfm7YvAb5cET+j3fn2onjC66PALcA30n9IPwYmVJ9jimcqvT0tT0jtVH3eK9udby+Kp9YeIE0Uqj5/7XieU7E5mP6ATkjneV47nmdgZlWxacp5Tdueroif0W6kl2+jNc/wP+Jhh1LsgpZuG9wA7AReHxE/TJt+BLw+LY809gvtd/JfgI8BP0vrU4FjETGY1iv7f3psafvx1P5CGvMsYAD4H+nW4Z9I+nna+DxHRD/wn4HngR9SnLddtPd5Htas8zo9LVfHR+ViYyOS9BrgfwJ/FBE/qdwWxf/StM28eUm/BbwYEbta3ZdxNIHiVssXI+IG4KcUt1dOa8PzfAWwkKLQXgX8PDC/pZ1qgVacVxeb5ukHrq5Yn5FiFyRJEykKzV9ExIMp/H8lXZm2Xwm8mOIjjf1C+p3cDNwu6Vmgm+JW2n8Fpkgafnx6Zf9Pjy1tvxw4zIU15kPAoYjYmda3UBSfdj7PtwIHImIgIk4BD1Kc+3Y+z8OadV7703J1fFQuNs3zBDA7zWqZRPFmYk+L+3RO0sySDcD3IuLzFZt6gOEZKUsp3ssZjr8vzWqZAxxPl+vbgHdJuiL9H+W7Uuy8ExErI2JGRMykOHfbI+I9wA7gjtSseszDv4s7UvtI8cVpFtMsYDbFm6nnnYj4EXBQ0nUpNBfYRxufZ4rbZ3MkXZb+nQ+PuW3Pc4WmnNe07SeS5qTf4fsqco2s1W9itdOLYlbHMxQzUz7e6v68inG8g+IS+0ngH9PrNop71Y8C3wf+Fnhdai9gbRr3HqBUkevfA33p9YFWj63B8f8Gr8xGeyPFH5E+4OvAJSl+aVrvS9vfWLH/x9PvopcGZum0eKy/ApTTud5KMeuorc8z8CngaeAp4AGKGWVtdZ6Br1G8J3WK4gp2WTPPK1BKv78fAP+dqkkmtV7+uhozM8vOt9HMzCw7FxszM8vOxcbMzLJzsTEzs+xcbMzMLDsXGzMzy87FxszMsvv/fg3D6yG74I4AAAAASUVORK5CYII=\n"
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "def benchmarkRemocao(func, itens=10000, pulaImpressao=False):\n",
    "    tempos = []\n",
    "    for i in range(itens):\n",
    "        resultado, tempo = func()\n",
    "        tempos.append(tempo)\n",
    "    if not pulaImpressao:\n",
    "        print(f\"Benchmark levou {sum(tempos):.2E}s no total, e {statistics.mean(tempos):.2E}±{statistics.stdev(tempos):.2E}s por iteração\")\n",
    "        plt.scatter(list(range(itens)), tempos)\n",
    "        plt.ylabel(\"Tempo (s)\")\n",
    "        plt.show()\n",
    "\n",
    "func = partial(marcaTempo(listaTeste.removerValor), posicao=0)\n",
    "benchmarkRemocao(func)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Também bastante rápido removendo do começo da lista.\n",
    "\n",
    "O problema vem na hora de remover elementos do final.\n",
    "\n",
    "Não tem escapatória, já que mesmo com a referência para o último elemento, não podemos removê-lo e atualizar o elemento anterior a ele para ser o novo último elemento."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Benchmark levou 6.82E+00s no total, e 6.82E-04±4.58E-04s por iteração\n"
     ]
    },
    {
     "data": {
      "text/plain": "<Figure size 432x288 with 1 Axes>",
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZUAAAD4CAYAAAAkRnsLAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8qNh9FAAAACXBIWXMAAAsTAAALEwEAmpwYAAAk3UlEQVR4nO3df5TV9X3n8efLYcTRpALGemSUgEpxsTaQThWXnJ6Y1EKkicTaikla27Vxt9VzqnbZDtU9MTZZMbTqdpukNatNNhrFGHdCxZQasduzrhJRUESdBBWVCUaqYHJkosPw3j/u5453hntn7p253/trXo9z7uHez/fz/d7Ply/Mez6/FRGYmZlVw2H1LoCZmbUOBxUzM6saBxUzM6saBxUzM6saBxUzM6uaKfUuQD29733vi9mzZ9e7GGZmTeXxxx//t4g4ttixSR1UZs+ezebNm+tdDDOzpiLppVLH3PxlZmZV46BiZmZVk2lQkbRUUq+kHZK6ixyfKmltOr5J0uyCY6tSeq+kJSntREkPSXpG0nZJf1qQ/1pJfZK2pte5Wd6bmZkdKrM+FUltwJeBc4BdwGOS1kXEMwXZLgH2RsQpklYANwAXSpoPrABOA2YC35f0S8AB4M8i4glJ7wUel/RAwTVvioi/yuqezMxsdFnWVM4AdkTECxHxDnAXcN6IPOcB30jv7wE+Kkkp/a6IeDsiXgR2AGdExO6IeAIgIn4GPAt0ZngPZmZWgSyDSifwSsHnXRwaAIbyRMQB4E3gmHLOTU1lC4FNBcmXS3pK0m2SphcrlKRLJW2WtHnPnj0V3xRAz5Y+Fq/eyJzu9SxevZGeLX3juo6ZWatpyo56Se8BvgNcERE/TclfBU4GFgC7gb8udm5E3BIRXRHRdeyxRYdZj6pnSx+r7t1G375+Aujb18+qe7c5sJiZkW1Q6QNOLPh8QkormkfSFOBo4PXRzpXUTi6g3BER9+YzRMRPImIwIg4CXyPX/FZ1azb00j8wOCytf2CQNRt6s/g6M7OmkmVQeQyYK2mOpMPJdbyvG5FnHXBxen8BsDFyG7ysA1ak0WFzgLnAD1J/y63AsxFxY+GFJB1f8PGTwNNVvyPgx/v6K0o3M5tMMhv9FREHJF0ObADagNsiYruk64DNEbGOXID4pqQdwBvkAg8p393AM+RGfF0WEYOSPgT8HrBN0tb0VX8REfcDX5K0AAhgJ/Afs7ivmdM66CsSQGZO68ji68zMmoom886PXV1dUekyLfk+lcImsI72Nq4//3SWL/RANDNrfZIej4iuYscm9dpf45EPHGs29PLjff3MnNbByiXzHFDMzHBQGZflCzsdRMzMinBQGYeeLX2uqZiZFeGgUqGRfSr5eSqAA4uZTXpNOfmxnjxPxcysNAeVCnmeiplZaQ4qFSo1H8XzVMzMHFQqtnLJPDra24aldbS3sXLJvDqVyMyscbijvkKep2JmVpqDyjh4noqZWXFu/jIzs6pxTWUcPPnRzKw4B5UKefKjmVlpbv6qkCc/mpmV5qBSIU9+NDMrzUGlQp78aGZWmoNKhVYumUf7YRqW1n6YPPnRzAwHlfHRGJ/NzCYpB5UKrdnQy8Dg8C2YBwbDHfVmZjioVMwd9WZmpTmoVKhUh/zRHe01LomZWeNxUKlQsY56gLfeOUDPlr46lMjMrHE4qFRo+cJO3nPEoQsRuF/FzMzLtIzLvv0DRdNH9qt4jTAzm2wcVMZh5rQO+op0zAcwu3s9bRKLTprOEy+/6TXCzGxScfPXOBTb/bHQYAQPP/+G1wgzs0nHQWWcpk4Z319dsRqOmVmrcPNXhUYufV+pNnn6vZm1LtdUKlRs6ftKDEaMncnMrEk5qFRoojPnXVMxs1bmoFKhiS5x75qKmbWyTIOKpKWSeiXtkNRd5PhUSWvT8U2SZhccW5XSeyUtSWknSnpI0jOStkv604L8MyQ9IOlH6c/pWdzTyiXzylqUuFSNpNP7rphZC8ssqEhqA74MfAyYD1wkaf6IbJcAeyPiFOAm4IZ07nxgBXAasBT4SrreAeDPImI+sAi4rOCa3cCDETEXeDB9rrrlCzv59KJZowaWjvY2LjrzRO+7YmaTTpY1lTOAHRHxQkS8A9wFnDciz3nAN9L7e4CPSlJKvysi3o6IF4EdwBkRsTsingCIiJ8BzwKdRa71DWB5NrcFXe+fMWwBySPbD2P6ke2IXE3k+vNPp+v9M7zviplNOlkOKe4EXin4vAs4s1SeiDgg6U3gmJT+6Ihzh01DT01lC4FNKem4iNid3r8KHFesUJIuBS4FmDVrVkU3BLkhxSvveXLYnioDB4P/9vHTWL6wc2hplmLzUfLrg3lGvZm1qqacpyLpPcB3gCsi4qcjj0dESCraIx4RtwC3AHR1dVXca/75f9xedJOuld/eyrXrtrOvv/i6YHned8XMWlmWzV99wIkFn09IaUXzSJoCHA28Ptq5ktrJBZQ7IuLegjw/kXR8ynM88FrV7qTA3hKLSQ4cZMyAAhMfPWZm1siyDCqPAXMlzZF0OLmO93Uj8qwDLk7vLwA2RkSk9BVpdNgcYC7wg9TfcivwbETcOMq1Lga+W/U7mqCO9jZ31JtZS8us+Sv1kVwObADagNsiYruk64DNEbGOXID4pqQdwBvkAg8p393AM+RGfF0WEYOSPgT8HrBN0tb0VX8REfcDq4G7JV0CvAT8blb3Nh6dXvrezCYBxSSejNfV1RWbN2+u6JzZ3evH9V03X7jAAcXMWoKkxyOiq9gxz6ivES95b2aTQVOO/qqXiexBX2yIsXeGNLNW46BSgYnUNkYu2zJyCX3vDGlmrcDNXxWYyByTkQtJFltC3ztDmlmzc1CpQOHSLJUasQxYyQDlyZFm1swcVCrw1ttjT24s5eCIQXalJkF6cqSZNTMHlQoMHKzetVYumedVjM2s5Tio1JNXMTazFuOgUoGR/SITsWZDb9GFKd1Rb2bNzEGlAmedNKNq1yrVId+3r5/FqzdOaE6MmVm9OKhU4ImX91XtWqN1yOfnrDiwmFmzcVCpQP8Ee+oLg0Sxjvrh3+U5K2bWfBxUauiKtVtZeN0/vxtcxuij8ZwVM2s2XqalxvbuH2DlPU/ynqlTDumoH8lzVsys2Tio1MHAYJTcQTKvvU2cfeqxLF690QtOmlnTcFCpgIBa7T4zOBisfeyVodqMF5w0s2bgPpUK1HI7s4NwSPOYO+/NrNE5qFSgswH6ONx5b2aNzEGlAiuXzKOjva2uZXDnvZk1MvepVCDfl7FmQ2/RnRxr4exTj63L95qZlcNBpULLF3YW7Sj/9Nce4eHn38j8+x96bk/m32FmNl5u/qqSOz57FjtXL8v8e7w2mJk1MgeVKtu5elnmwcVrg5lZo3JQycjO1cu4+cIFmV3fw4vNrBE5qGRo+cJOdq5exnHvPTyT63t4sZk1GgeVGth09TnsXL2MxSdXbz8WM7NG5KBSQ/nO/M8smlWV6wVwTc+2qlzLzKwaFFHLxUcaS1dXV2zevLmuZZjdvX7C16jFqDMzszxJj0dEV7FjrqnUWX60mJvGzKwVOKg0iFrNczEzy5KDSoPZuXoZc3/xqHoXw8xsXDINKpKWSuqVtENSd5HjUyWtTcc3SZpdcGxVSu+VtKQg/TZJr0l6esS1rpXUJ2lrep2b5b1l6YGrPlyTSZRmZtWWWVCR1AZ8GfgYMB+4SNL8EdkuAfZGxCnATcAN6dz5wArgNGAp8JV0PYCvp7RiboqIBel1fzXvp17G6m9x4MlWz5Y+Fq/eyJzu9V4ex6wMWS4oeQawIyJeAJB0F3Ae8ExBnvOAa9P7e4C/laSUfldEvA28KGlHut4jEfGvhTWayeCOz55V7yJMSj1b+lh17zb6BwYB775pVo4xayqSuiRdKWmNpOsk/a6k6WVcuxN4peDzrpRWNE9EHADeBI4p89xiLpf0VGoiK6eMZiWt2dA7FFDyvDyO2ehKBhVJfyjpCWAV0AH0Aq8BHwK+L+kbkqozi686vgqcDCwAdgN/XSyTpEslbZa0ec8eLyNvpZVaBsfL45iVNlrz15HA4ogo+j9I0gJgLvByifP7gBMLPp+Q0orl2SVpCnA08HqZ5w4TET8pKNvXgPtK5LsFuAVykx9Hu6ZNbjOndRTdjM27b5qVVrKmEhFfLhVQ0vGtEfHgKNd+DJgraY6kw8l1vK8bkWcdcHF6fwGwMXJT/NcBK9LosDnkgtcPRrsRSccXfPwk8HSpvGblKLZ9dEd7GyuXzKtTicwaXzl9Kl+S9AuS2iU9KGmPpM+MdV7qI7kc2AA8C9wdEdtTv8wnUrZbgWNSR/xVQHc6dztwN7lO/X8CLouIwVSeO4FHgHmSdkm6JF3rS5K2SXoKOBu4suy/BbMili/s5PrzT6dzWgcCOqd1cP35p7uT3mwUY679JWlrRCyQ9Engt8j98P/XiPhALQqYpUZY+8vMrNlMdO2vfL/LMuDbEfFm1UpmZmYtpZx5KvdJeg7oB/5Y0rHAz7MtlpmZNaMxayoR0Q38e6ArIgaA/eQmJ5qZmQ0z2jyVD+XfR8Qb+Y7yiHgrIl5Nnfe/XItCmplZcxit+eu3JX2J3Oirx4E9wBHAKeRGV70f+LPMS2hmZk2jZFCJiCslzQB+G/gd4Hhy/SrPAn8fEf+3NkU0M7NmMWpHfUS8AXwtvczMzEaV5SrFVic9W/pYs6GXH+/rZ+a0DlYumecJe2ZWEw4qLaZnSx9Xrd3KwfS5b18/V63dCni5djPLnrcTbjGr7n1qKKDkHUzpZmZZG7OmIqkd+GPg11PS/wH+Ls1ZsQbTPzAypIyebmZWTeU0f30VaAe+kj7/Xkr7o6wKZWZmzamcoPJrIxaP3CjpyawKZBMjoNgSoap1QcxsUiqnT2VQ0sn5D5JOAgZHyW91dER78UdaKt3MrJrKqamsBB6S9AK5X3jfD/xhpqWycft5ib6TUulmZtU0ZlCJiAclzQXy2931RsTb2RbLxstb4JpZPZWz8+MRwGXAtcDnyC1/f0TG5bJxOvvUYytKNzOrpnKav/4X8DPgf6TPnwK+SW49MGswDz23p6J0M7NqKieo/HJEzC/4/JCkZ7IqkE3Mj4s0fY2WbmZWTeUElSckLYqIRwEknQl4Y/c6Gm1tL/epmFk9lTPO9FeB/ydpp6SdwCPAr0naJslrf9TYNT3buHLtVvr29RPk1vZade82erb0AbByyTw62tuGndPR3sbKJfOKXM3MrLoUUWyqXEEG6f2jHY+Il6paohrq6uqKzZubp9J1Tc82bn/05VHzdE7rYPYxHTz6wl4GI2iTuOjME/nC8tNrVEoza3WSHo+IrmLHyhlS/JKk6cCJhfkj4onqFdHG0rOlb8yAArmaS2Hz12AEtz/6Mt/a9DIHA9okFp00nZ2v99d8aXwvyW/W+spZUPIvgT8AnufdFUAC+Eh2xbKRPv+P2yd0/sH05AYjePj5N4bS+/b1s/Ke3Ko7Wf6A79nSx6p7t9E/MDj0vavu3Zb595pZbZXTp/K7wMkR8eGIODu9HFBqbO/+7BaFHhiMCQetsazZ0DsUUPL6BwZZs6E30+81s9oqJ6g8DUzLuBxWZ1kGLfBQZ7PJopwhxdcDWyQ9DQwtzxIRn8isVFYXs7vXD71ffPIM7vjsWVW7toc6m00O5QSVbwA3ANvgkE0FrUU9/PwbnHPjv/DAVR/mmp5t3LnplQmNJlu5ZN6wPhXwUGezVlROUNkfEX+TeUlsVMe993B+8rN3avqdP3rtrWG1F3h3NBlQUWDJd8Y32+gvj1gzq0w581RuJNfstY7hzV9NP6S42eapnHr1/fx8cPTnVSttEs9ff269i5GpkSPWIFe7uv780x1YbFKb0DwVYGH6c1FBmocU18FzXzx3WFNUPdX7+2thtBFrDipmxZUz+fHsWhTEyvOF5acf0uw0somqVq7p2UbX+2ew6t6n6E+bgB0m+NSZs1piBr9HrJlVrpz9VI6TdKuk76XP8yVdUs7FJS2V1Ctph6TuIsenSlqbjm+SNLvg2KqU3itpSUH6bZJeS6PRCq81Q9IDkn6U/pxeThlbwc7Vy4ZevzC1bewTquT2R1/mirVbhwIK5CZZ3v7oy1zTs61m5chKqZFpHrFmVlo581S+DmwAZqbPPwSuGOskSW3Al4GPAfOBiyTNH5HtEmBvRJwC3ERulBkp3wrgNGAp8JV0vXx5lhb5ym7gwYiYCzyYPk86T31+KTtXL2PxyTPqWo7bH32Zedd8b2ihy54tfSxevZE53etZvHrjUHoj8+KcZpUr2VEvaUpEHJD0WET8mqQtEbEwHdsaEQtGvbB0FnBtRCxJn1cBRMT1BXk2pDyPSJoCvAocSwoI+byF+dLn2cB9EfHLBdfqBT4cEbslHQ/8S0SM+r+/2Trqx+ucG/+FH732Vr2LMUz7YWLN73wgs76JckZtVSuP2WQz3o76HwAfBN6SdAxp3S9Ji4A3y/jeTuCVgs+7gDNL5UkB7E3gmJT+6Ihzx/qffFxE7E7vXwWOK5ZJ0qXApQCzZs0a+y5awANXfXjofc+WPq5dt519/dnOoB/LwMHgyrVbgeqv/dWzpY+V336SgbTgWd++flZ+e/j6ZuWuRbZ8YaeDiFkFRgsqSn9eRW448cmSHiZXk7gg64JNRESEpKJVsIi4BbgFcjWVmhasART+kCxnKf0sBbDynifZ/NIb3Pfk7qFAN/3Idj738dPG/cP82nXbhwJK3sDB4Np124fNl/HILrPqGy2oHCvpqvT+fwP3kws0bwO/AYy1QVcfueXy805IacXy7ErNX0cDr5d57kg/kXR8QfPXa2Pkn/SKjSSD2o4mGxiMQwLb3v0DQysnQ+UTJkvVwgrTPbLLLBujBZU24D28W2PJO7LMaz8GzJU0h1xAWAF8akSedcDF5HaTvADYmGoZ64BvpYmXM4G55JrjRpO/1ur053fLLKeNsHP1sqH39RquPDCYq1m8feBgJsvley0ys2yMFlR2R8R1471w6iO5nNzIsTbgtojYLuk6YHNErANuBb4paQfwBrnAQ8p3N/AMcAC4LCIGASTdCXwYeJ+kXcDnIuJWcsHk7jTc+SVyS/bbBOUDTD2CS7EaR//A4LBmrGKmH9ledNXl6Ue2D733WmRm2Rht9NfQaK9WNVlGf1VLvftgCi0+eUbJ3SuLlbO9Tay5YPhoM4/sMhuf0UZ/jRZUZkTEG0UPtggHlfHL/0Au1oRUD/mgARxSAxHw6UXjn+Xv4GM23LiCymTgoFI9Z37xgZqvolzMUYe38dY7g4ekd07r4OHuyper86KSk49/iRjbaEGlnBn1ZmPadPU57Fy9jJsvXFDXchQLKMC4a1TeBnlyyf8S0bevn+DdwSHNsAJEoyhnlWKzso2cLFiv0WPF/NLV93PU1Cns2z9Q9m+gHno8uXj+0sQ5qFimCocnA3z6a4/w8PP16ap7ZzB4J40KK5xlD6Xnwnjo8eTiXyImzn0q7lOpm54tfVyRlmppNPlZ/XBox3+1+lTcdt94Fq/eWPSXiPH2ybUq96lYQ1q+sHNoyf7PLGqsddj27h/gyrVb2fzSG1x//ul0TutA5H64VCugXLV267C2+6vWbnXbfZ15ZeqJc03FNZWG1Eh9MTdfuKDqNYh/91+/N2wfmryO9sN49i8/VtXvssq4Bjk2DykuwUGl8TXShMuJLnRZaLSgObIfyqzRuPnLmtYXlp8+1ERW743H9u4f4Iq1W5nTvb4ldrY0y4JHf1nTuOOzZw37XK+RZEFuZ8t8DapzHE0khym39XKxdLNm5qBiTSsfZOq9s2Xfvn6uWLt1aCRbm8RFZ5446rIwZ500o2hAPOuk+tbGzCbKQcWaXuHOlvUOMACD8e4eMSMDy1hrpu183fMhrLk5qFhLKQww9V6P7PZHX2b9U7uHZvCffeqxfOfxvkNmbBfyJDtrdh795dFfk8Kc7vU0w7/0aR3tHDV1ioezWkMbbfSXayo2KbxYZJhuI82FAWg/TPzs7QNDm5P17esf2lbZgcWahYOKTVqNsG1yoYEiw8EGBoPP/+PoO12aNRIHFTPeDTCNuB5Zsa2RzRqV+1Tcp2KjaJQg09F+2NCyLocJPnXm+HeyNJsoL9NSgoOKlatRgstI45l4aTZRDiolOKjYeNRzT5hS5v7iUcOGU5tlyUGlBAcVq4Z6z4cZ6cj2w5ja3lbRDpdmlfCQYrMMbbr6nKH3jTCKbP/AQfan/pfCHS4dWKwWHFTMqqhwmHKjNJMNHAxWfnurg4rVhJu/3PxlNdAINZg8d+7bRLlPpQQHFau1ni19rLr3qaK7PtaaO/dtvBxUSnBQsXprhFWVCx11eBv73xl0B7+NykGlBAcVaySN0gczkpvLbCRvJ2zWBO747FnsXL2M4957eL2LMkzfvn5W3buNni199S6KNQHXVFxTsQZ2Tc+2oQ2/8hafPIM7PntWXWb5Tz+ync99/DTXWiY5N3+V4KBiraBnSx9Xrd1KLbv+p045jBt++1ccXCapujV/SVoqqVfSDkndRY5PlbQ2Hd8kaXbBsVUpvVfSkrGuKenrkl6UtDW9FmR5b2aNYvnCTl5YvYyd6bX45Oz3uX/7wEGuWLuVT3/tkcy/y5pLZjUVSW3AD4FzgF3AY8BFEfFMQZ4/AX4lIv6TpBXAJyPiQknzgTuBM4CZwPeBX0qnFb2mpK8D90XEPeWW0TUVa2W1bh7LN40BrNnQ690rW1i9lmk5A9gRES+kQtwFnAc8U5DnPODa9P4e4G8lKaXfFRFvAy9K2pGuRxnXNDNyNZjlCzvp2dLHynueZGAw26buvfsHDglizbh7Zc+WPgfFCciy+asTeKXg866UVjRPRBwA3gSOGeXcsa75RUlPSbpJ0tRihZJ0qaTNkjbv2bOn8rsyazLLF3ay5oIP0DmtA5EbIvwLU9tq9v353SubQW5y6jb69vUTeOTbeLTS2l+rgFeBw4FbgD8HrhuZKSJuScfp6uqavKMUbFLJ11oK5X8j79vXn/n3790/wCl/cT9/9TsfaOjf+tds6KV/YHBYWv/AIGs29DZ0uRtJlkGlDzix4PMJKa1Ynl2SpgBHA6+PcW7R9IjYndLelvQPwH+uwj2YtazCQNOzpY9r121nX392WxcfOBhcsXbrUBPZWMOT69EM9eMSAbZUuh0qy6DyGDBX0hxyP/hXAJ8akWcdcDHwCHABsDEiQtI64FuSbiTXUT8X+AGgUteUdHxE7E59MsuBpzO8N7OWUqwmk/U+Mfk+mCvWbj0kwOSbofK1hnwzVL6sWZk5raNozW3mtI7MvrPVZNankvpILgc2AM8Cd0fEdknXSfpEynYrcEzqiL8K6E7nbgfuJtcB/0/AZRExWOqa6Vp3SNoGbAPeB3whq3szmww2XX0ON1+4gI727BfeyAeYOd3rh2oopZqhsnT2qceiEWkd7W2sXDIv0+9tJZ786CHFZmU7ZdV6DtTxR4aAFwv2rKmmni19rPz2kwwcHH6Dn1k0iy8sPz2T72xWXvvLzKpix/XvTrI8om3k7/TZk8hsJNa167YfElAA7ntyd5HcVkorjf4ysxp67ovnDr2v1UTLg0FmfSulBilkOXihFbmmYmYTtnxh51ANJutVlvsHBrli7VYWXvfPnj/SgFxTMbOq2nT1OUPvT736fn6e0Uz+0UaPjcf0I9vZu//QWsn0I9snUsxJxzUVM8vMc188tyaLXOYDzDU928Z9jc99/DTaR/QTtbdpaD0zK49Hf3n0l1lNFdsjptp2jnOEmNf9Ko/3UynBQcWsvmZ3r8/s2qWaxBw4Js5BpQQHFbPGkVWAETDtyHb27R/g6I523nrnwLAVmzva27j+/NOHVnR2wBlbvZa+NzMrW2GTVTUDTMBQB3yx4cGFM/XrsTRMq3FNxTUVs4aWZRNZoVKjvzqndfBw90dqUoZm4ZqKmTWtfA0m6wmWxQIKUJOtAVqJhxSbWVMonGD5mUWzavrdnmRZPjd/ufnLrGnVqmksr9Od94BHf5XkoGLW/GodWAAWnzyDna/3T9pRYu5TMbOWVas+l0IPP//G0HuPEhvONRXXVMxaTi0DTKHJ0jzm5q8SHFTMJpc53eup1U+8Vg4wbv4yM2P4rpFZ98X07esfqi21YmApxTUV11TMJrVaNZUJmDmtoyU6911TMTMrYfnCzmE/3LOqwQTvTqTs29fPynueHPr+VuKgYmZWIKs1yEYaGIyWbB5z85ebv8xsDLXYAwbGvw9MrXn0VwkOKmY2HrWYcPmZRbP4wvLTM/+e8XBQKcFBxcwmqhYBptFqMA4qJTiomFk1TZYajINKCQ4qZpaFWg1TrlcNxkGlBAcVM8taKwYYB5USHFTMrJbO/OID/ORn72T+PTdfuCDTYcoOKiU4qJhZvdRqyf4s1iBzUCnBQcXMGkGtAky1msgcVEpwUDGzRlPLlZTHG2RGCyqZ7lEvaamkXkk7JHUXOT5V0tp0fJOk2QXHVqX0XklLxrqmpDnpGjvSNQ/P8t7MzLLw4upl7EyvrM3uXs81Pduqes3MgoqkNuDLwMeA+cBFkuaPyHYJsDciTgFuAm5I584HVgCnAUuBr0hqG+OaNwA3pWvtTdc2M2taO2sQYG5/9OWqBpYsaypnADsi4oWIeAe4CzhvRJ7zgG+k9/cAH5WklH5XRLwdES8CO9L1il4znfORdA3SNZdnd2tmZrWVZYC5c9MrVbtWlqsUdwKFJd0FnFkqT0QckPQmcExKf3TEufmhC8WueQywLyIOFMk/jKRLgUsBZs2aVdkdmZk1gGqvpDxYxb71Sbf0fUTcAtwCuY76OhfHzGxCqhFg2qRqFSfToNIHnFjw+YSUVizPLklTgKOB18c4t1j668A0SVNSbaXYd5mZtbTCAPMrn/snfvr2YFnnXXTmiWNnKlOWQeUxYK6kOeR+wK8APjUizzrgYuAR4AJgY0SEpHXAtyTdCMwE5gI/ILcj5yHXTOc8lK5xV7rmdzO8NzOzhvbU55cO+1yqFlPtBSozCyqpj+RyYAPQBtwWEdslXQdsjoh1wK3ANyXtAN4gFyRI+e4GngEOAJdFxCBAsWumr/xz4C5JXwC2pGubmRm1WxvMkx89+dHMrCJ1m/xoZmaTi4OKmZlVjYOKmZlVjYOKmZlVzaTuqJe0B3hpnKe/D/i3KhanGfieJwff8+QwkXt+f0QcW+zApA4qEyFpc6nRD63K9zw5+J4nh6zu2c1fZmZWNQ4qZmZWNQ4q43dLvQtQB77nycH3PDlkcs/uUzEzs6pxTcXMzKrGQcXMzKrGQWUcJC2V1Ctph6TuepdnvCSdKOkhSc9I2i7pT1P6DEkPSPpR+nN6Spekv0n3/ZSkDxZc6+KU/0eSLq7XPZVLUpukLZLuS5/nSNqU7m2tpMNT+tT0eUc6PrvgGqtSeq+kJXW6lbJImibpHknPSXpW0lmt/pwlXZn+XT8t6U5JR7Tac5Z0m6TXJD1dkFa15yrpVyVtS+f8jVTGbl4R4VcFL3JL7j8PnAQcDjwJzK93ucZ5L8cDH0zv3wv8EJgPfAnoTundwA3p/bnA98jta7MI2JTSZwAvpD+np/fT631/Y9z7VcC3gPvS57uBFen93wF/nN7/CfB36f0KYG16Pz89+6nAnPRvoq3e9zXK/X4D+KP0/nBgWis/Z3Lbib8IdBQ83z9otecM/DrwQeDpgrSqPVdy+1gtSud8D/jYmGWq919Ks72As4ANBZ9XAavqXa4q3dt3gXOAXuD4lHY80Jve/z1wUUH+3nT8IuDvC9KH5Wu0F7mdQR8EPgLcl/7D/BswZeQzJrd3z1np/ZSUTyOfe2G+RnuR21H1RdLAnJHPrxWfcwoqr6QflFPSc17Sis8ZmD0iqFTluaZjzxWkD8tX6uXmr8rl/7Hm7UppTS1V9xcCm4DjImJ3OvQqcFx6X+rem+3v5GbgvwAH0+djgH2R24oahpd/6N7S8TdT/ma65znAHuAfUpPf/5R0FC38nCOiD/gr4GVgN7nn9jit/ZzzqvVcO9P7kemjclAxJL0H+A5wRUT8tPBY5H5FaZlx55J+C3gtIh6vd1lqaAq5JpKvRsRC4C1yzSJDWvA5TwfOIxdQZwJHAUtHPakF1eO5OqhUrg84seDzCSmtKUlqJxdQ7oiIe1PyTyQdn44fD7yW0kvdezP9nSwGPiFpJ3AXuSaw/w5Mk5TfXruw/EP3lo4fDbxOc93zLmBXRGxKn+8hF2Ra+Tn/BvBiROyJiAHgXnLPvpWfc161nmtfej8yfVQOKpV7DJibRpEcTq5Tb12dyzQuaSTHrcCzEXFjwaF1QH4EyMXk+lry6b+fRpEsAt5M1ewNwG9Kmp5+Q/zNlNZwImJVRJwQEbPJPbuNEfFp4CHggpRt5D3n/y4uSPkjpa9Io4bmAHPJdWo2nIh4FXhF0ryU9FHgGVr4OZNr9lok6cj07zx/zy37nAtU5bmmYz+VtCj9Hf5+wbVKq3cnUzO+yI2i+CG5kSBX17s8E7iPD5GrGj8FbE2vc8m1JT8I/Aj4PjAj5Rfw5XTf24Cugmv9B2BHev1hve+tzPv/MO+O/jqJ3A+LHcC3gakp/Yj0eUc6flLB+Venv4teyhgVU+d7XQBsTs+6h9won5Z+zsDngeeAp4FvkhvB1VLPGbiTXJ/RALka6SXVfK5AV/r7ex74W0YM9ij28jItZmZWNW7+MjOzqnFQMTOzqnFQMTOzqnFQMTOzqnFQMTOzqnFQMTOzqnFQMTOzqvn/8e7g7M0riKYAAAAASUVORK5CYII=\n"
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "func = partial(marcaTempo(listaTeste.insereValor), posicao=-1)\n",
    "benchmark(func, pulaImpressao=True)\n",
    "func = partial(marcaTempo(listaTeste.removerValor), posicao=-1)\n",
    "benchmarkRemocao(func)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Extremamente lento. Mas há uma solução.\n",
    "\n",
    "Uma estrutura de dados diferente, agora duplamente encadeada.\n",
    "\n",
    "## Deque\n",
    "\n",
    "O deque corrige este problema da lista, colocando referências também para os elementos anteriores, e não somente para os elementos posteriores.\n",
    "\n",
    "Isto permite remoção rápida dos elementos em ambas as extremidades."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "outputs": [],
   "source": [
    "class ElementoDeque():\n",
    "    def __init__(self, valorInicial):\n",
    "        # Cria um elemento de deque\n",
    "        # contendo o valor enfileirado\n",
    "        self.valor = valorInicial\n",
    "        # e a referência para o elemento posterior a ele no deque\n",
    "        self.proximo = None\n",
    "        # e a referência para o elemento anterior a ele no deque\n",
    "        self.anterior = None\n",
    "\n",
    "class Deque():\n",
    "    def __init__(self):\n",
    "        # Cria um deque vazia\n",
    "        self.primeiroElementoDeque = None\n",
    "        self.ultimoElementoDeque = None\n",
    "\n",
    "    def buscaElementoPosicao(self, posicao):\n",
    "        # Procure o elemento atualmente na posição\n",
    "        elementoPosicao = self.primeiroElementoDeque\n",
    "        posicaoBuscada = posicao\n",
    "        while posicaoBuscada > 0:\n",
    "            if elementoPosicao is None:\n",
    "                raise Exception(f\"Posição não existente no deque: {posicao}\")\n",
    "            elementoPosicao = elementoPosicao.proximo\n",
    "            posicaoBuscada -= 1\n",
    "        return elementoPosicao\n",
    "\n",
    "    def insereNovoElemento(self, novoElemento, elementoPosicao):\n",
    "        # Salva a referência para o elemento na\n",
    "        # posição como próximo do novo elemento\n",
    "        #\n",
    "        #            novoElemento\n",
    "        #         anterior  proximo\n",
    "        #                   |\n",
    "        #                   v\n",
    "        # | posicao-1 |  posicao  | posicao+1\n",
    "        # | proximo-> | proximo-> | proximo->\n",
    "        # | <-anterior|<-anterior |<-anterior\n",
    "        novoElemento.proximo = elementoPosicao\n",
    "\n",
    "        # Salva a referência para o elemento anterior\n",
    "        # ao da posição como anterior do novo elemento\n",
    "        #\n",
    "        #            novoElemento\n",
    "        #         anterior  proximo\n",
    "        #           |       |\n",
    "        #           v       v\n",
    "        # | posicao-1 |  posicao  | posicao+1\n",
    "        # | proximo-> | proximo-> | proximo->\n",
    "        # | <-anterior|<-anterior |<-anterior\n",
    "        novoElemento.anterior = elementoPosicao.anterior\n",
    "\n",
    "        # Atualiza referencia do elemento posterior do elemento\n",
    "        # anterior para o novo elemento\n",
    "        #\n",
    "        #            novoElemento\n",
    "        #     anterior  ^    proximo\n",
    "        #           |   |    |\n",
    "        #           v   |    v\n",
    "        # | posicao-1   |    posicao    | posicao+1\n",
    "        # | proximo-----^    proximo->  | proximo->\n",
    "        # | <-anterior       <-anterior |<-anterior\n",
    "        # Salva a referência para o elemento anterior ao movido\n",
    "        if elementoPosicao.anterior is not None:\n",
    "            elementoPosicao.anterior.proximo = novoElemento\n",
    "\n",
    "        # Atualiza referencia do elemento anterior do elemento\n",
    "        # na posição para o novo elemento\n",
    "        #\n",
    "        #            novoElemento\n",
    "        #     anterior  ^ ^  proximo\n",
    "        #           |   | |   |\n",
    "        #           v   | |   v\n",
    "        # | posicao-1   | |   posicao    | posicao+1\n",
    "        # | proximo-----^ |   proximo->  | proximo->\n",
    "        # | <-anterior    ^----anterior  |<-anterior\n",
    "        elementoPosicao.anterior = novoElemento\n",
    "\n",
    "        if elementoPosicao == self.primeiroElementoDeque:\n",
    "            self.primeiroElementoDeque = self.primeiroElementoDeque.anterior\n",
    "\n",
    "    def insereValor(self, valor, posicao=0):\n",
    "        # Cria um elemento para o deque\n",
    "        novoElementoDeque = ElementoDeque(valorInicial=valor)\n",
    "\n",
    "        # E a posição de inserção seja a primeira posição\n",
    "        if self.primeiroElementoDeque is None:\n",
    "            self.primeiroElementoDeque = novoElementoDeque\n",
    "            self.ultimoElementoDeque = self.primeiroElementoDeque\n",
    "        # Se a deque não estiver vazia\n",
    "        else:\n",
    "            if posicao == 0:\n",
    "                novoElementoDeque.proximo = self.primeiroElementoDeque\n",
    "                self.primeiroElementoDeque.anterior = novoElementoDeque\n",
    "                self.primeiroElementoDeque = novoElementoDeque\n",
    "            elif posicao == -1:\n",
    "                self.ultimoElementoDeque.proximo = novoElementoDeque\n",
    "                novoElementoDeque.anterior = self.ultimoElementoDeque\n",
    "                self.ultimoElementoDeque = novoElementoDeque\n",
    "            else:\n",
    "                # Busca elemento anterior a posicao\n",
    "                #                  v\n",
    "                # | posicao-1 |  posicao  | posicao+1\n",
    "                # | proximo-> | proximo-> | proximo->\n",
    "                #\n",
    "                elementoPosicao = self.buscaElementoPosicao(posicao) if posicao > 0 else self.primeiroElementoDeque\n",
    "\n",
    "                # Reorganizando\n",
    "                #                novoElemento\n",
    "                #                    v\n",
    "                # | posicao-1  | posicao    | posicao+1 | posicao+2\n",
    "                # | proximo->  | proximo->  | proximo-> | proximo->\n",
    "                # | <-anterior | <-anterior |<-anterior |<-anterior\n",
    "                self.insereNovoElemento(novoElementoDeque, elementoPosicao)\n",
    "\n",
    "    def removerValor(self, posicao=0):\n",
    "        if self.primeiroElementoDeque is None or self.ultimoElementoDeque is None:\n",
    "            return None\n",
    "        else:\n",
    "            # inicio el0 | el1 | el2 | ... | eln | fim el-1\n",
    "            if posicao == 0:\n",
    "                elementoPosicao = self.primeiroElementoDeque\n",
    "\n",
    "                # Se estivermos tirando um elemento que seja o primeiro\n",
    "                #   primeiro    el removido   ultimo\n",
    "                # | posicao    | posicao+1  | posicao+2\n",
    "                # | proximo->  | proximo->  | proximo->\n",
    "                # | <-anterior | <-anterior |<-anterior\n",
    "                self.primeiroElementoDeque = elementoPosicao.proximo\n",
    "                #  el removido    primeiro     ultimo\n",
    "                # | posicao    | posicao+1  | posicao+2\n",
    "                # | proximo->  | proximo->  | proximo->\n",
    "                # | <-anterior | <-anterior |<-anterior\n",
    "                # Se havia de fato um valor na posicao+1, não era um None,\n",
    "                # precisamos arrumar a referência para o elemento anterior removido\n",
    "                if self.primeiroElementoDeque:\n",
    "                    self.primeiroElementoDeque.anterior = None\n",
    "                else:\n",
    "                    self.ultimoElementoDeque = None\n",
    "            elif posicao == -1:\n",
    "                elementoPosicao = self.ultimoElementoDeque\n",
    "\n",
    "                # Se estivermos tirando um elemento que seja o último\n",
    "                #   primeiro                  ultimo\n",
    "                # | posicao-2  | posicao-1  | posicao\n",
    "                # | proximo->  | proximo->  | proximo->\n",
    "                # | <-anterior | <-anterior |<-anterior\n",
    "                # Primeiro atualizamos a referencia para o último elemento\n",
    "                self.ultimoElementoDeque = elementoPosicao.anterior\n",
    "\n",
    "                #   primeiro     ultimo        el removido\n",
    "                # | posicao-2  | posicao-1  | posicao\n",
    "                # | proximo->  | proximo->None| proximo->\n",
    "                # | <-anterior | <-anterior |<-anterior\n",
    "                # Em seguida removemos a referência para o próximo elemento\n",
    "                if self.ultimoElementoDeque:\n",
    "                    self.ultimoElementoDeque.proximo = None\n",
    "                else:\n",
    "                    self.primeiroElementoDeque = None\n",
    "            else:\n",
    "                elementoPosicao = self.buscaElementoPosicao(posicao)\n",
    "\n",
    "                if posicao != -1 and elementoPosicao == self.ultimoElementoDeque:\n",
    "                    return self.removerValor(-1)\n",
    "\n",
    "                # Se estivermos tirando um elemento que não seja o primeiro\n",
    "                #   primeiro                  ultimo\n",
    "                # | posicao-1  | posicao    | posicao+1\n",
    "                # | proximo->  | proximo->  | proximo->\n",
    "                # | <-anterior | <-anterior |<-anterior\n",
    "                elementoPosicao.anterior.proximo = elementoPosicao.proximo\n",
    "                #   primeiro    el removido   ultimo\n",
    "                # | posicao-1  | posicao    | posicao+1\n",
    "                # | proximo---------------->| proximo->\n",
    "                # | <-anterior | <-anterior |<-anterior\n",
    "\n",
    "                # Se estivermos tirando um elemento que não seja o primeiro\n",
    "                #   primeiro                  ultimo\n",
    "                # | posicao-1  | posicao    | posicao+1\n",
    "                # | proximo---------------->| proximo->\n",
    "                # | <-anterior | <-anterior |<-anterior\n",
    "                # Precisamos arrumar a referência anterior do próximo elemento\n",
    "                elementoPosicao.proximo.anterior = elementoPosicao.anterior\n",
    "                #   primeiro     el removido  ultimo\n",
    "                # | posicao-1  | posicao    | posicao+1\n",
    "                # | proximo---------------->| proximo->\n",
    "                # | <-anterior |<-------------anterior\n",
    "\n",
    "            if self.ultimoElementoDeque is None or self.primeiroElementoDeque is None:\n",
    "                self.primeiroElementoDeque = self.ultimoElementoDeque = None\n",
    "            return elementoPosicao.valor\n",
    "\n",
    "    def push_left(self, valor):\n",
    "        self.insereValor(valor, 0)\n",
    "    def push_right(self, valor):\n",
    "        self.insereValor(valor, -1)\n",
    "    def pop_left(self):\n",
    "        return self.removerValor(0)\n",
    "    def pop_right(self):\n",
    "        return self.removerValor(-1)\n",
    "deque = Deque()\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Agora precisamos testar este deque. Primeiro testaremos se podemos acrescentar e remover elementos por ambos os lados corretamente"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Saida pela esquerda: [3, 1, 2, 4], esperando [3,1,2,4]\n",
      "Saida pela direita: [4, 2, 1, 3], esperando [4,2,1,3]\n",
      "São o inverso? True\n"
     ]
    }
   ],
   "source": [
    "deque.push_left(1)\n",
    "deque.push_right(2)\n",
    "deque.push_left(3)\n",
    "deque.push_right(4)\n",
    "saida_esquerda = [deque.pop_left() for _ in range(4)]\n",
    "deque.push_left(1)\n",
    "deque.push_right(2)\n",
    "deque.push_left(3)\n",
    "deque.push_right(4)\n",
    "saida_direita = [deque.pop_right() for _ in range(4)]\n",
    "print(f\"Saida pela esquerda: {saida_esquerda}, esperando [3,1,2,4]\")\n",
    "print(f\"Saida pela direita: {saida_direita}, esperando [4,2,1,3]\")\n",
    "print(\"São o inverso?\", saida_esquerda == list(reversed(saida_direita)))"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Em seguida, testaremos o que acontece se tentarmos tirar mais elementos que os contidos"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 1, 2, 4, None]\n",
      "[4, 2, 1, 3, None]\n"
     ]
    }
   ],
   "source": [
    "deque.push_left(1)\n",
    "deque.push_right(2)\n",
    "deque.push_left(3)\n",
    "deque.push_right(4)\n",
    "print([deque.pop_left() for _ in range(5)])\n",
    "deque.push_left(1)\n",
    "deque.push_right(2)\n",
    "deque.push_left(3)\n",
    "deque.push_right(4)\n",
    "print([deque.pop_right() for _ in range(5)])"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Finalmente, se conseguimos inserir e remover elementos de qualquer posição do deque"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "2\n",
      "4\n",
      "3\n",
      "None\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "deque.push_right(2) # [2]\n",
    "deque.push_left(3) # [3, 2]\n",
    "deque.insereValor(5, 1) # [3, 5, 2]\n",
    "deque.push_right(4)  # [3, 5, 2, 4]\n",
    "print(deque.removerValor(1))  # [3, 2, 4] -> return 5\n",
    "print(deque.removerValor(1))  # [3, 4] -> return 2\n",
    "print(deque.removerValor(-1))  # [3] -> return 4\n",
    "print(deque.removerValor(0))  # [] -> return 3\n",
    "print(deque.removerValor(0))  # [] -> return None\n",
    "print(deque.removerValor(-1))  # [] -> return None"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Mas onde podemos utilizar estes deques? Vai depender muito do caso de uso da sua aplicação.\n",
    "\n",
    "Em simuladores de eventos discretos, é bastante comum agendarmos operações que ocorrerão em diferentes instantes de tempo."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Executando Evento 0\n",
      "Iniciando execução de eventos\n",
      "Evento 0 não retornou nenhum valor. Prosseguindo para o próximo evento\n",
      "Finda a execução do Evento 0\n",
      "==================================\n",
      "Executando Evento 1\n",
      "Evento 2\n",
      "Evento 1 não retornou nenhum valor. Prosseguindo para o próximo evento\n",
      "Finda a execução do Evento 1\n",
      "==================================\n",
      "Executando Evento 2\n",
      "Requisitando arquivos do site http://site0.com\n",
      "Evento 2 não retornou error. Agendando seu callbackFracasso sem prioridade (inicio do deque)\n",
      "Finda a execução do Evento 2\n",
      "==================================\n",
      "Executando Evento 3\n",
      "Requisitando arquivos do site http://site1.com\n",
      "Evento 3 não retornou error. Agendando seu callbackFracasso sem prioridade (inicio do deque)\n",
      "Finda a execução do Evento 3\n",
      "==================================\n",
      "Executando Evento 4\n",
      "Requisitando arquivos do site http://site2.com\n",
      "Evento 4 retornou error. Agendando seu callbackFracasso com prioridade (fim do deque)\n",
      "Finda a execução do Evento 4\n",
      "==================================\n",
      "Executando Evento 8\n",
      "Requisição de arquivos do site http://site2.com FALHOU\n",
      "Evento 8 não retornou nenhum valor. Prosseguindo para o próximo evento\n",
      "Finda a execução do Evento 8\n",
      "==================================\n",
      "Executando Evento 5\n",
      "Requisitando arquivos do site http://site3.com\n",
      "Evento 5 retornou error. Agendando seu callbackFracasso com prioridade (fim do deque)\n",
      "Finda a execução do Evento 5\n",
      "==================================\n",
      "Executando Evento 9\n",
      "Requisição de arquivos do site http://site3.com FALHOU\n",
      "Evento 9 não retornou nenhum valor. Prosseguindo para o próximo evento\n",
      "Finda a execução do Evento 9\n",
      "==================================\n",
      "Executando Evento 6\n",
      "Requisição arquivos do site http://site0.com FOI BEM-SUCEDIDA\n",
      "Evento 6 não retornou nenhum valor. Prosseguindo para o próximo evento\n",
      "Finda a execução do Evento 6\n",
      "==================================\n",
      "Executando Evento 7\n",
      "Requisição arquivos do site http://site1.com FOI BEM-SUCEDIDA\n",
      "Evento 7 não retornou nenhum valor. Prosseguindo para o próximo evento\n",
      "Finda a execução do Evento 7\n",
      "==================================\n",
      "Fim da execução\n"
     ]
    }
   ],
   "source": [
    "dequeEventos = Deque()\n",
    "\n",
    "class Evento:\n",
    "    CONTADOR_EVENTOS = 0\n",
    "    def __init__(self, tarefaDoEvento, tarefaCasoSucesso=None, tarefaCasoFracasso=None):\n",
    "        self.id = Evento.CONTADOR_EVENTOS\n",
    "        Evento.CONTADOR_EVENTOS += 1\n",
    "        self.tarefaDoEvento = tarefaDoEvento\n",
    "        self.callbackSucesso = tarefaCasoSucesso\n",
    "        self.callbackFracasso = tarefaCasoFracasso\n",
    "    def __str__(self):\n",
    "        return f\"Evento {self.id}\"\n",
    "\n",
    "def tarefa_inicial():\n",
    "    print(\"Iniciando execução de eventos\")\n",
    "\n",
    "def evento2():\n",
    "    print(\"Evento 2\")\n",
    "\n",
    "from random import randint\n",
    "from functools import partial\n",
    "\n",
    "def requisicaoRede(id=0):\n",
    "    print(f\"Requisitando arquivos do site http://site{id}.com\")\n",
    "    return randint(0, 1) # requisições de rede tem chances de falhar\n",
    "\n",
    "def requisicaoFalhou(id=0):\n",
    "    print(f\"Requisição de arquivos do site http://site{id}.com FALHOU\")\n",
    "\n",
    "def requisicaoSucesso(id=0):\n",
    "    print(f\"Requisição arquivos do site http://site{id}.com FOI BEM-SUCEDIDA\")\n",
    "\n",
    "dequeEventos.push_left(Evento(tarefa_inicial))\n",
    "dequeEventos.push_left(Evento(evento2))\n",
    "for req in range(4):\n",
    "    dequeEventos.push_left(Evento(partial(requisicaoRede, req),\n",
    "                                  partial(requisicaoSucesso, req),\n",
    "                                  partial(requisicaoFalhou, req)))\n",
    "\n",
    "# Deque contém\n",
    "# \n",
    "#                   | Evento 5             | Evento 4             | Evento 3             | Evento 2             | Evento 1     | Evento 0         |\n",
    "# tarefaDoEvento    | requisicaoRede(4)    | requisicaoRede(3)    | requisicaoRede(2)    | requisicaoRede(1)    | evento2()    | tarefa_inicial() |\n",
    "# callbackSucesso   | requisicaoSucesso(4) | requisicaoSucesso(3) | requisicaoSucesso(2) | requisicaoSucesso(1) | None         | None             |\n",
    "# callbackFracasso  | requisicaoFalhou(4)  | requisicaoFalhou(3)  | requisicaoFalhou(2)  | requisicaoFalhou(1)  | None         | None             |\n",
    "\n",
    "# O laço abaixo consumirá os elementos do final do deque (evento 0)\n",
    "\n",
    "# Tempo = 0\n",
    "# Deque\n",
    "#                   | Evento 5             | Evento 4             | Evento 3             | Evento 2             | Evento 1\n",
    "# tarefaDoEvento    | requisicaoRede(4)    | requisicaoRede(3)    | requisicaoRede(2)    | requisicaoRede(1)    | evento2()\n",
    "# callbackSucesso   | requisicaoSucesso(4) | requisicaoSucesso(3) | requisicaoSucesso(2) | requisicaoSucesso(1) | None\n",
    "# callbackFracasso  | requisicaoFalhou(4)  | requisicaoFalhou(3)  | requisicaoFalhou(2)  | requisicaoFalhou(1)  | None\n",
    "#\n",
    "# Executa Evento 0\n",
    "# Deque inalterado\n",
    "#\n",
    "###########################################################################################\n",
    "# Tempo = 1\n",
    "# Deque\n",
    "#                   | Evento 5             | Evento 4             | Evento 3             | Evento 2\n",
    "# tarefaDoEvento    | requisicaoRede(4)    | requisicaoRede(3)    | requisicaoRede(2)    | requisicaoRede(1)\n",
    "# callbackSucesso   | requisicaoSucesso(4) | requisicaoSucesso(3) | requisicaoSucesso(2) | requisicaoSucesso(1)\n",
    "# callbackFracasso  | requisicaoFalhou(4)  | requisicaoFalhou(3)  | requisicaoFalhou(2)  | requisicaoFalhou(1)\n",
    "#\n",
    "# Executa Evento 1\n",
    "# Deque inalterado\n",
    "#\n",
    "###########################################################################################\n",
    "# Tempo = 2\n",
    "# Deque\n",
    "#                   | Evento 5             | Evento 4             | Evento 3\n",
    "# tarefaDoEvento    | requisicaoRede(4)    | requisicaoRede(3)    | requisicaoRede(2)\n",
    "# callbackSucesso   | requisicaoSucesso(4) | requisicaoSucesso(3) | requisicaoSucesso(2)\n",
    "# callbackFracasso  | requisicaoFalhou(4)  | requisicaoFalhou(3)  | requisicaoFalhou(2)\n",
    "#\n",
    "# Executa Evento 2\n",
    "#\n",
    "# Caso o Evento 2 retorne VERDADEIRO\n",
    "# Deque\n",
    "#                   | Evento 6             | Evento 5             | Evento 4             | Evento 3\n",
    "# tarefaDoEvento    | requisicaoSucesso(1) | requisicaoRede(4)    | requisicaoRede(3)    | requisicaoRede(2)\n",
    "# callbackSucesso   | None                 | requisicaoSucesso(4) | requisicaoSucesso(3) | requisicaoSucesso(2)\n",
    "# callbackFracasso  | None                 | requisicaoFalhou(4)  | requisicaoFalhou(3)  | requisicaoFalhou(2)\n",
    "#\n",
    "# Caso o Evento 2 retorne FALSO\n",
    "# Deque\n",
    "#                   | Evento 5             | Evento 4             | Evento 3             | Evento 6\n",
    "# tarefaDoEvento    | requisicaoRede(4)    | requisicaoRede(3)    | requisicaoRede(2)    | requisicaoFalhou(1)\n",
    "# callbackSucesso   | requisicaoSucesso(4) | requisicaoSucesso(3) | requisicaoSucesso(2) | None\n",
    "# callbackFracasso  | requisicaoFalhou(4)  | requisicaoFalhou(3)  | requisicaoFalhou(2)  | None\n",
    "\n",
    "\n",
    "# Executa eventos\n",
    "while True:\n",
    "    # Pega evento mais prioritário\n",
    "    evento = dequeEventos.pop_right()\n",
    "    # Se não existir, termina execução\n",
    "    if evento is None:\n",
    "        print(\"Fim da execução\")\n",
    "        break # quebra laço infinito\n",
    "    # Caso exista, executa sua tarefa\n",
    "    print(f\"Executando {evento}\")\n",
    "    # Funcionamento normal: agendar um novo evento\n",
    "    resultado = evento.tarefaDoEvento()\n",
    "    if resultado is None:\n",
    "        print(f\"{evento} não retornou nenhum valor. Prosseguindo para o próximo evento\")\n",
    "        pass # continua para próximo evento\n",
    "    elif resultado == 1:\n",
    "        print(f\"{evento} retornou error. Agendando seu callbackFracasso com prioridade (fim do deque)\")\n",
    "        # Funcionamento inesperado, precisa prejudicar algum evento já no deque\n",
    "        dequeEventos.push_right(Evento(evento.callbackFracasso))\n",
    "    else:\n",
    "        print(f\"{evento} não retornou error. Agendando seu callbackFracasso sem prioridade (inicio do deque)\")\n",
    "        dequeEventos.push_left(Evento(evento.callbackSucesso))\n",
    "\n",
    "    print(f\"Finda a execução do {evento}\")\n",
    "    print(\"==================================\")"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}