Somar output de uma função

Secção dedicada à linguagem de programação favorita dos quarkianos: Python!

Re: Somar output de uma função

Mensagempor jap em Quinta Fev 02, 2012 11:53 pm

Então ainda sobre o teu crash. Como bem disse o Francisco, o problema reside no teu count recursivo que esgota a memória de stack. Vejamos então o que se passa.

Uma função recursiva é uma função que se chama a ela própria. A forma como isto é implementado na maioria das linguagens de programação (incluindo a versão "normal" do Python) é recorrendo a memória de stack (em português dize "pilha"), que é uma porção da memória do teu computador que é reservada no início do programa para um conjunto de operação especiais - não vou aqui entrar em detalhe. O valor da memória de stack que é reservada é variável (no Python pode ser definida pelo utilizador, na realidade), mas não é uma memória muito grande - digamos que um stack de alguns megabytes é normalmente mais do que suficiente. Se for preciso mais, provavelmente há alguma coisa de errado com o programa pelo que, embora possamos aumentar o tamanho da memória de "stack", na realidade um erro de stack overflow deve ser encarado de frente, para perceber como é que esgotámos "a memória de pilha"!

Como é que uma função recursiva usa o stack?

Repara neste exemplo de uma função recursiva, que implementa o cálculo de n! usando a propriedade

n! = n*(n-1)!

e a definição 1! = 1.

Código: Seleccionar Todos
def fact(n):
    if n == 1:
        return 1
    else:
        return n*fact(n-1)


Quando usas esta função recursiva para calcular 6!, o programa procede da seguinte forma:

fact(6); é 6*fact(5) não sei o que é fact(5), então guardo espaço em memoria de stack para o que seja lá que isto for, mais espaço com a operação a efectuar, mais o número 6 que também é preciso guardar para multiplar com fact(5), quando se souber o que isto é.

Ora calculemos fact(5): isto é 5* fact(4), que não sei o que é; toca a reservar memória de stack para que seja lá que isto for, mais espaço com a operação a efectuar, mais o número 5 que também é preciso guardar para multiplar com fact(4), quando se souber o que isto é.
(...)
(...)
finalmente chegamos a fact(2) = 2* fact(1). Ena, fact(1) =1, isto a função sabe o que é! :D
Agora torna a percorrer a pilha ao contrário, substituindo todos os valores para trá:


2! = 2*1 = 2
3! = 3*2! = 3*2 = 6
4! = 4*3! = 4*6 = 24
5! = 5*4! = 5*24 =120
6! = 6*5! = 6*120=720

Uff!

Isto, para além de ser moroso, consume (na fase inicial, quando ainda não chegou à condição de paragem que resolve a ambiguidade da definição) muita memória de stack. É por estas duas razões que as funções recursivas devem ser usadas como muita parcimónia.

Pior que isso é uma função recursiva infinita, ou seja, aquela onde não há uma condição de paragem. É o caso da tua função count(n). Ora repara:

Código: Seleccionar Todos
def count(n):
    print n
    count(n+1)



é uma função sem condição de paragem, o equivalente a um ciclo infinito porque, na realidade, consome em cada passo uma porção da memória de stack à espera de ver a luz ao fundo do túnel - a condição de paragem, ou seja o equivalente no exemplo acima ao

Código: Seleccionar Todos
if n == 1:
   return n

Repara que no algoritmo factorial andamos para trás até chegar ao 1, que nos dá a condição de paragem. No teu caso, a tua definição de contagem contém a contagem acima e há sempre mais algo acima...nunca para!

O teu stack acabou num número próximo de 1000, mas é acidental, podia ser num outro número - foi quando esgotaste o teu stack! :lol:

Percebido?

Claro que isto tem solução! :yes Vou ensinar-te a programar uma função de contagem que não abusa do stack - na realidade essa função existe no Python, mas vou mostrar-te como se pode implementá-la recorrendo a um gerador. Mas para isso vou abrir um novo tópico, por uma questão de arrumação, OK?
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Somar output de uma função

Mensagempor jap em Sexta Fev 03, 2012 6:34 pm

Ah, e já agora aqui vai um programa pitónico que resolve (numa linha de códgo!) o problema nº1 do projecto Euler:

Código: Seleccionar Todos
sum(x for x in range(1000) if not (x%3 and x%5))


A função "sum" é intrínseca do Python e o argumento "x for x in range(1000) if not (x%3 and x%5)" é uma expressão que produz um gerador - mais sobre este assunto noutra altura.
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Somar output de uma função

Mensagempor ruifm em Sexta Fev 03, 2012 9:31 pm

tenho de ganhar a arte de sintetizar tudo numa linha. isso foisimpcesmente lindo :D
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Re: Somar output de uma função

Mensagempor Tharis em Sexta Fev 03, 2012 10:15 pm

