7

Eu estava tendo muita dificuldade de executar um código de forma eficiente e descobri que o problema estava em uma linha que usava o operador in. Então criei uma nova função que faz a busca por um match na lista de elementos de forma binária. Fiz uma análise da performance da minha função e do operador in e notei, para minha surpresa, que minha função era bem mais rápida. Aqui está meu código:

import bisect
import matplotlib.pyplot as plt
import time
import random
import numpy as np
import seaborn as sns

sns.set_style("whitegrid")

def belongs2(elements, value):
    index = bisect.bisect_left(elements, value)
    if index < len(elements) and elements[index] == value:
        return True
    else:
        return False
    
def belongs2time(elements, value):
    start_time=time.time()
    index = bisect.bisect_left(elements, value)
    if index < len(elements) and elements[index] == value:
        True
    else:
        False
    return time.time() - start_time

def in_time(elements, value):
    start_time=time.time()
    value in elements
    return time.time() - start_time


# ### Timing belongs


number=random.choice(range(1000))
lengths=np.arange(100,100000,100)
time_belongs=[]
for lenght_list in lengths:
    numbers=[random.choice(range(1000)) for i in range(lenght_list)]
    numbers.sort()
    time_belongs.append(belongs2time(numbers, number))


# ### Timing in

number=random.choice(range(1000))
lengths=np.arange(100,100000,100)
time_in=[]
for lenght_list in lengths:
    numbers=[random.choice(range(1000)) for i in range(lenght_list)]
    numbers.sort()
    time_in.append(in_time(numbers, number))

fig, ax= plt.subplots()

ax.plot(lengths, time_belongs, label='belongs')
ax.plot(lengths, time_in, label='in')

ax.spines['right'].set_visible(False)
ax.spines['top'].set_visible(False)

plt.legend(loc='upper center', bbox_to_anchor=(0.5,-0.15),
          ncol=2, fontsize=14)

plt.yscale('log')

plt.show()

inserir a descrição da imagem aqui

Eu não estou acostumado a fazer esse tipo de "análise de performance" (na verdade, é a primeira vez que faço isso), então posso ter cometido algum erro aqui e está chegando em uma conclusão errada. Mas se estiver certo, por que o operador in é tão lento? Eu esperava uma implementação mais eficiente de um método tão ubíquo ao python. Existe algum outro método built-in mais eficiente que o in para esse tipo de operação?

1 Resposta 1

5

Primeiramente, se quer testar o tempo de execução, uma forma rápida e um pouco mais confiável é usar o módulo timeit.

Dito isso, a busca usando o módulo bisect é mais rápida porque ela faz uma busca binária, que é um algoritmo conhecido por ter complexidade O(logN). Ou seja, em uma lista com bilhões de elementos, ela precisa de pouco mais de 30 iterações no máximo. O único pré-requisito para que funcione adequadamente é que os elementos estejam ordenados.

Já o operador in, quando aplicado a listas, faz uma busca linear (e portanto tem complexidade O(N)): ele parte do início da lista e vai testando os elementos um a um, até encontrar (ou até chegar ao final da lista, caso o elemento não exista). Apesar de mais lento que a busca binária, ele é o mais garantido caso a lista não esteja ordenada.

Enfim, não é que o in seja lento e ponto. Ele pode ser mais lento que outros algoritmos, como a busca binária, mas caso o uso desta não seja aplicável, ele ainda pode ser uma alternativa viável.


O seu teste re-escrito com timeit ficaria assim:

import bisect
import random

def belongs(elements, value):
    index = bisect.bisect_left(elements, value)
    return index < len(elements) and elements[index] == value

def in_time(elements, value):
    return value in elements

valores = range(10000)
number = random.choice(valores)
print(f'procurando por {number}')
numeros = list(valores)

from timeit import timeit

# executa 100 mil vezes cada teste
params = { 'number' : 100000, 'globals': globals() }
# imprime os tempos em segundos
print(timeit('belongs(numeros, number)', **params))
print(timeit('in_time(numeros, number)', **params))

Eu criei uma lista com todos os valores do range, assim já garanto que ela está ordenada (mas acho que tanto faz para fins de teste, poderíamos usar sua lista também).

Rodando, podemos ver que o in só é mais rápido se o número a ser procurado está logo no início da lista (se for um dos primeiros, o in encontra em menos iterações, já que a busca binária sempre parte do meio da lista).


Obs: se usar um set em vez de uma lista, a busca fica mais rápida:

valores = range(10000)
set_numeros = set(valores)
... restante do código igual ao exemplo acima

# adicionar mais um caso
print(timeit('in_time(set_numeros, number)', **params))

O detalhe, claro, é que um set não garante a ordem dos elementos e não permite valores repetidos. Se isso não for um problema, fazer a busca nele é mais rápida - conforme a página já linkada anteriormente, a operação in em um set é O(1).

3
  • Muito interessante. Obrigado pela resposta detalhada. Eu conhecia o conceito de busca binária, mas como você sabe que o in é linear? Eu fiz o teste justamente pq eu não sabia como o in fazia a busca. Tinha uma forma de saber que ele era linear de ante-mão?
    – Lucas
    Commented 4/12/2020 às 17:06
  • Desculpe, agora que vi que tinha essa informação na página que vc linkou
    – Lucas
    Commented 4/12/2020 às 17:07
  • 1
    @Lucas Outra alternativa é ver o código fonte :-)
    – hkotsubo
    Commented 4/12/2020 às 17:23

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 .