.. -*- coding: utf-8 -*- Pote de ideias ============== Tratamos de projeto e análise de algoritmos tendo como pretexto principalmente, mas não exclusivo, o problema de ordenação. Ao longo do caminho vimos várias técnicas para a nosso **pote de ideias**: * recursão: ``hanoi()``; * memorização: ``fibonacci()``, ``binomial()``; * busca binária: inserção binária; * algoritmos dinâmicos: ordenação por inserção; * divisão e conquista: ``mergesort()`` e ``quicksort()``; * pré-processamentos: ``heapsort()``; * organização de informação: pilhas, dicionários, heaps; * ... Expressamos o consumo de tempo e espaço através de notação assintótica. O resultado de alguns algoritmos, em termos de consumo de tempo foram .. math:: \begin{array}{lcc} \text{algoritmo} & \text{melhor caso} & \text{pior caso} \\ \hline \text{inserção} & \mathtt{\textup{O}(n)} & \mathtt{\textup{O}(n^2)} \\ \text{inserção binária} & \mathtt{\textup{O}(n \lg n)} & \mathtt{\textup{O}(n^2)} \\ \text{seleção} & \mathtt{\textup{O}(n^2)} & \mathtt{\textup{O}(n^2)} \\ \text{Mergesort} & \mathtt{\textup{O}(n \lg n)} & \mathtt{\textup{O}(n \lg n)} \\ \text{Quicksort} & \mathtt{\textup{O}(n \lg n)} & \mathtt{\textup{O}(n^2)} \\ \text{Heapsort} & \mathtt{\textup{O}(n \lg n)} & \mathtt{\textup{O}(n^2)} \\ \hline \end{array} Fizemos análises experimentais para treinar a validação das nossas contas, validação dos nossos *modelos*, estimando os tempos gastos pelas funções. Objetivos de aprendizagem ------------------------- O objetivo é, através de um problema simples, discutirmos especificamente sobre o consumo de tempo de operações sobre os objetos das classes nativas ``list`` e ``dict``. Há tabelas com o consumo de tempo dessas classes de objetos no final dessas notas. Várias ideias que estão no nosso pote serão trazidas para a mesa. Faremos ainda mais análise experimentais para validar, ou não, as nossas conclusões. Trabalharemos ainda com a função ``sorted()`` e o módulo para busca binária ``bisect``. 3SUM ---- Passamos a considerar o seguinte problema **Problema 3SUM:** dada uma lista de número inteiros **distintos**, determinar o número de trios que somam zero. Por exemplo, para a lista ``[30, -30, -20, -10, 40, 0, 10, 15]`` temos que há 4 trios que somam zero: :: 30 -30 0 30 -20 -10 -30 -10 40 -10 0 10 +----+----+----+----+----+----+----+----+ | 30 |-30 |-20 |-10 | 40 | 0 | 10 | 15 | +----+----+----+----+----+----+----+----+ Esse é o conhecido `3SUM problem `_ e, apesar de parecer artificial, está relacionado a várias tarefas fundamentais em geometria computacional. Segundo a Wikipedia O consumo de tempo do algoritmo mais eficiente para o 3SUM é :math:`\mathtt{\textup{O}(n^{2}(\lg \lg n)^{\textup{O}(1)}/{\log ^{2}n})}` em que :math:`\mathtt{n}` é o número de elementos na lista. Assintoticamente, para listas com muitos elementos, esse algoritmo bate qualquer solução que tenha consumo de tempo proporcional a :math:`\mathtt{n^2}`. A hipótese de que os elementos da lista são todos diferentes é **simplificadora** já que, de fato, simplifica o código de algumas soluções. Isso ajudará a mantermos a nossa atenção nos pontos mais relevantes dos algoritmos e técnicas. Consideraremos quatro soluções para esse problema. Cada uma com seu próprio potinho de ideias: * testa tudo; * ordenação e busca binária; * dicionários; * ordenação e ideias mistas de busca binária e de uma versão ``separe()`` do Quicksort. Tirando a solução que testa todos os trios possíveis, a outras três passam por um pré-processamento, dois envolvem ordenação e um a criação de um dicionário. |:thinking:| Testa tudo na força bruta ------------------------- A nossa primeira solução calcula a soma de todos os trios possíveis, sem repetições, e verifica se essa soma é zero. .. code:: python def testa_tudo(v): '''(list) -> int RECEBE uma lista v de inteiros distintos. RETORNA o número trios v[i], v[j] e v[k], com i < j < k tais que v[i] + v[j] + v[k] = 0. ''' conta = 0 n = len(v) for i in range(n): for j in range(i+1, n): for k in range(j+1, n): if v[i] + v[j] + v[k] == 0: # (*) conta += 1 return conta Simplesmente testamos :math:`\mathtt{v[i]+v[j]+v[k] = 0}` para todos indices válidos :math:`\mathtt{i < j < k}`. Por exemplo, .. raw:: html 
   +----+----+----+----+----+----+----+----+
       | 30 |-30 |-20 |-10 | 40 |  0 | 10 | 15 |
       +----+----+----+----+----+----+----+----+
          i    j                   k   

       +----+----+----+----+----+----+----+----+
       | 30 |-30 |-20 |-10 | 40 |  0 | 10 | 15 |
       +----+----+----+----+----+----+----+----+
          i         j   k

       +----+----+----+----+----+----+----+----+
       | 30 |-30 |-20 |-10 | 40 |  0 | 10 | 15 |
       +----+----+----+----+----+----+----+----+
          i             j     k

       +----+----+----+----+----+----+----+----+
       | 30 |-30 |-20 |-10 | 40 |  0 | 10 | 15 |
       +----+----+----+----+----+----+----+----+
                         i         j    k
