7

O programa abaixo retorna a menor diferença possível entre todos os elementos de uma lista:

def calculo(A):
    r = float("inf")
    n = len(A)
    for i in range(0, n-1):
        for j in range(1, n):
            if abs(A[i] - A[j]) < r:
                r = abs(A[i] - A[j])
    print(r)

Mas estou cansado de escrever todos os códigos que precisam comparar pares de elementos de uma mesma lista, como se estivesse escrevendo um bubble sort.

Como reduzo o número de loops no código acima? Qual o princípio pra começar a se pensar diferente e começar a escrever códigos mais eficientes?

1
  • 1
    Talvez o segundo for devesse ser: for j in range(i+1, n):?
    – anonimo
    Commented 10/03/2020 às 20:12

1 Resposta 1

5

Uma alternativa é primeiro ordenar a lista, e depois percorrê-la apenas uma vez, calculando a diferença entre cada elemento e o próximo. Como a lista estará ordenada, não é necessário calcular a diferença entre o primeiro e o terceiro, por exemplo, pois certamente será maior ou igual à diferença entre o primeiro e o segundo.

def menor_diferenca(lista):
    r = float("inf")
    lista = sorted(lista)
    for i in range(len(lista) - 1):
        diff = abs(lista[i] - lista[i + 1])
        if diff < r:
            r = diff
    return r

Claro que ordenar a lista tem o seu custo, mas segundo a documentação, o algoritmo usado é o TimSort, que garante um bom desempenho (O(n logn) no pior caso), o que já é melhor que dois loops aninhados.

Um detalhe é que seu segundo loop não está certo. Por exemplo, quando i for 3, você faz um for j in range(1, n), ou seja, j também passará pelo índice 3 e aí a diferença será zero (se a lista não tiver valores repetidos, o resultado será - erroneamente - zero). Então na verdade este loop deve começar em i + 1.


Fazendo uma comparação básica, usando o módulo timeit para medir os tempos:

def com_loop(lista):
    r = float("inf")
    n = len(lista)
    for i in range(0, n - 1):
        for j in range(i + 1, n):
            diff = abs(lista[i] - lista[j])
            if diff < r:
                r = diff
    return r

def com_sort(lista):
    r = float("inf")
    lista = sorted(lista)
    for i in range(len(lista) - 1):
        diff = abs(lista[i] - lista[i + 1])
        if diff < r:
            r = diff
    return r


import random
# gerando uma lista com 1000 números aleatórios
numeros = random.sample(range(1, 1000000), 1000)

import timeit

print(timeit.repeat('com_loop(numeros)', repeat=3, number=100, globals=globals()))
print(timeit.repeat('com_sort(numeros)', repeat=3, number=100, globals=globals()))

O tempo de execução exato varia de uma máquina para outra, e mesmo na mesma máquina pode ter variações entre uma execução ou outra, mas só para ter uma ideia, o resultado que obtive foi:

[24.693826, 24.928060100000003, 25.2158304]
[0.13898210000000688, 0.14047560000000203, 0.10606690000000185]

Ou seja, os loops aninhados levaram cerca de 24 segundos, enquanto o algoritmo percorrendo a lista ordenada demorou por volta de 0,13 segundos.

Também coloquei o código em IDE's online e o resultado foi bem similar (a versão com a lista ordenada é bem mais rápida que os dois loops). Veja no Repl.it e no IdeOne.com (neste último tive que diminuir a quantidade de execuções para não estourar o tempo limite do site).


Você também poderia usar lista.sort() para ordenar a lista. A diferença é lista.sort() modifica a própria lista, enquanto sorted retorna outra lista.

1
  • 1
    Muito obrigado por todo o detalhe, e pelo benchmark, impressionante como n.log(n) cresce tão menor que exponencial. Eu realmente não tinha me tocado que com a lista ordenada só precisaria iterar uma vez, e não conhecia sobre timsort, pra mim, quicksort era a melhor opção disponível
    – Pirategull
    Commented 11/03/2020 às 9:11

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .