25. 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

\[\begin{split} \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}\end{split}\]

Fizemos análises experimentais para treinar a validação das nossas contas, validação dos nossos modelos, estimando os tempos gastos pelas funções.

25.1. 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.

25.2. 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 é \(\mathtt{\textup{O}(n^{2}(\lg \lg n)^{\textup{O}(1)}/{\log ^{2}n})}\) em que \(\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 \(\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. 🤔

25.3. 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.

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 \(\mathtt{v[i]+v[j]+v[k] = 0}\) para todos indices válidos \(\mathtt{i < j < k}\). Por exemplo,

   +----+----+----+----+----+----+----+----+
   | 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:

\[\begin{split}\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*}\end{split}\]

O consumo de tempo é portanto \(\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 \(\mathtt{T(n)}\) segundos em que \(\mathtt{n}\) é o número de elementos da lista. O fato do consumo de tempo ser \(\mathtt{\textup{O}(n^3)}\) sugere que \(\mathtt{T(n)}\) pode ser aproximada por uma função da forma da forma \(\mathtt{cn^3}\) para alguma constante \(\mathtt{c}\). Assim, se para \(\mathtt{T(n) = t}\) segundos então

\[\begin{split}\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*}\end{split}\]

Vemos que o tempo gasto pela função testa_tudo() para trabalhar com uma lista de 4096 elementos foi de \(\mathtt{2709.14}\) segundos que corresponde a aproximadamente 45 minutos 15 segundos. 🤦🏼‍♀️ 🤦🏾‍♂️ 🤦🏾‍♀️ 🤦🏿‍♂️

Quanto tempo a função gastaria para resolver o problema com uma lista de \(\mathtt{2^{17} = 131072}\) inteiros?

Vejamos …

Supondo que o tempo gasto pela função obedece a função \(\mathtt{T(n) = cn^3}\) para alguma contante \(\mathtt{c}\) teremos que

\[\begin{split}\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*}\end{split}\]

Portanto, a resposta é aproximadamente \(\mathtt{1024}\) dias. 🤦🏼‍♀️ 🤦🏾‍♂️ 🤦🏾‍♀️ 🤦🏿‍♂️

25.4. 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 \(\mathtt{\textup{O}(n \lg n)}\) e
• bisect.bisect_left(): função busca binária que consome tempo \(\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:

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 .

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:

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 \(\mathtt{i}\) e \(\mathtt{j}\), com \(\mathtt{i < j}\),

• calculamos a soma \(\mathtt{v[i]+v[j]}\)
• procuramos na lista ordenada o elemento \(\mathtt{-(v[i]+v[j])}\) usando busca binária;
• se o elemento é encontrado em uma posição \(\mathtt{k}\) tal que \(\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.

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 \(\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 \(\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 \(\mathtt{9.83}\) segundos. 👍🏽 👍🏻 👍🏿 Para uma lista com 16384 o tempo gasto foi de \(\mathtt{213.36}\) segundos que são aproximadamente \(\mathtt{3.5}\) minutos.

Quanto tempo a função gastaria para resolver o problema com uma lista de \(\mathtt{2^{17} = 131072}\) inteiros?

Supondo agora que o tempo gasto respeita a função \(\mathtt{T(n) = c \; n^2 \lg n}\) para alguma constante \(\mathtt{c}\) obtemos que

\[\begin{split}\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*}\end{split}\]

Bem, de 1024 dias reduzimos o tempo de espera para menos que \(\mathtt{6}\) horas. 👍🏽 👍🏻 👍🏿 Será que conseguimos dimuir mais ainda?

25.5. 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 \(\mathtt{i}\) e \(\mathtt{j}\), com \(\mathtt{i < j}\),

• calculamos a soma \(\mathtt{v[i]+v[j]}\);
• procuramos o elemento \(-(\mathtt{v[i]+v[j]})\) no dicionário;
• se esse elemento for encontrado em uma posição \(\mathtt{k}\) tal que \(\mathtt{i < j < k}\), bingo! Encontramos um novo trio de soma zero.

A condição \(\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.

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. 😵 Essa é uma característica encantada 🧙🏾 de um dicionário. Escrevemos que esse consumo de tempo é \(\mathtt{\textup{O}(1)}\). Portanto, o consumo de tempo esperado da função conta_dict() é \(\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 \(\mathtt{49.84}\) segundos. 🙌🏼 🙌🏿 🙌🏾 digamos \(\mathtt{50}\) segundos. A função sorted_bb() havia gasto \(\mathtt{3.5}\) minutos.

A pergunta agora é, novamente,

Quanto tempo a função gastaria para para resolver o problema com uma lista de \(\mathtt{2^{17} = 131072}\) inteiros?

Suponhamos agora que o tempo gasto esperado respeita a função \(\mathtt{T(n) = c \; n^2}\) em que \(\mathtt{c}\) é uma constante. Obtemos que

\[\begin{split}\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*}\end{split}\]

Ops! Menos que \(\mathtt{55}\) minutos. 🥇 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 \(\mathtt{2^{16}=65536}\) inteiros?

Mais uma vez, suponhamos que o tempo gasto esperado respeite \(\mathtt{T(n) = c \; n^2}\) em que \(\mathtt{c}\) é uma constante. Temos que

\[\begin{split}\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*}\end{split}\]

Resposta: menos que \(\mathtt{14}\) minutos! 🥇

25.6. 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 \(\mathtt{i}\) e procuramos índices \(\mathtt{e}\) e \(\mathtt{d}\) tais que \(\mathtt{v[i]+v[e]+v[d] = 0}\). A procura por \(\mathtt{v[e]}\) e \(\mathtt{v[d]}\) tais que \(\mathtt{v[i] = -(v[e]+v[d])}\) combina aspectos da busca binária a uma maneira de percorrer v com índices \(\mathtt{e}\) e \(\mathtt{d}\) similar ao que é feito em uma versão do separe() do Quicksort. Aqui está uma implementação da função magica().

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 \(\mathtt{i}\) o bloco de comandos dentro de for i in range(n-2): consome tempo \(\mathtt{\textup{O}(n)}\). Portanto, o consumo de tempo total da função magica() é proporcional a \(\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 \(\mathtt{2^{17} = 131072}\) inteiros?

Suponhamos que o tempo gasto pela função magica() siga a regra \(\mathtt{T(n) = c \; n^2}\). Dessa forma teremos que

\[\begin{split}\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*}\end{split}\]

Diminuimos ainda mais o tempo!

\(\mathtt{2368}\) segundos são aproximadamente \(\mathtt{38}\) minutos. 👑 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! \(\mathtt{2247.64}\) segundos são aproximadamente \(\mathtt{37}\) minutos e havíamos estimado que o tempo seria de \(\mathtt{38}\) minutos! 👑 🎆 Bem, é para isso mesmo que serve a combinação das análises de algoritmos experimentais e analíticas.

25.7. 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.

25.8. 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.

\[\begin{split}\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}\end{split}\]

25.9. 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

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:

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:

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:

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.

\[\begin{split}\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}\end{split}\]

25.10. Exercícios

1. Modifique a função testa_tudo() para que ela faça menos adições.

25.11. 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.