O consumo de tempo da função ``testa_tudo()`` é proporcional ao número de execuções da linha ``(*)`` na qual o teste ``v[i] + v[j] + v[k] == 0`` é realizado. Podemos determinar a ordem de grandeza desse número: .. math:: \begin{align*} \sum_{i=0}^{\mathtt{n-3}} \sum_{\mathtt{j=i+1}}^{\mathtt{n-2}} \sum_{\mathtt{k=j+1}}^{\mathtt{n-1}} 1 & = \sum_{i=0}^{\mathtt{n-3}} \sum_{j=i+1}^{n-2} (\mathtt{n-j-1}) \\ & = \sum_{i=0}^{n-3} \mathtt{(n-i-1)(n-i-2)/2} \\ & \leq \sum_{i=0}^{\mathtt{n-3}} \mathtt{n^2/2} = \mathtt{\textup{O}(n^3)}. \end{align*} O consumo de tempo é portanto :math:`\mathtt{\textup{O}(n^3)}`. Vejamos alguns resultados experimentais que obtivemos: :: n testa_tudo cont 16 0.00 14 32 0.00 57 64 0.01 247 128 0.06 985 256 0.44 3829 512 4.01 16289 1024 33.37 65421 2048 275.14 264028 4096 2709.67 1040099 A coluna ``cont`` indica o número de trios que somam zero que foram encontrados. Vemos que à medida que o número de elementos na lista dobra, o tempo gasto parece que é multiplicado por oito. Esse comportamento confirma a nossa análise. O tempo gasto por funções que implementam algoritmos cúbicos é possivelmente multiplicado por oito a medida que o número de elementos na entrada dobra. Suponhamos que para executarmos ``testa_tudo(v)`` o tempo gasto seja de :math:`\mathtt{T(n)}` segundos em que :math:`\mathtt{n}` é o número de elementos da lista. O fato do consumo de tempo ser :math:`\mathtt{\textup{O}(n^3)}` sugere que :math:`\mathtt{T(n)}` pode ser aproximada por uma função da forma da forma :math:`\mathtt{cn^3}` para alguma constante :math:`\mathtt{c}`. Assim, se para :math:`\mathtt{T(n) = t}` segundos então .. math:: \begin{align*} \mathtt{T(2n)} & = \mathtt{c(2n)^3} \\ & = \mathtt{c2^3n^3} \\ & = \mathtt{2^3cn^3} \\ & = \mathtt{8cn^3} \\ & = \mathtt{8T(n)} \\ & = \mathtt{8 t} . \end{align*} Vemos que o tempo gasto pela função ``testa_tudo()`` para trabalhar com uma lista de 4096 elementos foi de :math:`\mathtt{2709.14}` segundos que corresponde a aproximadamente 45 minutos 15 segundos. |:woman_facepalming_tone2:| |:man_facepalming_medium_dark_skin_tone:| |:woman_facepalming_medium_dark_skin_tone:| |:man_facepalming_dark_skin_tone:| Quanto tempo a função gastaria para resolver o problema com uma lista de :math:`\mathtt{2^{17} = 131072}` inteiros? Vejamos ... Supondo que o tempo gasto pela função obedece a função :math:`\mathtt{T(n) = cn^3}` para alguma contante :math:`\mathtt{c}` teremos que .. math:: \begin{align*} \mathtt{T(131072)} & = \mathtt{c\, 131072^3} \\ & = \mathtt{32^3 \times c\, 4096^3} \\ & = \mathtt{32^3 \times T(4096)} \\ & \approx \mathtt{32768 \times 45} \\ & = \mathtt{1474560} \ \mbox{minutos}. \end{align*} Portanto, a resposta é aproximadamente :math:`\mathtt{1024}` dias. |:woman_facepalming_tone2:| |:man_facepalming_medium_dark_skin_tone:| |:woman_facepalming_medium_dark_skin_tone:| |:man_facepalming_dark_skin_tone:| Ordenação e busca binária ------------------------- A nossa próxima solução utilizará as seguintes funções auxiliares: * ``sorted()``: função para **ordenação** que consome tempo :math:`\mathtt{\textup{O}(n \lg n)}` e * ``bisect.bisect_left()``: função **busca binária** que consome tempo :math:`\mathtt{\textup{O}(\lg n)}`. Para a ordenação a função ``sorted()`` do Python **recebe** uma lista e **retorna** uma nova lista crescente com os elementos da lista original. Portanto, diferentemente do método ``sort()`` da classe ``list``, a função ``sorted()`` não é mutadora. A não mutabilidade de ``sorted()`` pode ser verificada através de um exemplo: .. code:: python In [1]: v = [30, -30, -20, 40, 0, 10, 15] In [2]: a = sorted(v) In [3]: v Out[3]: [30, -30, -20, 40, 0, 10, 15] In [4]: a Out[4]: [-30, -20, 0, 10, 15, 30, 40] In [5]: a[0] = -40 In [6]: a Out[6]: [-40, -20, 0, 10, 15, 30, 40] In [7]: v Out[7]: [30, -30, -20, 40, 0, 10, 15] Para busca binária usaremos o modulo `Lib/bisect.py `_ . .. code:: python In [8]: from bisect import bisect_left In [9]: a = [1, 1, 2, 2, 3] In [10]: bisect_left(a, 1) Out[10]: 0 In [11]: bisect_left(a, 1.5) Out[11]: 2 In [12]: bisect_left(a, 2) Out[12]: 2 In [13]: bisect_left(a, 2.5) Out[13]: 4 In [14]: bisect_left(a, 3.5) Out[14]: 5 Mais especificamente, usaremos a seguinte adaptação de ``index()`` da página do módulo ``bisect`` do Python: .. code:: python def index(v, x, e, d): '''(list, obj, int, int) -> int | None RECEBE uma lista v crescente, um valor x e inteiros e e d. RETORNA o menor inteiro i em range(e, d) tal que v[i] == x. Se x não ocorre em v a função retorna None. ''' i = bisect_left(v, x, e, d) if i != len(v) and v[i] == x: return i return None # raise ValueError A ideia do novo algoritmo é inicialmente, em um pré-processamento, ordenar a lista ``v``. **Pré-processar** significa organizar as coisas sem nos preocuparmos em resolver diretamente o problema, mas é claro, tendo a esperança de que ao final esse trabalho terá valido a pena. Foi isso que ocorreu no `heapsort()` e também é feito será feito aqui. :: +----+----+----+----+----+----+----+----+ | 30 |-30 |-20 |-10 | 40 | 0 | 10 | 15 | +----+----+----+----+----+----+----+----+ Préprocessamento: ordenação +----+----+----+----+----+----+----+----+ |-30 |-20 |-10 | 0 | 10 | 15 | 30 | 40 | +----+----+----+----+----+----+----+----+ Depois de feito esse pré-processamento o algoritmo é simples. Para cada :math:`\mathtt{i}` e :math:`\mathtt{j}`, com :math:`\mathtt{i < j}`, * calculamos a soma :math:`\mathtt{v[i]+v[j]}` * procuramos na lista ordenada o elemento :math:`\mathtt{-(v[i]+v[j])}` usando **busca binária**; * se o elemento é encontrado em uma posição :math:`\mathtt{k}` tal que :math:`\mathtt{i < j < k}`, bingo! Encontramos um **novo trio** de soma zero. A função que implementa essa ideia é a ``sorted_bb()`` especificada abaixo. Completar a função será deixado com um exercício. .. code:: python def sorted_bb(v): '''(list) -> int RECEBE uma lista `v` de inteiros distintos. RETORNA o número trios v[i], v[j] e v[k], com i < j < k tais que v[i] + v[j] + v[k] = 0. ''' conta = 0 n = len(v) # complete o código [...] return conta Como há cerca de :math:`\mathtt{\textup{O}(n^2)}` pares de valores para serem adicionados e para cada um destes devemos realizar uma busca binária na lista ``v``, uma implementação razoável da função ``sorted_bb()`` deve consumir tempo :math:`\mathtt{\textup{O}(n^2 \lg n)}`. Um ex-aluno de MAC0122 implementou a função ``sorted_bb()`` e obteve os seguintes resultados ao realizar testes experimentais: :: n sort-bb cont 16 0.00 14 32 0.00 57 64 0.00 247 128 0.01 985 256 0.03 3829 512 0.13 16289 1024 0.54 65421 2048 2.30 264028 4096 9.83 1040099 8192 46.77 4188640 16384 213.36 16744670 Parece bem melhor! O tempo gasto pela função ``sorted_bb()`` para trabalhar com uma lista de 4096 elementos foi de :math:`\mathtt{9.83}` segundos. |:thumbsup_tone3:| |:thumbsup_tone1:| |:thumbsup_tone5:| Para uma lista com 16384 o tempo gasto foi de :math:`\mathtt{213.36}` segundos que são aproximadamente :math:`\mathtt{3.5}` minutos. Quanto tempo a função gastaria para resolver o problema com uma lista de :math:`\mathtt{2^{17} = 131072}` inteiros? Supondo agora que o tempo gasto respeita a função :math:`\mathtt{T(n) = c \; n^2 \lg n}` para alguma constante :math:`\mathtt{c}` obtemos que .. math:: \begin{align*} \mathtt{T(131072)} & = \mathtt{c\, 131072^2 \lg 131072} \\ & = \mathtt{8^2 \times c\, 16384^2 \lg 131072} \\ & < \mathtt{8^2 \times c\, 16384^2 \lg 16384^{1.5}} \\ & = \mathtt{8^2 \times 1.5 \times c\, 16384^2 \lg 16384} \\ & = \mathtt{8^2 \times 1.5 \times 16384^2 T(16384)} \\ & \approx \mathtt{64 \times 3 \times 3.5} \\ & = \mathtt{336} \ \mbox{minutos} \end{align*} Bem, de 1024 dias reduzimos o tempo de espera para menos que :math:`\mathtt{6}` horas. |:thumbsup_tone3:| |:thumbsup_tone1:| |:thumbsup_tone5:| Será que conseguimos dimuir mais ainda? Dicionários ----------- A ideia agora é similar a da seção anterior com a diferença que trocaremos o papel da busca binária pelo uso de um dicionário. Inicialmente, em um pré-processamento, criaremos um dicionário ``d`` em que as chaves são os elementos em ``v`` e os valores são os índices em que os elementos se encontram. O resultado desse pré-processamento está ilustrado a seguir. :: +----+----+----+----+----+----+----+----+ v | 30 |-30 |-20 |-10 | 40 | 0 | 10 | 15 | +----+----+----+----+----+----+----+----+ 0 1 2 3 4 5 6 7 dicionário +----+----+----+----+----+----+----+----+ d | 30 |-30 |-20 |-10 | 40 | 0 | 10 | 15 | chave +----+----+----+----+----+----+----+----+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | valor +----+----+----+----+----+----+----+----+ Depois de feito esse pré-processamento o algoritmo agora é semelhante ao anterior. Para cada :math:`\mathtt{i}` e :math:`\mathtt{j}`, com :math:`\mathtt{i < j}`, * calculamos a soma :math:`\mathtt{v[i]+v[j]}`; * procuramos o elemento :math:`-(\mathtt{v[i]+v[j]})` no **dicionário**; * se esse elemento for encontrado em uma posição :math:`\mathtt{k}` tal que :math:`\mathtt{i < j < k}`, bingo! Encontramos um **novo** trio de soma zero. A condição :math:`\mathtt{k > j}`, como nas funções ``testa_tudo()`` e ``sorted_bb()``, garante que esse seja um *novo* trio de soma zero e já não tenha sido contabilizado. A função que implementa a ideia descrita acima é a ``conta_dict()``. Completar essa função será mais um exercício. .. code:: python def conta_dict(a): '''(list) -> int RECEBE uma lista v RETORNA o número trios v[i], v[j] e v[k], com i < j < k tais que v[i] + v[j] + v[k] = 0. ''' conta = 0 n = len(v) # complete o código [...] return conta O consumo de tempo esperado de cada busca no dicionário é constante, independe do número de elementos no dicionário. |:dizzy_face:| Essa é uma característica encantada |:mage_tone4:| de um dicionário. Escrevemos que esse consumo de tempo é :math:`\mathtt{\textup{O}(1)}`. Portanto, o consumo de tempo esperado da função ``conta_dict()`` é :math:`\mathtt{\textup{O}(n^2)}`. Uma ex-aluna de MAC0122 implementou a função ``conta_dict()``, realizou testes experimentais e obteve os seguintes resultados: :: n conta_dict cont 16 0.00 14 32 0.00 57 64 0.00 247 128 0.00 985 256 0.01 3829 512 0.04 16289 1024 0.15 65421 2048 0.65 264028 4096 2.72 1040099 8192 11.31 4188640 16384 49.84 16744670 <<<< 32768 207.76 67207738 65536 972.98 267403147 Melhorou ainda mais! O tempo gasto pela função ``conta_dict()`` para trabalhar com uma lista de 16384 elementos foi de :math:`\mathtt{49.84}` segundos. |:raised_hands_tone2:| |:raised_hands_tone5:| |:raised_hands_tone4:| digamos :math:`\mathtt{50}` segundos. A função ``sorted_bb()`` havia gasto :math:`\mathtt{3.5}` minutos. A pergunta agora é, novamente, Quanto tempo a função gastaria para para resolver o problema com uma lista de :math:`\mathtt{2^{17} = 131072}` inteiros? Suponhamos agora que o tempo gasto esperado respeita a função :math:`\mathtt{T(n) = c \; n^2}` em que :math:`\mathtt{c}` é uma constante. Obtemos que .. math:: \begin{align*} \mathtt{T(131072)} & = \mathtt{c\, 131072^2} \\ & = \mathtt{8^2 \times c\, 16384^2} \\ & < \mathtt{64 \times 50} \nonumber \\ & \approx \mathtt{3200} \ \mbox{segundos} \\ \end{align*} Ops! Menos que :math:`\mathtt{55}` minutos. |:first_place:| O melhor até agora era umas 6 horas. Vamos investigar mais. Quanto tempo a função gastaria para resolver o problema com uma lista de :math:`\mathtt{2^{16}=65536}` inteiros? Mais uma vez, suponhamos que o tempo gasto esperado respeite :math:`\mathtt{T(n) = c \; n^2}` em que :math:`\mathtt{c}` é uma constante. Temos que .. math:: \begin{align*} \mathtt{T(65536)} & = \mathtt{c\, 65536^2} \\ & = \mathtt{4^2 \times c\, 16384^2} \\ & \approx \mathtt{16 \times 50} \\ & = \mathtt{800} \ \mbox{segundos} \end{align*} *Resposta*: menos que :math:`\mathtt{14}` minutos! |:first_place:| Mágica ------ Desta vez a ideia é um pouco mais envolvente. Continuamos a ordenar a lista em uma fase de pré-processamento. :: +----+----+----+----+----+----+----+----+ | 30 |-30 |-20 |-10 | 40 | 0 | 10 | 15 | +----+----+----+----+----+----+----+----+ Préprocessamento: ordenação +----+----+----+----+----+----+----+----+ |-30 |-20 |-10 | 0 | 10 | 15 | 30 | 40 | +----+----+----+----+----+----+----+----+ Depois de termos ordenado a lista, fixaremos um índice :math:`\mathtt{i}` e procuramos índices :math:`\mathtt{e}` e :math:`\mathtt{d}` tais que :math:`\mathtt{v[i]+v[e]+v[d] = 0}`. A procura por :math:`\mathtt{v[e]}` e :math:`\mathtt{v[d]}` tais que :math:`\mathtt{v[i] = -(v[e]+v[d])}` combina aspectos da busca binária a uma maneira de percorrer ``v`` com índices :math:`\mathtt{e}` e :math:`\mathtt{d}` similar ao que é feito em uma versão do ``separe()`` do Quicksort. Aqui está uma implementação da função ``magica()``. .. code:: def magica(v): '''(list) -> int RECEBE uma lista v RETORNA o número trios v[i], v[j] e v[k], com i < j < k tais que v[i] + v[j] + v[k] = 0. ''' conta = 0 n = len(v) v = sorted(v) for i in range(n-2): x = v[i] e = i+1 d = n-1 while e < d: y = v[e] z = v[d] soma = x + y + z if soma > 0: d -= 1 elif soma < 0: e += 1 else: conta += 1 e += 1 d -= 1 return conta Para cada valor de :math:`\mathtt{i}` o bloco de comandos dentro de ``for i in range(n-2):`` consome tempo :math:`\mathtt{\textup{O}(n)}`. Portanto, o consumo de tempo total da função ``magica()`` é proporcional a :math:`\mathtt{n^2}`. :: n magica cont 16 0.00 14 32 0.00 57 64 0.00 247 128 0.00 985 256 0.01 3829 512 0.03 16289 1024 0.11 65421 2048 0.48 264028 4096 2.16 1040099 8192 8.93 4188640 16384 36.58 16744670 Voltamos a pergunta Quanto tempo a função gastaria para resolver o problema com uma lista de :math:`\mathtt{2^{17} = 131072}` inteiros? Suponhamos que o tempo gasto pela função ``magica()`` siga a regra :math:`\mathtt{T(n) = c \; n^2}`. Dessa forma teremos que .. math:: \begin{align*} \mathtt{T(131072)} & = \mathtt{c\, 131072^2} \\ & = \mathtt{8^2 \times c\, 16384^2} \\ & = \mathtt{8^2 \times T(16384)} \\ & \approx \mathtt{64 \times 37} \\ & = \mathtt{2368} \ \mbox{segundos} \end{align*} Diminuimos ainda mais o tempo! :math:`\mathtt{2368}` segundos são aproximadamente :math:`\mathtt{38}` minutos. |:crown:| Bem, vejamos a tabela completa até 131072. :: n magica cont 16 0.00 14 32 0.00 57 64 0.00 247 128 0.00 985 256 0.01 3829 512 0.03 16289 1024 0.11 65421 2048 0.48 264028 4096 2.16 1040099 8192 8.93 4188640 16384 36.58 16744670 32768 143.07 67207738 65536 593.73 267403147 131072 2247.64 1074426532 Vixe! :math:`\mathtt{2247.64}` segundos são aproximadamente :math:`\mathtt{37}` minutos e havíamos estimado que o tempo seria de :math:`\mathtt{38}` minutos! |:crown:| |:fireworks:| Bem, é para isso mesmo que serve a combinação das análises de algoritmos experimentais e analíticas. .. raw:: html Lições ------ Chegou o momento de abrirmos a caixa de ferramentas, o pote de ideias, que andamos montando ao longo do ano e resolvermos alguns problemas. As ferramentas que usamos aqui foram *ordenação*, *busca binária*, *dicionários*, *pré-processamento*,..., esquecemos alguma? As funções ``teste_tudo()``, ``sorted_bb()`` e ``conta_dict()`` tem uma mesma estrutura, com a diferença que no coração de * ``teste_tudo()`` pulsa a **busca sequencial**; * ``sorted_bb`` corre o sangue da **busca binária**; e * ``conta_dict()`` a frequência é a dos **dicionários**. Eficiência de ``list`` ----------------------- Suponha que a lista ``v`` tem ``n`` elementos e que a lista ``w`` tem ``k`` elementos. A tabela abaixo foir copiada de `Resolução de problemas em Python `_. Veja também a página `TimeComplexity `_. .. math:: \begin{array}{lc} \text{Operação} & \text{consumo de tempo} \\ \hline \texttt{v[i]}& \mathtt{\textup{O}(1)}\\ \texttt{v[i] = x}& \mathtt{\textup{O}(1)}\\ \texttt{v.append(item)}& \mathtt{\textup{O}(1)}\\ \texttt{pop()}& \mathtt{\textup{O}(1)}\\ \texttt{pop(i)}& \mathtt{\textup{O}(n)}\\ \texttt{insert(i,item)}& \mathtt{\textup{O}(n)}\\ \texttt{del v[i]}& \mathtt{\textup{O}(n)}\\ \texttt{for item in v:}& \mathtt{\textup{O}(n)}\\ \texttt{item in v}& \mathtt{\textup{O}(n)}\\ \texttt{v[e:d]}& \mathtt{\textup{O}(k)}\\ \texttt{del v[e:d]}& \mathtt{\textup{O}(n)}\\ \texttt{v[e:d] = w}& \mathtt{\textup{O}(n+k)}\\ \texttt{v.reverse()}& \mathtt{\textup{O}(n)}\\ \texttt{v+w}& \mathtt{\textup{O}(k)}\\ \texttt{v.sort()}& \mathtt{\textup{O}(n \lg n)}\\ \texttt{v*k}& \mathtt{\textup{O}(nk)}\\ \hline \end{array} Eficiência de ``dict`` ---------------------- Um dicionário é objeto que associa uma **chave** a um **valor**. A chave precisa ser única, em um dicionário não podemos ter chaves repetidas. As chaves também deve ser objetos imutáveis com números e strings. O Python possui o tipo nativo ``dict`` que permite a criação e manipulação de dicionários. Para se criar um dicionário vazio, podemos escrever .. code:: python In [2]: dic = {} Com pode ser visto, usamos chaves ao invés dos colchetes como usados na criação de listas. Podemos criar dicionários com elementos, separando a chave do valor usando dois pontos (``:``) como em: .. code:: python In [3]: dic = {'banana':50, 'abacaxi':10} In [4]: print(dic) {'banana': 50, 'abacaxi': 10} Utilizamos chaves como en lista para inserir ou modificar um elemento do dicionário como: .. code:: python In [5]: dic = {'banana':50, 'abacaxi':10} In [6]: print(dic) {'banana': 50, 'abacaxi': 10} In [7]: dic["melancia"] = 7 In [8]: print(dic) {'banana': 50, 'abacaxi': 10, 'melancia': 7} In [9]: dic['banana'] += 15 In [10]: print(dic) {'banana': 65, 'abacaxi': 10, 'melancia': 7} O acesso de uma chave usando colchetes ``[]`` resulta em erro caso a chave não exista. Uma forma de evitar esse erro é acessar uma chave usando o método ``get(chave)``, que retorna ``None`` caso a chave não existir. O ``for`` oferece uma forma conveniente de varrer todas as chaves do dicionário, como: .. code:: python In [11]: for fruta in dic: ... print(f"chave:{fruta} \t valor: {dic[fruta]}") ... chave:banana valor: 65 chave:abacaxi valor: 10 chave:melancia valor: 7 Agora vamos aos consumos de tempo. Suponha que o dicionário ``d`` tem ``n`` itens, pares ``chave-valor``. A tabela foi copiada de `Dicionários `_ de `Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python `_ de Brad Miller e David Ranum. Veja também a página `TimeComplexity `_. .. math:: \begin{array}{lc} \text{operação} & \text{consumo de tempo médio} \\ \hline \texttt{d.copy()}& \mathtt{\textup{O}(n)}\\ \texttt{d[chave]}& \mathtt{\textup{O}(1)}\\ \texttt{d[chave]=valor}& \mathtt{\textup{O}(1)}\\ \texttt{del d[chave]}& \mathtt{\textup{O}(1)}\\ \texttt{for chave in d:}& \mathtt{\textup{O}(n)}\\ \texttt{item in v}& \mathtt{\textup{O}(1)}\\ \hline \end{array} Exercícios ---------- #. Modifique a função ``testa_tudo()`` para que ela faça menos adições. Para saber mais --------------- * `Analysis of Algorithms `_ de `Introduction to Programming in Python `_. de Robert Sedgewick, Kevin Wayne e Robert Dondero. * `bisect — Array bisection algorithm `_ da `Python documentation `_. * `Data Structures `_ da `Python documentation `_ . * `Dicionários `_ de `Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python `_ de Brad Miller e David Ranum. * `heapq — Heap queue algorithm `_ da `Python documentation `_ . * `Listas `_ de `Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python `_ de Brad Miller e David Ranum. * `queue `_ da `Python documentation `_ . * `Resolução de problemas em Python `_. * `Sorting HOW TO `_ da `Python documentation `_. * `TimeComplexity `_.