Como fazer a implementação “in” no Python

Como fazer a implementação “in” no Python

12 de junho de 2019 0 Por Ramos de Souza Janones
Do Zero ao Profissional com PHP. Mais de 2.300 alunos recomenda.Powered by Rock Convert

Por que é tão mais rápido? Apenas por que é escrito em C? Caso sim, existem algumas outras implementações melhores e conhecidas que seriam melhor usadas se forem a original?

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.

Como limpar o console no Python com Linux

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?

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.

Treinamento em Machine Learning, Big Data e Analytics com PYTHON, HADOOP, SPARK e APACHE KAFKA! PRESENCIAL e ONLINE!

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 (sets):

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.

VOCÊ ESTÁ NAS SEÇÕES:  Programação » Python

Powered by Rock Convert
Powered by Rock Convert

Ramos de Souza Janones

Janones, é um empreendedor brasileiro apaixonado por empreendedorismo e tecnologia. Ao longo dos anos trabalhando com o desenvolvimento de softwares desktop desde a linguagem Clipper, passando pelo Delphi e atualmente com Java.

Optou pela formação de Publicidade e Marketing por sua segunda empresa de tecnologia ter participado do "boom" da internet nos anos 90 e na procura de melhorar seus conhecimentos em negócios.

Em razão da principal formação e profundos conhecimentos em programação e banco de dados, é capaz de realizar o desenvolvimento de aplicativos web, desktop e mobile com maior criatividade e inovação que profissionais de desenvolvimento com uma formação única e mais especifica, dedicada somente ao desenvolvimento de softwares.

Com toda sua experiência com empresas de software, sua formação e paixão por negócios escreveu o livro "Marketing para Empresas e Profissionais de Software", publicado pela editora carioca Ciência Moderna em 2012. Além de outros livros sobre programação.

Últimos posts por Ramos de Souza Janones (exibir todos)

Sumário
Como fazer a implementação "in" no Python
Nome do artigo
Como fazer a implementação "in" no Python
Descrição
Por que é tão mais rápido? Apenas por que é escrito em C? Caso sim, existem algumas outras implementações melhores e conhecidas que seriam melhor usadas se forem a original?
Autor
Nome
Ramos da Informática
Logo

Frontend Do Zero Ao Profissional