Já escrevi aqui no site sobre curto-circuito nos operadores or e and da linguagem Python. Neste artigo, vamos verificar que o conceito de curto-circuito também se aplica às funções all e any, presentes numa instalação padrão da linguagem. E, mais, vamos ver a utilidade de cada uma dessas funções e cuidados ao utilizá-las com base em uma análise de complexidade.
Tópicos
all
Vamos começar verificando o que a documentação informa sobre a função:
help(all)Help on built-in function all in module builtins:
all(iterable, /)
Return True if bool(x) is True for all values x in the iterable.
If the iterable is empty, return True.
Como indica documentação, se cada valor x de um iterável passado para a função retornar True em bool(x), a função retorna True. Um iterável, de acordo com a documentação, nada mais é que um objeto que pode retornar seus membros um de cada vez como, por exemplo, tipos sequenciais como listas, strings e tuplas. Usando uma lista como exemplo, podemos verificar que é um iterável através de um simples loop for:
lista_exemplo = [1, 2, 3, 4]
for numero in lista_exemplo:
print(numero)1 2 3 4
O que for faz é passar o iterável, no exemplo a lista, para a função iter(), que retorna um iterador, do qual o for solicita cada item sucessivamente através de uma chamada next() até que o o iterável seja completamente consumido. No exemplo, a lista é consumida passando cada item sucessivamente para a função print.
Caso ainda tenha ficado em dúvida, recomendo fortemente a leitura desse artigo sobre iteradores e iteráveis onde é explicado detalhadamente o conceito com diversos exemplos.
Vamos para um exemplo simples, passando algumas sequências para a função all:
todos_true = (True, True, True)
all(todos_true)True
Se pelo menos um valor for False, o retorno da função será False:
alguns_true = (True, False, True)
all(alguns_true)False
Já vimos em outros artigos que o interpretador considera alguns casos casos como False. Eis alguns exemplos:
print(bool(False)) # a própria palavra reservada False
print(bool(None)) # a palavra reservada None
print(bool(0)) # o inteiro 0 (zero)
print(bool("")) # uma string vazia
print(bool(())) # uma tupla vazia
print(bool([])) # uma lista vazia
print(bool({})) # um dicionário vazioFalse False False False False False False
Assim, podemos fazer um exemplo mais completo no qual o retorno da função all é True:
todos_true = (True, "Chico", 1, (1, 2), [1, 2], {'a': 1, 'b': 2})
all(todos_true)True
O exemplo a seguir retorna False por possir uma string vazia entre os valores passados:
alguns_true = (True, "", 1, (1, 2), [1, 2], {'a': 1, 'b': 2})
all(alguns_true)False
Já o seguinte exemplo retorna False por possir um inteiro de valor zero entre os valores passados:
alguns_true = (True, "Chico", 0, (1, 2), [1, 2], {'a': 1, 'b': 2})
all(alguns_true)False
Espero que esses exemplos tenham sido o suficiente para entender o retorno da função. Nos dois últimos, por existir ao menos um elemento que retorna False ao ser passado como argumento para bool(), o retorno de all() será False. Agora, será que é necessário analisar cada valor passado para ter o retorno? Para avaliar isso, vamos criar a seguinte função:
def funcao_executada(valor):
print("Fui executada!")
return valorObserve que é uma função bem simples, que recebe um determinado valor, que pode ser de qualquer tipo, faz o print da string “Fui executada!” e retorna o mesmo valor passado. Vamos fazer um pequeno teste passando a string “oi” como argumento da função:
funcao_executada('oi')Fui executada!
'oi'
Observe a presença da mensagem “Fui executada!” e do retorno da string passada para a função. Mas qual o objetivo desse função?
Considere a célula de código abaixo. Nela há uma lista denominada lista_teste. Veja que todos os itens dela retornam True caso sejam passados como argumento da função bool, exceto o terceiro item, por ser o inteiro zero. Isso significa que o retorno da passagem de tal lista par a função all deve ser False. Mas será que a função all precisa avaliar todos os valores?
Para descobrir, vamos criar um gerador usando uma generator expression. Tal expressão origina um gerador que, ao invés de retornar de uma única vez todos os valores, os retorna sob demanda. Para maiores detalhes veja este artigo do site sobre geradores. Veja nas células abaixo como a expressao_geradora retorna cada valor sob demanda da função next:
lista_teste = [True, "Chico", 0, (1, 2), [1, 2], {'a': 1, 'b': 2}]
expressao_geradora = (funcao_executada(item) for item in lista_teste)
expressao_geradora<generator object <genexpr> at 0x7f2b1d5eec10>
next(expressao_geradora)Fui executada!
True
next(expressao_geradora)Fui executada!
'Chico'
next(expressao_geradora)Fui executada!
0
Acho que já deu para entender, poderíamos continuar solicitando cada item até a lista ser toda consumida. Caso queira todos os valores restantes de uma única vez, basta passar o gerador para um container como, por exemplo, uma lista:
list(expressao_geradora)Fui executada! Fui executada! Fui executada!
[(1, 2), [1, 2], {'a': 1, 'b': 2}]
Agora o gerador foi exaurido, de forma que um novo next retornará uma exceção StopIteration:
next(expressao_geradora)--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-16-7ac23c2b0c8d> in <module> ----> 1 next(expressao_geradora) StopIteration:
Observe que o comportamento de um gerador é de um iterável, conforme conceito do início do artigo. Como o gerador foi exaurido, vamos criá-lo novamente e passá-lo para a função all:
expressao_geradora = (funcao_executada(item) for item in lista_teste)
all(expressao_geradora)Fui executada! Fui executada! Fui executada!
False
Observe que foram apresentadas três vezes a mensagem “Fui executada!”. Faz sentido, pois os dois primeiros itens retornam True ao serem passados como argumento da função bool, enquanto que o terceiro, o inteiro zero, retorna False. Como o objetivo da função all é retornar True apenas se todos os itens retornarem True, não é necessário avaliar os demais itens após achar um caso de False. Assim, demonstramos que a função all apresenta comportamento de curto-circuito.
OK, mas o que fazer com essa informação? Qual a consequência prática disso? Vamos ver o que acontece se for passado um grande iterável, no caso uma lista de um milhão de valores:
lista_gigante_todos_true = [True] * 1_000_000Todos os valores dessa lista são True, isso significa que o retorno da função all deve ser True. Mas, pelo que vimos anteriormente, a função passa por cada valor antes de dar seu retorno. Já vimos nesse artigo que o IPython e o Jupyter Notebook têm funções próprias (“mágicas” na documentação) que permitem fazer algumas análises interessantes. Uma delas é a %timeit, que permite medir o tempo que um dado comando demora. Como esse artigo está sendo escrito em um Jupyter Notebook, podemos usar essa função. Vamos ver o tempo passando essa lista com um milhão de valores True:
%timeit all(lista_gigante_todos_true)3.72 ms ± 74.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Vamos comparar esse dado com o tempo de listas que possuem ao menos um valor False. Já sabemos que o retorno será False, mas em quanto tempo? Comecemos gerando uma lista, também com um milhão de itens, com valor False logo no início, no índice 10:
lista_gigante_com_false_indice_10 = lista_gigante_todos_true.copy()
lista_gigante_com_false_indice_10[10] = False%timeit all(lista_gigante_com_false_indice_10)98.1 ns ± 0.44 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
Observe a grande diferença! Saímos de milisegundos (10-3 segundos) para nanossegundos (10-9 segundos). Uma melhoria de um milhão de vezes! Mas isso porque o valor estava logo no início, vamos criar outra lista de um milhão de itens, sendo apenas um False mas na última posição:
lista_gigante_com_false_ultimo_indice = lista_gigante_todos_true.copy()
lista_gigante_com_false_ultimo_indice[-1] = False%timeit all(lista_gigante_com_false_ultimo_indice)3.8 ms ± 123 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Observe que voltamos novamente para a casa de milisegundos, valor quase igual ao da lista com todos os valores True. Faz sentido, cada valor foi analisado sequencialmente até chegar ao último.
Apenas para fechar o raciocínio, vamos colocar um único False, mas exatamente no meio da lista:
lista_gigante_com_false_indice_meio = lista_gigante_todos_true.copy()
lista_gigante_com_false_indice_meio[499_999] = False%timeit all(lista_gigante_com_false_indice_meio)1.83 ms ± 3.31 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Como esperado, obtivemos um valor que é praticamente a metade do anterior.
Ou seja, temos uma função de comportamento linear no que diz respeito à uma análise de complexidade temporal. No pior caso possível, terá que avaliar todos os itens para conseguir ter retorno. Tenha isso em mente se pretende usar tal função em uma grande quantidade de dados, especialmente se houver motivos para acreditar que haverá poucos False, pois se estiverem no final do iterável um grande tempo será necessário. Caso queira ver o código fonte em C dessa função e se certificar da implementação clique aqui.
any
Vamos seguir o mesmo roteiro feito anteriormente para a função all. Começando pela documentação:
help(any)Help on built-in function any in module builtins:
any(iterable, /)
Return True if bool(x) is True for any x in the iterable.
If the iterable is empty, return False.
Novamente, tal função recebe um iterável. Mas, neste caso, retorna True se ao menos um dos itens tiver retorno True ao ser passado como argumento da função bool. Vamos ver dois exemplos. No primeiro, passamos apenas valores False:
todos_false = (False, False, False)
any(todos_false)False
Como era de se esperar, tivemos o retorno False. Se ao menos um dos valores passados for True, já é o suficiente para termos retorno True:
alguns_false = (False, True, False)
any(alguns_false)True
Como já visto, não necessariamente precisamos passar diretamente True ou False, podemos passar outros tipos que terão retornos True ou False ao serem passados para a função bool. Vamos redefinir nossa variável lista_teste a seguir. Observe que os três primeiros itens retornam False ao serem passados para a função bool (veja a célula de código 5 acima caso tenha dificuldade de entender). Vamos passar tal lista para nossa expressão geradora:
lista_teste = [False, "", 0, (1, 2), [1, 2], {'a': 1, 'b': 2}]
expressao_geradora = (funcao_executada(item) for item in lista_teste)
expressao_geradora<generator object <genexpr> at 0x7f2b1d5eef20>
E passar tal expressão para a função any:
any(expressao_geradora)Fui executada! Fui executada! Fui executada! Fui executada!
True
Veja que a função foi executada 4 vezes. Ao encontrar o primeiro item que retorna True não é mais necessário continuar consumindo o gerador, pois um True é o suficiente para o retorno da função como True. Novamente, um comportamento de curto-circuito.
Assim, como fizemos para all, bamos ver o que acontece se for passado um grande iterável, no caso uma lista de um milhão de valores:
lista_gigante_todos_false = [False] * 1_000_000Todos os valores dessa lista são False, isso significa que o retorno da função any deve ser False. Mas, pelo que vimos anteriormente, a função passa por cada valor antes de dar seu retorno. Vamos ver o tempo passando essa lista com um milhão de valores False:
%timeit any(lista_gigante_todos_false)3.18 ms ± 93.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Vamos comparar esse dado com o tempo de listas que possuem ao menos um valor True. Já sabemos que o retorno será True, mas em quanto tempo? Comecemos gerando uma lista, também com um milhão de itens, com valor True logo no início, no índice 10:
lista_gigante_com_true_indice_10 = lista_gigante_todos_false.copy()
lista_gigante_com_true_indice_10[10] = True%timeit any(lista_gigante_com_true_indice_10)94.4 ns ± 0.355 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
Observe a grande diferença! Saímos de milisegundos (10-3 segundos) para nanossegundos (10-9 segundos). Uma melhoria de um milhão de vezes! Mas isso porque o valor estava logo no início, vamos criar outra lista de um milhão de itens, sendo apenas um True mas na última posição:
lista_gigante_com_true_ultimo_indice = lista_gigante_todos_false.copy()
lista_gigante_com_true_ultimo_indice[-1] = True%timeit any(lista_gigante_com_true_ultimo_indice)3.18 ms ± 41.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Observe que voltamos novamente para a casa de milisegundos, valor quase igual ao da lista com todos os valores False. Faz sentido, cada valor foi analisado sequencialmente até chegar ao último.
Apenas para fechar o raciocínio, vamos colocar um único True, mas exatamente no meio da lista:
lista_gigante_com_true_indice_meio = lista_gigante_todos_false.copy()
lista_gigante_com_true_indice_meio[499_999] = True%timeit any(lista_gigante_com_true_indice_meio)1.54 ms ± 3.18 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Como esperado, obtivemos um valor que é praticamente a metade do anterior.
Ou seja, assim como a all, a any também é uma função de comportamento linear no que diz respeito à uma análise de complexidade temporal. No pior caso possível, terá que avaliar todos os itens para conseguir ter retorno. Tenha isso em mente se pretende usar tal função em uma grande quantidade de dados, especialmente se houver motivos para acreditar que haverá poucos True, pois se estiverem no final do iterável um grande tempo será necessário. Caso queira ver o código fonte em C dessa função e se certificar da implementação clique aqui.
Conclusão
Por esse artigo é isso. Espero que tenha compreendido e aprendido algo novo. Passamos por diversos conceitos, como iteráveis, iteradores, funções geradores e fizemos um pouco de análise de complexidade temporal de algoritmos. Muito valor agregado, tenho certeza.
Aproveite para acompanhar o Ciência Programada nas redes sociais.
Gostou desse artigo? Ele faz parte do Python Drops, um conjunto de posts mais curtos voltados para fundamentos falando sobre alguns aspectos da linguagem Python e de programação em geral. Você pode ler mais desses artigos buscando a tag “drops” aqui no site. Até a próxima!
Observação: o tempo gerado pela %timeit pode variar de máquina para máquina, não necessariamente você obterá os mesmos valores. No entanto, a diferença de ordens de grandeza deve se manter.
