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.
for
devesse ser:for j in range(i+1, n):
?