O interpretador Python é mantido por centenas de voluntários ao longo de décadas. Embora seja um software complexo, e, claro, longe de ser perfeito, em geral para coisa simples e óbvias, como "parar a busca no momento que o primeiro resultado é encontrado", a coisa está otimizada. (de novo: são centenas de colaboradores, ao longo de quase 3 décadas).
E sim, a função em C que você achou deve fazer a busca padrão do contains - e, ela para ao achar o primeiro valor igual. A questão é que a gente tem aulas na faculdade de C, decora o for
do C com o padrão i=0; i<X; i++
, e esquece que na verdade são expressões arbitrárias que podem ser muito bem usadas - e é o caso aí:
Py_ssize_t i;
int cmp;
for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
Py_EQ);
return cmp;
Observe a condição de parada do for
(a do meio, depois do primerio ;
): enquanto cmp == 0
e i < PySIZE(a)
- então não é só a segunda parte, a primeira também - assim que PyObject_RichCompareBool
retornar verdadeiro, a expressão do for
dá Falsa, e ele é interrompido. O valor de cmp
é verdadeiro e é retornado pela função em C.
O outro detalhe digno de nota nessa análise é justmamente esse: para respeitar a semântica do Python, a comparação entre os objetos é feita por essa função PyObject_RichCompareBool
- e não diretamente com ==
em cima de um ou mais campos do objeto. É ela que vai retornar True
se os objetos forem o mesmo (a parte do x is e
na documentação) ou se foram iguais - x == e
- só que para retornar o x == e
, e manter toda a coerência e simplicidade - para o programador - do Python é que está o pulo do gato - nesse ponto o Python verifica se os objetos tem implementações do método __eq__
e chama esses métodos (que podem inclusive ser em Python). Ou seja, mesmo na comparação em alta velociade, dentro do código nativo na função RichCompareBool
, se o objeto está personalizado em Python com um __eq__
específico, esse código é executado. No caso de inteiros, a versão do __eq__
para inteiros, bastante otimizada, mas ainda assim preparada para comparar inteiros com um número arbitrário de dígitos, é chamada.
E mesmo a expressão em Python sendo equivalente ao in
, a execução do operador é muito mais rápida por que a simples execução de x is e or x == e ...
envolve várias operações na VM do Python (VM == máquina virtual, a máquina de pilha que interpreta bytecode) - e cada operação na VM vai ser equivalente a, grosso modo, uma centena de operações nativas da CPU - enquanto que as comparações de um for
em C como o acima, requerem pouquíssimas expressões nativas na CPU, da ordem de 20.
O método dis.dis
permite uma visualização dos passos dessa expressão traduzidos em bytecode:
In [430]: dis.dis("x in e or x == e")
1 0 LOAD_NAME 0 (x)
2 LOAD_NAME 1 (e)
4 COMPARE_OP 6 (in)
6 JUMP_IF_TRUE_OR_POP 14
8 LOAD_NAME 0 (x)
10 LOAD_NAME 1 (e)
12 COMPARE_OP 2 (==)
>> 14 RETURN_VALUE
Como o uso de any
é mais lento?
O any
fica mais lento do que a funçãozinha que você criou que faz a comparação direta por que exige, para cada elemento, uma mudança de contexto na máquina virtual do Python - o any
, assim como a RichCompareBool
acima, tem que respeitar os protocolos do Python para os objetos, e no caso, isso é chamar o método __next__
da generator expression que você passa como parâmetro.
A VM do Python é um "grande switch case" em código nativo, que executa expressões e funções em C para cada bytecode da máquina Python. Ela é bem eficiente, e tem lá variáveis para acompanhar qual ponto do bytecode está em execução e algumas outras variáveis de estado da função em execução. Cada vez que o any
vai buscar um novo item (que no caso é o resultado da expressão x is e or x == e
, sempre True
ou False
), a VM tem que "trocar de contexto" - isso é, mudar todas as variáveis internas sobre qual objeto de código está em execução, em que ponto do bytecode está, etc... isso é bem mais "caro" em ciclos de clock do que ter o "True" ou "False" da mesma expressão no mesmo bloco de código, como está na sua função.
Por que Python continua sendo uma excelente escolha, mesmo com essa discrepância?
A proposta da linguagem é trazer simplicidade para implementação de algoritmos complexos, delegando os laços de computação intensiva para código nativo. E nesse caso, faz isso muito bem - se uma pessoa usa o in
, que é a forma "óbvia" de fazer uma busca em uma sequência, o caminho de código utilizado usa bastante código nativo e é naturalmente cerca de 5 vezes mais rápido do que re-escrever a mesma busca em Python (eu achava que essa diferença seria muito maior, na verdade).
Então se vocẽ leva em conta que a comparação do in
no Python faz tudo na máxima velocidade possível respeitando a natureza dinâmica dos objetos em Python - a comparação funciona também para classes que re-implementem a operação de "==" e façam qualquer coisa maluca no código - a implementação é muito boa.
Se você sabe que vai buscar números inteiros, numa coleção de tipos de dados homogêneos que Cabem na CPU, como inteiros de 32 ou 64bit, e precisa de velocidade, a forma de fazer isso é usar bibliotecas especialidas, por exemplo o numpy - O numpy vai fazer a comparação num vetor de inteiros e vai fazer isso não só em código nativo, mas usando instruções SIMD, e threads em CPUs concorrentes onde for o caso.
Então, numa máquina mais rápida que a sua - mas só colei exatamente o código que você colocou na questão, e em seguida, adicionei o código necessário para fazer a busca usando o numpy e exibi o tempo:
Usando o 'in' do Python, demorou 0.044108 e retornou True
Usando minha implementação, demorou 0.157202 e retornou True
Usando a implementação da documentação, demorou 0.262640 e retornou True
In [443]: import numpy as np
In [444]: np_list = np.array(list_of_integers, dtype="int32")
In [445]: %time x in np_list
CPU times: user 1.79 ms, sys: 997 µs, total: 2.79 ms
Wall time: 2.21 ms
Out[445]: True
2.21ms, ou 0.00221 segundos, comparado com o 0.044 da implementação com inteiros nativos - um ganho de 20x na velocidade. Isso é possível, de novo, graças a flexibilidade da linguagem, que permite que os arrays de numpy implementem o método __contains__
. Então, em vez do código em C genérico para qualquer objeto Python que estavamos analizando, o numpy usa código otimizado para busca em inteiros do tipo desejado.
Então, o interessante de ir aprendendo são coisas como essa: Python garante maior velocidade do desenvolvedor, e, uma vez que se sabe o que está fazendo, permite que o desenvolvedor delegue os laços mais críticos do programa para serem executados em código nativo, combinando o melhor dos dois mundos.
Mas não desligue ainda
Se realmente tempo for crítico numa busca de um elemento no meio de conjunto de outros, há uma coisa que ainda é mais rápida do que usar o numpy para busca em números nativos, que é , usar o algoritmo correto - em listas e arrays do numpy, o in
usa uma busca linear, comparando elemento por elemento. É fácil perceber que qualquer algoritmo que em vez de percorrer a lista linearmente vá "direto ao ponto" e diga se um elemento está lá ou não vai ser muito mais rápido. Em Python isso é feito com os conjuntos (set
s):
In [446]: conjunto_grande = {i for i in range(5_000_000)}
In [447]: conjunto_grande.add(x)
In [448]: %time x in conjunto_grande
CPU times: user 3 µs, sys: 0 ns, total: 3 µs
Wall time: 5.72 µs
Out[448]: True
Pronto, o tempo passou dos 2ms na busca linear com o numpy para 3 MICROssegundos - um ganho de 20000x em cima do in
em uma lista, e sem ter que recorrer a outra linguagem, assembler, nada - apenas fazendo uso dos tipos de dados de alto nível otimizados que a linguagem disponibiliza e com o programador "sabendo o que está fazendo".
Então, quando organizações como "Google e NASA" (sem nenhuma "mitologia") optam por usar Python num projeto, sim, os times levam em consideração todos esses fatores: o quanto vão ganhar em programadores/hora ao usar uma linguagem de muito alto nível no desenvolvimento, e quando e que partes otimizar em código nativo. O resultado são projetos como TensorFlow, um maquinário excepcionalmente otimizado para operações envolvendo redes neurais e aprendizado de máquina, mas podendo ser controlado por uma API em alto nível que economiza um tempo gigantesco que seria gasto em boiler-plate-code se a mesma biblioteca fosse ser usada a partir de uma linguagem de mais baixo nível.
any
não para logo que encontra um elemento? Pelo menos a documentação diz que ele para: docs.python.org/3/library/functions.html#any - E pra testar o tempo de execução, é melhor usar o módulotimeit
: docs.python.org/3.7/library/timeit.html(x is e or x == e for e in list_of_integers)
não percorre a lista inteira, só cria um generator, que é lazy (não retorna todos os booleanos de uma vez). Quando oany
vai iterar por esse generator, é pedido um elemento por vez, até encontrar um que satisfaça a condição. O que deve demorar é a criação do generator e as chamadas paranext()
, como o @jsbueno já citou no outro comentário