Página 2 de 2

Re: Somar output de uma função

MensagemEnviado: Quinta Fev 02, 2012 11:53 pm
por jap
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?

Re: Somar output de uma função

MensagemEnviado: Sexta Fev 03, 2012 6:34 pm
por jap
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.

Re: Somar output de uma função

MensagemEnviado: Sexta Fev 03, 2012 9:31 pm
por ruifm
tenho de ganhar a arte de sintetizar tudo numa linha. isso foisimpcesmente lindo :D

Re: Somar output de uma função

MensagemEnviado: Sexta Fev 03, 2012 10:15 pm
por Tharis
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. ;)

Re: Somar output de uma função

MensagemEnviado: Sábado Fev 04, 2012 7:24 pm
por Bruno Oliveira
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!

Re: Somar output de uma função

MensagemEnviado: Sábado Fev 04, 2012 7:37 pm
por ruifm
nao podem negar que fica lindo e subtil...

Re: Somar output de uma função

MensagemEnviado: Sábado Fev 04, 2012 7:57 pm
por Bruno Oliveira
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:

Re: Somar output de uma função

MensagemEnviado: Sábado Fev 04, 2012 8:37 pm
por ruifm
olhem eu nao sabia se havia de abrir um novo topico para isto.
como acedo ao idle no linux (tou agora a experimentar linux...)

Re: Somar output de uma função

MensagemEnviado: Sábado Fev 04, 2012 9:57 pm
por Tharis
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. ;)

Re: Somar output de uma função

MensagemEnviado: Sábado Fev 04, 2012 10:22 pm
por ruifm
ja consegui :)
o idle da um jeitao!

Re: Somar output de uma função

MensagemEnviado: Domingo Fev 05, 2012 2:15 pm
por filipematos
Que distribuição tens? Se tiveres no ubuntu, no centro de programas tens vários "idles" para python e o vidle, tudinho é só instalares!!

Re: Somar output de uma função

MensagemEnviado: Segunda Fev 06, 2012 12:04 am
por ruifm
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

Re: Somar output de uma função

MensagemEnviado: Segunda Fev 06, 2012 11:21 pm
por filipematos
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 :)

Re: Somar output de uma função

MensagemEnviado: Segunda Fev 20, 2012 7:47 pm
por ruifm
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