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
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:

Leia também:  
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).

Curso completo de Games, inclusive Realidade Aumentada.Powered by Rock Convert

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

React Native Do Zero Ao Profissional: crie apps para Android e IOSPowered by Rock Convert
Siga os bons!

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.

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