ruifm Escreveu:tenho de ganhar a arte de sintetizar tudo numa linha. isso foisimpcesmente lindo :D


Sem querer ser desmotivador: não, não tens. Primeiro convém perceber o que estás a fazer e a estruturar bem o programa (código) e só depois entrar nos one-liners. Os one-liners não são nada mais que o uso das potencialidades ([in]finitas) do Python por quem já o (minimamente) domina. ;)
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Somar output de uma função

Mensagempor Bruno Oliveira em Sábado Fev 04, 2012 7:24 pm

ruifm Escreveu:tenho de ganhar a arte de sintetizar tudo numa linha. isso foisimpcesmente lindo :D


[Futuro] campeão do Codegolf em perspectiva!! :mock:

Mas como o Franscisco bem referiu, apenas depois da pessoa se habituar a resolver os problemas simples, estruturando-os com um paradigma mais comum, poderá tentar passar para o funcional e resolver one-liners!! E eles apenas te são úteis, ou para divertimento próprio, ou caso queiras/tenhas de por alguma razão em particular de escrever código mais curto que o habitual! :wink:

O importante no inicio, é ir aprendendo aos poucos as estruturas de dados da linguagem e combiná-las para escrever algoritmos eficientes... O resto vem com a experiência e com o tempo!
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Somar output de uma função

Mensagempor ruifm em Sábado Fev 04, 2012 7:37 pm

nao podem negar que fica lindo e subtil...
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Re: Somar output de uma função

Mensagempor Bruno Oliveira em Sábado Fev 04, 2012 7:57 pm

Para te convencer do que disse acima da maneira mais pitónica possível, abre o interpretador e escreve:

import this

e lê o ponto 2 e o ponto 7!! :wink:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Somar output de uma função

Mensagempor ruifm em Sábado Fev 04, 2012 8:37 pm

olhem eu nao sabia se havia de abrir um novo topico para isto.
como acedo ao idle no linux (tou agora a experimentar linux...)
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Re: Somar output de uma função

Mensagempor Tharis em Sábado Fev 04, 2012 9:57 pm

ruifm Escreveu:olhem eu nao sabia se havia de abrir um novo topico para isto.
como acedo ao idle no linux (tou agora a experimentar linux...)


O IDLE não vem por default instalado no linux. Se estiveres a usar uma Debian-based distro, tipo Ubuntu ou Mint podes usar fazer "apt-get search idle | grep python" e depois escolhes o pacote correcto (eu não sei o nome de cor) e fazes "sudo apt-get install NOME_DO_PACOTE".

Anyway, não sei bem para que queres o IDLE, em Linux ele não te faz nada que outras coisas que vêm instaladas de raiz façam. Em Windows dá jeito porque não tens assim nada de jeito, mas em Linux não precisas. ;)
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Somar output de uma função

Mensagempor ruifm em Sábado Fev 04, 2012 10:22 pm

ja consegui :)
o idle da um jeitao!
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Re: Somar output de uma função

Mensagempor filipematos em Domingo Fev 05, 2012 2:15 pm

Que distribuição tens? Se tiveres no ubuntu, no centro de programas tens vários "idles" para python e o vidle, tudinho é só instalares!!
"If I have seen further than others, it is by standing upon the shoulders of giants" - Isaac Newton

“We build too many walls and not enough bridges.” - Isaac Newton
filipematos
down-Quark!
down-Quark!
 
Mensagens: 280
Registado: Sábado Jun 25, 2011 4:48 pm
Localização: Lisboa

Re: Somar output de uma função

Mensagempor ruifm em Segunda Fev 06, 2012 12:04 am

filipematos Escreveu:Que distribuição tens? Se tiveres no ubuntu, no centro de programas tens vários "idles" para python e o vidle, tudinho é só instalares!!

eu já consegui a partir do terminal. A instalação na linha de comandos é awesome. Nunca tinha feito uma. Parece que tou a fazer algo mesmo complexo xD
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Re: Somar output de uma função

Mensagempor filipematos em Segunda Fev 06, 2012 11:21 pm

No inicio é um bocado chato... Porque muitos tens que descomprimir e tal tal... São uma data de comandos mas depois com o hábito :)
"If I have seen further than others, it is by standing upon the shoulders of giants" - Isaac Newton

“We build too many walls and not enough bridges.” - Isaac Newton
filipematos
down-Quark!
down-Quark!
 
Mensagens: 280
Registado: Sábado Jun 25, 2011 4:48 pm
Localização: Lisboa

Re: Somar output de uma função

Mensagempor ruifm em Segunda Fev 20, 2012 7:47 pm

pessoal estou com outro problema de memoria, desta vez sem usar recursão...
é em vpython:
http://algol.fis.uc.pt/index.html/viewtopic.php?f=30&t=1076&start=30
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Anterior

Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 1 visitante

cron