Re: [python-brasil] Codigo QuickSort
Rodrigo Senra
On 1Sep 2005, at 5:43 PM, reis_oli wrote:
> TEnho este codigo, porém não tenho exito com sua Main(),
Em C terá muito mais êxito com main() do que com Main()
> Será que
> Alguem pode me Ajudar.
Claro, mas por aqui é assim que se faz um quicksort ;o)
from array import array
import copy
import profile
def quick_sort(seq,left,right,debug):
"Rotina recursiva"
n = len(seq)
if left<right:
if seq[left]>seq[right]:
swap(seq,left,right,debug)
j = left
k = right
while 1:
while 1:
j=j+1
if seq[j]>=seq[left]:
break
while 1:
k =k-1
if seq[k]<=seq[left]:
break
if j<k:
swap(seq,j,k,debug)
if (j>k):
break
swap(seq,left,k,debug)
quick_sort(seq,left,k-1,debug)
quick_sort(seq,k+1,right,debug)
def swap(seq,x,y,debug):
"""Rotina para fazer trocas entre dois elementos de um vetor.
Agora, se quiser fazer um quicksort animado, basta alterar aqui!"""
if debug:
print seq, 'swap', seq[x], seq[y]
aux = seq[x]
seq[x] = seq[y]
seq[y] = aux
def quicksort(seq,debug=0):
" Só para embelezar a chamada inicial"
quick_sort(seq,0,len(seq)-1,debug)
sequencia = array('i', [40,15,30,25,60,10,75,45,65,35,50,20,70,55])
quicksort(sequencia, debug=1)
[]s
Senra
Rodrigo Senra
______________
rsenra @ acm.org
http://rodrigo.senra.nom.br
===============================================================
Antes de enviar sua mensagem dê uma lida em:
http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar
===============================================================
Links do Yahoo! Grupos
<*> Para visitar o site do seu grupo na web, acesse:
http://br.groups.yahoo.com/group/python-brasil/
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@yahoogrupos.com.br
<*> O uso que você faz do Yahoo! Grupos está sujeito aos:
http://br.yahoo.com/info/utos.html
nalon
> Claro, mas por aqui é assim que se faz um quicksort ;o)
A concisão dos algoritmos básicos foi o que
me conquistou em Python. O algoritmo que o
Senra colocou tem a enorme vantagem de fa-
zer a ordenação in-loco, mas o algoritmo abai-
xo é melhor para mostrar a lógica da coisa.
---
def quicksort(l):
if l:
left = [ x for x in l if x < l[0] ]
right = [ x for x in l if x >= l[0] ]
return quicksort(left) + quicksort(right)
else:
return []
---
Obs.: não posso testar a implementação agora,
pois a máquina de onde escrevo não tem Python
instalado, mas o código real, se esse daí não
funcionar, é semelhante.
Sete linhas pra implementar o algoritmo, é real-
mente elegante. As outras linguagens que eu
conheço que suprem essa concisão são Prolog
e Lisp. Sem dúvida existem outras, mas com
certeza são todas linguagens de altíssimo nível.
Não é a toa que Python é apaixonante. :)
---
José Alexandre Nalon
na...@terra.com.br
Rodrigo Senra
On 2Sep 2005, at 10:11 AM, João Paulo Fernandes Farias wrote:
> Opa!
>
> Eu adaptei o teu código pra funcionar, ficou assim:
>
> >>> def quicksort(l):
> if l:
> left = [x for x in l if x < l[0]]
> right = [x for x in l if x > l[0]]
> if len(left) > 1:
> left = quicksort(left)
> if len(right) > 1:
> right = quicksort(right)
> return left + [l[0]] * l.count(l[0]) + right
> return []
>
> >>> quicksort(lista)
> [0, 1, 2, 3, 3, 4, 5, 7, 8, 8, 9, 9, 12, 13, 85, 99]
> >>> lista
> [1, 5, 3, 9, 2, 4, 8, 7, 3, 9, 8, 12, 13, 0, 99, 85]
>
Legal, gostei muito desta evolução, muito melhor, show galera!!!
Só faria uma leve alteração, para ganhar um pouco mais
de desempenho e quiçá um nanotico a mais de clareza.
def quicksort2(l):
if l:
pivot = l[0]
left = [x for x in l if x < pivot]
right = [x for x in l if x > pivot]
if len(left) > 1:
left = quicksort2(left)
if len(right) > 1:
right = quicksort2(right)
return left + [pivot] * l.count(pivot) + right
return []
Como l[0] implica em uma chamada de função por baixo dos panos,
o uso de um alias (pivot) economiza esta chamada, o que pode significar
alguns segundos economizados.
Dizem as más línguas que o Heapsort pode dar um coro no quicksort,
ainda que no caso médio ambos tenham a mesma complexidade teórica O
(n*log_n)
Abração,
Senra
Rodrigo Senra
______________
rsenra @ acm.org
http://rodrigo.senra.nom.br
João Paulo Fernandes Farias
Eu adaptei o teu código pra funcionar, ficou assim:
if l:
left = [x for x in l if x < l[0]]
if len(left) > 1:
left = quicksort(left)
if len(right) > 1:
right = quicksort(right)
return left + [l[0]] * l.count(l[0]) + right
return []
>>> quicksort(lista)
[0, 1, 2, 3, 3, 4, 5, 7, 8, 8, 9, 9, 12, 13, 85, 99]
>>> lista
[1, 5, 3, 9, 2, 4, 8, 7, 3, 9, 8, 12, 13, 0, 99, 85]
--
JP
| Yahoo! Grupos, um serviço oferecido por: | |
|
Links do Yahoo! Grupos
- Para visitar o site do seu grupo na web, acesse:
http://br.groups.yahoo.com/group/python-brasil/
- Para sair deste grupo, envie um e-mail para:
python-brasi...@yahoogrupos.com.br
- O uso que você faz do Yahoo! Grupos está sujeito aos Termos do Serviço do Yahoo!.
Mario Domenech Goulart
On Sun, 4 Sep 2005 04:58:47 +0000 (GMT) Johann Peter Gustav Lejeune Dirichlet <peterdiri...@yahoo.com.br> wrote:
> Bem, eu nao sei se Python sofre com tal limitacao.
Sim, sofre.
> Teoricamente a lista teria que ter um tamanho gigantesco para dar uma
> especie de pau deste tipo.
Nem precisa ser tão grande:
>>> import sys
>>> sys.getrecursionlimit()
1000
Com 1001 elementos já pode-se ter um erro.
> E isto aconteceria em qualquer linguagem com suporte a recursao.
Não. Linguagens que implementam "tail call optimization" ** não sofrem
deste mal.
Em http://mail.python.org/pipermail/python-dev/2004-July/046201.html há
uma discussão sobre isso, relacionada a Python.
** há alguma tradução "oficial" para o termo "tail" neste contexto?
Cauda?
> Mas acho que ha um modo nao-recursivo de fazer tal algoritmo, mas nada
> garante que este algoritmo sera mais rapido ou consumira menos
> memoria.
Sim, mas a tarefa de converter chamadas recursivas em iterações deveria
ficar a cargo do interpretador, não do programador. Se o computador
pode fazer isso, por que eu deveria fazer? :-)
Um abraço.
Mario
Nilton Volpato
def qsort(L):
if L == []: return []
return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \
qsort([x for x in L[1:] if x>=L[0]])
Entretanto, como o pessoal já notou, essa versão recursiva (e os
outros exemplos aqui) pode estourar o limite máximo da pilha do
python.
Outro detalhe importante é a escolha do pivô. Para essa escolha
específica (L[0]), um pior caso para o quicksort é quando a lista está
ordenada, levando tempo O(n**2).
Como o pessoal já disse também, o caso médio do quicksort é O(n log n)
e o pior caso O(n**2), o que faz com que a escolha do pivô seja um
assunto crucial na eficiência do algoritmo. Se o pivô fosse
L[len(L)//2] ao invés de L[0], a ordenação de uma lista já ordenada
não levaria tempo n**2, mas existiria um outro caso (talvez menos
comum, no qual o quicksort levaria o tempo do pior caso novamente).
Ainda sobre a escolha do pivô, existe um algoritmo para a seleção do
k-ésimo, em tempo linear (i.e., o algoritmo retorna o elemento que
estaria na posição k da lista, sem ordenar a lista (que obviamente
levaria tempo n.log(n))). E esse algoritmo pode ser usado para
implementar um quicksort com tempo de pior caso O(n log n).
Apesar de o algoritmo de seleção do k-ésimo ser muito útil, na prática
não compensa. Já que existem algoritmos de ordenação em tempo O(n
log(n)) no pior caso, como o mergesort.
O algoritmo de ordenação do python é uma variante do mergesort. Aliás,
muito bem otimizado. Para uma lista ordenada, ele leva tempo apenas
linear. E é muito eficiente para listas parcialmente ordenadas também.
Abaixo a implementação do mergesort (fonte wikipedia):
def sort(array):
if len(array) <= 1: return array
mid = len(array) // 2
return merge (sort(array[0:mid]), sort(array[mid:]))
def merge(a, b):
if len(a) == 0: return b
if len(b) == 0: return a
if a[0] <= b[0]: return a[0:1] + merge(a[1:], b)
else: return b[0:1] + merge(a, b[1:])
Onde merge, é uma função auxiliar, que cria uma lista ordenada a
partir de outras duas. Essa implementação do merge do wikipedia é bem
ruim por sinal...
-- Nilton
Em 03/09/05, Rodrigo Senra<rse...@acm.org> escreveu:
Rodrigo Senra
On 4Sep 2005, at 1:58 AM, Johann Peter Gustav Lejeune Dirichlet wrote:
> Bem, eu nao sei se Python sofre com tal limitacao.
Sofre.
> Teoricamente a lista teria que ter um tamanho
> gigantesco para dar uma especie de pau deste tipo.
Bom, depende do que vc chama de gigantesco.
O seguinte seria suficiente para dar pau:
sample = range(sys.getrecursionlimit()+1)
sample.reverse() # garante pior caso para quicksort que pega pivot = l
[0]
quicksort(sample)
> E isto aconteceria em qualquer linguagem com suporte a
> recursao.
Eventualmente sim, dada um conjunto de dados suficientemente grande
e uma memória suficientemente pequena ;o)
> Ah, Heapsort e um algoritmo O(n*logn) mas o caso medio
> dele e mais lento (por uma constante) que o do
> Quicksort (que e O(n^2)).
Desculpe mas há um engano aqui.
O caso médio do quicksort também é O(n*lg n), assim como
o heapsort. O quicksort só é O(n**2) no seu pior caso.
E tem mais, o quicksort só é O(n*lg n) se for garantido o
balanceamento do particionamento. Existe uma versão mais
complicada do algoritmo (randomized quicksort) que tenta garantir
isso, caso contrário seu comportamento assintótico degenera em
direção ao pior caso O(n**2).
Dê uma olhadela só em:
Heapsort /versus/ Quicksort
http://www.ic.unicamp.br/~fkm/seminarios/stolfi4.txt
> E como é que fica a questão da recursão? Estratégias
> recursivas em Python ficam limitadas ao tamanho da pilha. No caso
> do quicksort, o uso de uma lista muito grande como entrada causará
> um erro
> em tempo de execução.
Sem dúvida alguma.
> Como é que o pessoal costuma contornar esse
> problema?
Python vem com um algoritmo de ordenação híbrido super-otimizado,
de forma que eu nunca precisei de algo muito diferente. Exceto talvez
quando as chaves do processo de ordenação são números inteiros em um
intervalo conhecido. Nestes casos é possível aplicar algoritmos de
ordenação
em tempo linear O(n), usando combinações de bucketsort, radixsort e
countingsort.
Abração,
Senra
Rodrigo Senra
______________
rsenra @ acm.org
http://rodrigo.senra.nom.br
===============================================================
Antes de enviar sua mensagem dê uma lida em:
http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar
===============================================================
Links do Yahoo! Grupos
<*> Para visitar o site do seu grupo na web, acesse:
Mario Domenech Goulart
> > E como é que fica a questão da recursão? Estratégias
> > recursivas em Python ficam limitadas ao tamanho da pilha. No caso
> > do quicksort, o uso de uma lista muito grande como entrada causará
> > um erro
> > em tempo de execução.
>
> Sem dúvida alguma.
>
> > Como é que o pessoal costuma contornar esse
> > problema?
>
> Python vem com um algoritmo de ordenação híbrido super-otimizado,
> de forma que eu nunca precisei de algo muito diferente. Exceto talvez
> quando as chaves do processo de ordenação são números inteiros em um
> intervalo conhecido. Nestes casos é possível aplicar algoritmos de
> ordenação
> em tempo linear O(n), usando combinações de bucketsort, radixsort e
> countingsort.
Sim, o de ordenação, ok. Mas e no caso geral, com qualquer algoritmo recursivo?
Um quebra-galho temporário seria algo como:
import sys
def rec():
try:
rec()
except RuntimeError:
sys.setrecursionlimit(sys.getrecursionlimit() * 2)
print sys.getrecursionlimit()
rec()
rec()
Que, além de feio :-), apenas posterga o problema:
$ python rec.py
2000
4000
8000
16000
32000
64000
Segmentation fault (core dumped)
Sei que isso se deve à forma como o interpretador é implementado. A
única solução (me
corrijam se eu estiver errado) é transformar as chamadas recursivas em
iterações (no
caso do exemplo, seria algo como "while True: pass").
Gostaria de saber quais as alternativas comumente usadas para amenizar
o problema.
Um abraço.
Mario
Rodrigo Senra
On 5Sep 2005, at 9:26 PM, Leonardo Santagada wrote:
> O gente, só um cuidado, caso médio é o O (ó grande) o pior caso é T
> (na verdade theta mas eu não tenho um teclado q divite isso). Tem
> também o gamma que é o melhor caso. Então pior caso não é O(n*log(n))
> e sim da ordem de n*loh(n). Só um detalhe de notação, e eu estou sendo
> chato mas tudo bem.
Oi Leo,
vc não está sendo chato. Me desculpe, mas há um equívoco =)
Dizer que uma f(n) é O(g(n)) significa pela definição
que existe um valor K do domínio de f(n) a partir do qual
vale 0<= f(n) <= c* g(n) para todo n>K.
Dizer que uma f(n) é Theta(g(n)) significa
que existe um valor K do domínio de f(n) a partir do qual
vale 0<= c1*g(n) <= f(n) <= c2* g(n) para todo n>K.
A interpretação de f(n)=O(g(n)) pode ser que dizer existe uma família
de funções g(n) que limitam superiormente f(n) a partir de um dado
valor.
Esse limite dá uma idéia sobre como é o crescimento da função f(n).
No caso da funcão Theta, essa família limita tanta superiormente quanto
inferiormente, escolhidas constantes apropriadas.
A notação assintótica é uma aproximação matetmática para a comparação
entre o crescimento de duas funções, ela não diz nada a respeito de pior
ou melhor caso.
Quando se quer fazer uma análise de pior caso, se fazem algumas
suposições
e se trabalha em uma formulação matetmática. Pode-se obter o,O,Theta
dependendo de quão boa for a aproximação no caso estudado.
Não faz sentido dizer que : caso médio é O e pior caso é Theta!
Tudo depende de quão boa é sua aproximação matemática.
Além do mais, pela definição, toda função que é Theta(g(n)) é também
O(g(n)). Significa que quem fez uma demonstração Theta(g(n)) fez uma
aproximação melhor.
E de fato existe uma demonstração do quicksort recursivo com
complexidade
Theta(n**2) para pior caso [1].
Existe ainda a notação Gamma, que é análoga mas descreve um limite
inferior. Ao invés de dizer algo sobre o algoritmo, *geralmente* a
notação Gamma é usada
para descrever algo sobre __o problema__. Ou seja qual é o esforço
mínimo que um
algoritmo deve fazer para resolver um dado problema, definindo assim
um critério de
optimalidade.
Por exemplo, qualquer algoritmo para identificar o máximo de um
conjunto deve
examinar no mínimo todos os elementos do conjunto (se 1 for deixado
de fora
este poderia ser o máximo), logo o limite inferior *do problema* de
cálculo de máximo
é Gamma(n).
> O sort do python usa o algoritmo Tim Sort, q é uma mistureba de um
> monte de coisas, mas que funciona e é rapido pacas. Eu coloquei um
> link para a documentação na outra thread sobre sort, então não vou
> repetir.
Obrigado pelo link, show! Tim rules!
[1] Introduction to Algorithms - Thomas Cormen, Charles Leiserson,
Ronald Rivest,
Cliford Stein - MIT Press
Johann Peter Gustav Lejeune Dirichlet
Esta historia de "Last Call Optimization" é típica do
GCC, mas isto é "dependente de código". Um Fibonacci
recursivo feito em C mata a memória bem rápido, e o
GCC tem este suporte...
Pelo que eu saiba, a "recursao de cauda" (ou
otimizacao de ultima chamada recursiva, que seria um
bom nome oficial...) é feita quando o compilador vê
que ele nao precisa retornar para as chamadas
recursivas anteriores. E isto só acontece em
determinados tipos de chamada (tem uma pequena lista
de requisitos para isto dar certo, pelo menos do que
sei de C e de Prolog...).
De certo modo, a tarefa poderia ser do tradutor, mas
nao sei se a linguagem C e mais poderosa que a
linguagem de montagem, no sentido de implementar
recursões em tempo aceitável, com um desempenho menos
preocupante. Por exemplo, em Linguagem de Montagem e
mesmo em certas linguagens de nivel mais alto, nao se
implementa recursao. Fazer um Quicksort nestes casos é
um porre! Ter que criar uma pilha, escolher o que
empilhar, criar pontos de retorno, torcer para ter
memoria suficiente...
Talvez dê para fazer uma biblioteca ou modulo que
cuide destes detalhes... Mas isto poderia evoluir para
coisas meio doidas, como a famosa frase "Recursao e
Tudo!" que todos que conhecem Prolog ja devem ter
ideia...
--- Mario Domenech Goulart <mario....@gmail.com>
escreveu:
---------------------------------
Alô Johann
Sim, sofre.
>>> import sys
>>> sys.getrecursionlimit()
1000
Um abraço.
Mario
===============================================================
http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar
===============================================================
Yahoo! Grupos, um serviço oferecido
por: PUBLICIDADE
var lrec_target="_blank";var lrec_URL=new
Array();lrec_URL[1]="http://br.rd.yahoo.com/SIG=12ffuqcgj/M=365837.7000707.7924794.2369893/D=brclubs/S=2137111259:HM/Y=BR/EXP=1125848959/A=2950750/R=0/id=flashurl/SIG=10tift5qr/*http://br.movies.yahoo.com/";var
lrec_flashfile="http://br.i1.yimg.com/br.yimg.com/i/br/ads6/0901_lrec_cinema_calendario.swf?clickTAG=javascript:LRECopenWindow(1)";var
lrec_altURL="http://br.rd.yahoo.com/SIG=12ffuqcgj/M=365837.7000707.7924794.2369893/D=brclubs/S=2137111259:HM/Y=BR/EXP=1125848959/A=2950750/R=1/id=altimg/SIG=10tift5qr/*http://br.movies.yahoo.com/";var
lrec_altimg="http://br.i1.yimg.com/br.yimg.com/i/br/ads6/0829_lrec_cinema_calendario.gif";var
lrec_width=300;var lrec_height=250;
---------------------------------
Links do Yahoo! Grupos
Para visitar o site do seu grupo na web, acesse:
http://br.groups.yahoo.com/group/python-brasil/
Para sair deste grupo, envie um e-mail para:
python-brasi...@yahoogrupos.com.br
O uso que você faz do Yahoo! Grupos está sujeito
aos Termos do Serviço do Yahoo!.
_______________________________________________________
Yahoo! Messenger com voz: PROMOÇÃO VOCÊ PODE LEVAR UMA VIAGEM NA CONVERSA. Participe! www.yahoo.com.br/messenger/promocao
Nilton Volpato
Dirichlet<peterdiri...@yahoo.com.br> escreveu:
[...]
> Pelo que eu saiba, a "recursao de cauda" (ou
> otimizacao de ultima chamada recursiva, que seria um
> bom nome oficial...) é feita quando o compilador vê
[...]
> De certo modo, a tarefa poderia ser do tradutor, mas
> nao sei se a linguagem C e mais poderosa que a
> linguagem de montagem, no sentido de implementar
> recursões em tempo aceitável, com um desempenho menos
> preocupante. Por exemplo, em Linguagem de Montagem e
> mesmo em certas linguagens de nivel mais alto, nao se
> implementa recursao. Fazer um Quicksort nestes casos é
> um porre! Ter que criar uma pilha, escolher o que
> empilhar, criar pontos de retorno, torcer para ter
> memoria suficiente...
[...]
Acho que o cúmulo da recursão é implementar recursivamente funções que
não precisam de pilha para serem implementadas iterativamente. É o
caso do Fibonacci, no qual um loop simples já resolve. O quicksort por
exemplo, precisa. Abaixo uma versão iterativa do quicksort e que não
sofre dos problemas com o limite máximo de recursões do python.
def qsort(lst, left, right):
pilha = []
pilha.append( (left, right) )
while pilha:
left, right = pilha.pop()
if left + 1 < right:
pivo = lst[left]
lst1 = [ x for x in lst[left+1:right] if x < pivo ]
lst2 = [ x for x in lst[left+1:right] if x >= pivo ]
lst[left:right] = lst1 + lst[left:left+1] + lst2
pilha.append( (left, left+len(lst1)) )
pilha.append( (left+len(lst1)+1, right) )
return lst
Ahh, a chamada inicial deveria ser qsort(lst, 0, len(lst)).
Abraços,
-- Nilton
Leonardo Santagada
(na verdade theta mas eu não tenho um teclado q divite isso). Tem
também o gamma que é o melhor caso. Então pior caso não é O(n*log(n))
e sim da ordem de n*loh(n). Só um detalhe de notação, e eu estou sendo
chato mas tudo bem.
se me lembro bem ele conclui que na maquina dele o merge sort era o
mais rapido, depois vinha o heapsort e depois o quicksort (mas eu
posso estar bem enganado).
O sort do python usa o algoritmo Tim Sort, q é uma mistureba de um
monte de coisas, mas que funciona e é rapido pacas. Eu coloquei um
link para a documentação na outra thread sobre sort, então não vou
repetir.
Em 05/09/05, Johann Peter Gustav Lejeune
Dirichlet<peterdiri...@yahoo.com.br> escreveu:
>
> > Ah, Heapsort e um algoritmo O(n*logn) mas o caso
> medio
> > dele e mais lento (por uma constante) que o do
> > Quicksort (que e O(n^2)).
>
> Desculpe mas há um engano aqui.
> O caso médio do quicksort também é O(n*lg n), assim
> como
> o heapsort. O quicksort só é O(n**2) no seu pior caso.
> >>>>Vou me explicar:
> O Quicksort tem um caso terrivel:
> (2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2),
> ou
> (1,2,3,4,5,6,7,8,9,10,100,1000,10000,1000000,1 mol)
>
> Mas este e um caso extremamente patologico, e isto
> raramente acontece na pratica.
> O caso do heapsort e que ele garante o tempo O(n*log
> n) em qualquer caso, mas na media o quicksort e mais
> rapido apenas por umas constantes.
>
--
Leonardo Santagada (http://www.lomohomes.com/retype)
"Documentation is like sex: When it is good, it is VERY good; and when
it's bad, it's still better than nothing at all." (Dick Brandon)
José Alexandre Nalon
> Acho que o cúmulo da recursão é implementar recursivamente funções que
> não precisam de pilha para serem implementadas iterativamente. É o
> caso do Fibonacci, no qual um loop simples já resolve.
Na verdade, qualquer função recursiva pode ser implemen-
tada de maneira não-recursiva. Se não fosse assim, algu-
mas funções recursivas jamais poderiam ser implementadas
computacionalmente. Isso porque se os algoritmos preci-
sam ser executados, então em alguma instância haverá a
execução de código de máquina, que é sequencial por na-
tureza. Existem diversas técnicas para tornar algorit-
mos recursivos em interativos.
A grande beleza de algoritmos recursivos é mostrar a na-
tureza da idéia. Algoritmos simples como o da seqüência
de Fibonacci não mostram o poder, mas mais complexos co-
mo o quicksort ou transformada de Fourier ficam _bem_
mais legíveis e fáceis de entender.
O grave problema da recursão é a chamada explosão combi-
natorial. Afinal, a cada chamada da função você pode ge-
rar mais chamadas, resultando num estouro de memória ou
outro problema semelhante. (A seqüência de Fibonacci é
interessante porque algumas implementações podem gerar
um número de chamadas igual a própria seqüência!)
Nem toda função recursiva pode sofrer eliminação de re-
cursão de cauda, mas é uma característica interessante
que eu gostaria de ver em Python. É uma daquelas coisas
que é lugar-comum em linguagens lógicas e funcionais que
eu realmente acredito que Python tem como implementar.
Alguém já pensou em sugerir isso para os desenvolvedores?
--
José Alexandre Nalon
na...@terra.com.br
Condector
algoritmo para o quicksort em 3 linhas:
def quicksort(L):
if L==[]: return []
return quicksort([x for x in L[1:] if x < L[0]]) + L[0:1] +
quicksort([x for x in L[1:] if x >= L[0] ])
Usando um pouquinho de lista de compreensão temos esse quick minusculo.
A claro, esse código não é meu, eu encontrei e o estudei e ele estava
na wikipédia.
[]´s
Brivaldo.
Em 06/09/05, Mario Domenech Goulart<mario....@gmail.com> escreveu:
> Alô Nalon,
>
> On Tue, 06 Sep 2005 09:28:55 +0000 José Alexandre Nalon
> <na...@terra.com.br> wrote:
>
> >> Acho que o cúmulo da recursão é implementar recursivamente funções que
> >> não precisam de pilha para serem implementadas iterativamente. É o
> >> caso do Fibonacci, no qual um loop simples já resolve.
> >
> > Na verdade, qualquer função recursiva pode ser implemen-
> > tada de maneira não-recursiva. Se não fosse assim, algu-
> > mas funções recursivas jamais poderiam ser implementadas
> > computacionalmente. Isso porque se os algoritmos preci-
> > sam ser executados, então em alguma instância haverá a
> > execução de código de máquina, que é sequencial por na-
> > tureza. Existem diversas técnicas para tornar algorit-
> > mos recursivos em interativos.
>
> Iterativos, não?
>
>
> > Nem toda função recursiva pode sofrer eliminação de re-
> > cursão de cauda, mas é uma característica interessante
> > que eu gostaria de ver em Python. É uma daquelas coisas
> > que é lugar-comum em linguagens lógicas e funcionais que
> > eu realmente acredito que Python tem como implementar.
> > Alguém já pensou em sugerir isso para os desenvolvedores?
>
> Sim, mas a ideia não agrada ao van Rossum. A thread em
> http://mail.python.org/pipermail/python-dev/2004-July/046201.html
> apresenta algumas argumentações.
>
> Um abraço.
> Mario
>
>
>
> ===============================================================
>
> Antes de enviar sua mensagem dê uma lida em:
>
>
> http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar
>
> ===============================================================
>
>
>
>
> Yahoo! Grupos, um serviço oferecido por:
>
> PUBLICIDADE
>
> ________________________________
> Links do Yahoo! Grupos
>
>
> Para visitar o site do seu grupo na web, acesse:
> http://br.groups.yahoo.com/group/python-brasil/
>
> Para sair deste grupo, envie um e-mail para:
> python-brasi...@yahoogrupos.com.br
>
> O uso que você faz do Yahoo! Grupos está sujeito aos Termos do Serviço do
> Yahoo!.
--
Debian Linux e você, tudo a ver.
Nilton Volpato
[...]
> usa uma pilha. Agora cuidado, o dominio dos problemas que podem ser
> resolvidos recursivamente é maior do que o dos iterativos, isto é, NÃO
> é possivel representar todos os programas recursivos em iterativos.
Todo programa recursivo pode ser escrito de maneira iterativa, com
(talvez) o uso de uma pilha auxiliar, desde que seu modelo
computacional possua memória disponível (possivelmente infinita, como
no caso das máquinas de Turing). E como é o caso dos nossos
computadores digitais que possuímos sobre nossas mesas. Então, num
computador digital, como esses que usamos, qualquer função recursiva
pode ser convertida em iterativa.
> Ex: Numa maqui com 2 operações somar/subtrair 1 e um teste (ver se o
> registrador é zero), que tenha 1 registrador e nada de memória ou
> qualquer outra coisa, tu pode implementar um monte de funções
> recursivas e quase nada util iterativamente (se me lembro bem essa
> maquina é universal). Em python poderiamos fazer algo assim (se a
> maquina além dessas duas operações tivesse um interpretador de python
> :):
Mas nesse caso o modelo computacional é muito restrito. Não há
memória, apenas um único registrador para um número inteiro. Mesmo
assim, o conjunto de funções computáveis nesse modulo é o mesmo
conjunto de funções computáveis numa máquina de Turing.
Interessantemente, esse conjunto de tem o nome de funções recursivas.
Esse nome é usado tanto num modelo recursivo (como esse), como num
modelo iterativo, como de uma máquina de Turing.
O legal desse modelo é que apesar de não apresentar memória alguma
(apenas um único registrador), ele pode computar qualquer função
computável por uma máquina de Turing. Numa ótica um pouco mais
direcionada à implementação física do modelo, você poderia pensar que
ele também tem uma memória infinita para implementar a pilha de
chamadas das funções.
Não é muito difícil fazer uma redução de um programa genérico desse
modelo restrito de máquina com recursão para o modelo de uma máquina
de Turing. (Se alguém estiver interessado posso explicar essa
redução). Isso mostra que qualquer um desses programa pode ser
implementado sem recursão numa máquina de Turing. Claro que nesse
mesmo modelo não daria, porque não haveria nenhum registrador
adicional para controlar um loop ou coisa do gênero.
> def multiplica_por_2():
> "multiplica o registrador por 2"
> registrador -= 1
> if not registrador == 0:
> multiplica_por_2
> registrador +=1
> registrador +=1
>
> tente escrever a mesma função sem ser recursiva (é impossivel)
Essa é fácil, essa função está na verdade apenas somando 1. :-)
Não sei como ficaria uma função para calcular o dobro, mas é provável
que a recursão seja essencial para multiplicar por 2 nesse modelo (e
pra fazer outras coisas complexas também), mas não num modelo de
máquina de Turing. Se você tiver a implementação correta desse
multiplica por 2, acho que seria interessante ver...
Abraços,
-- Nilton
Leonardo Santagada
emails ein? Dai fica dificil bater o teu material :). Tá gente nunca
fui muito fã do tenembaum, principalmente pq ele tem um livro de
estruturas de dados em Pascal e o nosso professor era um tapado que
chegou a tirar os livros do knuth das leituras recomendadas e só dava
coisas do livro dele.
Sobre o knuth, ele é um gênio, meio charope, mas tu encontra tudo no
livro dele e ele só usa recursão no quick sort e na verdade mesmo ele
usa uma pilha. Agora cuidado, o dominio dos problemas que podem ser
resolvidos recursivamente é maior do que o dos iterativos, isto é, NÃO
é possivel representar todos os programas recursivos em iterativos.
registrador é zero), que tenha 1 registrador e nada de memória ou
qualquer outra coisa, tu pode implementar um monte de funções
recursivas e quase nada util iterativamente (se me lembro bem essa
maquina é universal). Em python poderiamos fazer algo assim (se a
maquina além dessas duas operações tivesse um interpretador de python
:):
def multiplica_por_2():
"multiplica o registrador por 2"
registrador -= 1
if not registrador == 0:
multiplica_por_2
registrador +=1
registrador +=1
tente escrever a mesma função sem ser recursiva (é impossivel)
ps: Se estiver alguma coisa errado pode me corrigir
--
Leonardo Santagada (http://www.lomohomes.com/retype)
"Documentation is like sex: When it is good, it is VERY good; and when
it's bad, it's still better than nothing at all." (Dick Brandon)
Leonardo Santagada
registrador = 5 # número inicial
def multiplica_por_2():
"multiplica o registrador por 2"
global registrador
registrador -= 1
if not registrador == 0:
multiplica_por_2()
registrador +=1
registrador +=1
É só rodar q tu vai ver q ela multiplica mesmo por 2.
obs: Nessa maquina o registrador é um número natural infinito, então
não tente dizer q não funciona se for 0 ou se o número for grande
demais... pq na maquina teorica funcionaria.
É esse modelo é mais restrito com certeza do que um computador
digital, agora falta saber se num digital tb dá pra implementar tudo
sem recursão. Aparentemente tu pode sempre usar uma pilha para simular
a recursão, mas eu não tenho certeza se são equivalentes, o Senra
talvez saiba.
--
Leonardo Santagada (http://www.lomohomes.com/retype)
"Documentation is like sex: When it is good, it is VERY good; and when
it's bad, it's still better than nothing at all." (Dick Brandon)
Nilton Volpato
Em 09/09/05, Leonardo Santagada<sant...@gmail.com> escreveu:
> Saindo de uma seção elucidativa no interpretador:
>
> registrador = 5 # número inicial
>
> def multiplica_por_2():
> "multiplica o registrador por 2"
> global registrador
> registrador -= 1
> if not registrador == 0:
> multiplica_por_2()
> registrador +=1
> registrador +=1
>
> É só rodar q tu vai ver q ela multiplica mesmo por 2.
>
> obs: Nessa maquina o registrador é um número natural infinito, então
> não tente dizer q não funciona se for 0 ou se o número for grande
> demais... pq na maquina teorica funcionaria.
Desculpa foi erro meu mesmo. Depois eu percebi que funcionava sim, mas
só quando já tinha desligado o computador e estava indo dormir. Eu
tinha interpretado mal o modelo, pensei que o registrador entrava na
pilha de chamada também, mas não entra. Esse exemplo funciona certo
mesmo.
> É esse modelo é mais restrito com certeza do que um computador
> digital, agora falta saber se num digital tb dá pra implementar tudo
> sem recursão. Aparentemente tu pode sempre usar uma pilha para simular
> a recursão, mas eu não tenho certeza se são equivalentes, o Senra
> talvez saiba.
Como disse no email anterior: Sim, são equivalentes. Dá pra simular
esse modelo numa máquina de Turing facilmente. O contrário é mais
difícil, mostrar que se pode simular uma máquina de Turing nesse
modelo. Mas só com a primeira parte dá pra mostrar que é possível
eliminar essa recursão numa máquina de Turing.
A redução seria mais ou menos assim (em alto nível):
Vamos chamadar esse modelo restrito com recursão de modelo R. Uma
máquina do modelo R funciona assim, você inicializa o registrador com
um número, inicia a máquina (que roda um determinado programa), espera
a computação, e depois lê o resultado no registrador. (parecido com
uma máquina de Turing)
Imagine que temos uma máquina de Turing com o alfabeto 0,1,#,b (zero,
um, sustenido e branco). Para facilitar, vamor imaginar que a máquina
de turing tem duas fitas também.
Então, dado um programa P (qualquer) para esse modelo R e um número
inteiro que é o valor inicial do registrador, podemos convertê-lo para
uma máquina de Turing da seguinte forma:
Primeiro, convertemos o valor inicial do registrador para a sua
representação binária e colocamos na fita de entrada da máq. de
turing. Depois convertemos um programa da máquina R para um programa
da máquina de turing, da seguinte forma (em alto nível): as operações
de soma, subtração e comparação com zero podem ser facilmente
implementadas numa máquina de turing. Para simular a recursão,
utilizamos a outra fita da máq. de turing. Quando o programa da
máquina R faz uma chamada recursiva a alguma função, a máquina de
turing coloca na segunda fita o símbolo # seguido pelo número do
estado que ela se encontraria se não fizesse a chamada recursiva, e
vai para o estado inicial da função recursiva chamada. Na hora do
retorno da função, a máq. de turing simplesmente olha na segunda fita
para saber qual estado ela terá que voltar e muda para esse estado.
Só isso. E a simulação funciona... :)
Acho que essa discussão era mais adequada para uma lista de
computabilidade... :)
Só pra compensar a falta de python nesse email: python, python,
python, python, python.
:)
Abraço,
-- Nilton
Rodrigo Senra
On 8Sep 2005, at 8:28 PM, Leonardo Santagada wrote:
> Valeu senra, sempre dando aquela pesquisada antes de escrever os
> emails ein?
Essa nem precisou pesquisar pois quando estava dando aulas na PUC
fui remanejado para Analise de Algoritmos e aí tive que bitolar, então
essa parte estava na cache (salvo pela confusão que eu fiz entre o Ômega
e o Gamma -- mas graças a correção do Nilton ninguém saiu ferido).
> Sobre o knuth, ele é um gênio, meio charope, mas tu encontra tudo no
> livro dele e ele só usa recursão no quick sort e na verdade mesmo ele
> usa uma pilha.
Eu prefiro o livro do Cormen (ref em e-mails passados nesta thread)
ao do Knuth, pois o primeiro é mais fácil de ser "digerido" que o
segundo.
Mas concordo que o TAOCP é uma "bíblia".
> Agora cuidado, o dominio dos problemas que podem ser
> resolvidos recursivamente é maior do que o dos iterativos, isto é, NÃO
> é possivel representar todos os programas recursivos em iterativos.
Interessante Leo ! Eu confesso não sou da área de teoria, então
vc teria alguma referência para este resultado ?
Depois depende muito do que vc está chamando de "solução iterativa"
e "solução recursiva".
Vc poderia me dar uma definição de "solução iterativa" ?
Eu definiria o universo de soluções entre recursivas (chamada explícita
de uma função para si mesma) e não-recursivas, onde as recursivas
podem (eu acredito que sempre) ser disfarçadas de não-recursivas
pela eliminação da recursão por uma estrutura de dados
conveniente (usualmente 1 pilha).
Afinal, tudo que é computável hoje por algum computador (exceto talvez
algum experimento quântico) seria computável -- em teoria -- por uma
máquina de Turing, e na máquina de Turing não há suporte explícito para
recursão (pois não tem função nenhuma definida lá para chamar a si
mesma).
Vou tentar provar que vc está enganado:
1) Assumo que o que vc disse é verdade. (Hipótese)
Suponhamos que existem problemas resolvidos computacionalmente
somente por algoritmos recursivos.
2) Sabemos que tudo que é resolvido computacionalmente é resolvido
por uma Máquina de Turing [MdT] (Axioma -- não vou provar isso,
discutir
com Sr.Alan através de sessões espíritas)
3) A MdT não expressa seus algoritmos de forma recursiva, mas sim
através
de um autômato e uma memória infinita (definição de MdT).
3) Considerando 1) e 3) poderia se deduzir que existem problemas
resolvidos
computacionalmente só por algoritmos recursivos (de 1) e que não
são
resolvidos computacionalmente por uma Máquina de Turing (de 3).
Porém "ser resolvido computacionalmente" significa ser
resolvido por
uma Mdt (de 2). Contradição!!!! Isto significa que a hipótese é
FALSA.
> Ex: Numa maqui com 2 operações somar/subtrair 1 e um teste (ver se o
> registrador é zero), que tenha 1 registrador e nada de memória ou
> qualquer outra coisa, tu pode implementar um monte de funções
> recursivas e quase nada util iterativamente (se me lembro bem essa
> maquina é universal). Em python poderiamos fazer algo assim (se a
> maquina além dessas duas operações tivesse um interpretador de python
> :):
>
> def multiplica_por_2():
> "multiplica o registrador por 2"
> registrador -= 1
> if not registrador == 0:
> multiplica_por_2
> registrador +=1
> registrador +=1
Antes de mais nada é preciso fazer duas pequenas correções
no código acima:
1) registrador tem que ser declarado global, senão vc receberia
UnboundLocalError: local variable 'registrador' referenced
before assignment
2) está faltando um () em multiplica_por_2 dentro do if, a
construção está
sintaticamente válida, porém não vai invocar a função apenas
avaliar a referência.
Re-escrevi a versão aplicando estas correções (fui preguiçoso para
manter os nomes hehe):
<code>
reg = 0
def x2():
global reg
reg -= 1
if reg != 0:
x2()
reg += 1
reg += 1
</code>
> tente escrever a mesma função sem ser recursiva (é impossivel)
Eu tenho certeza que *eu* não estou entendendo alguma coisa,
pois eu juraria que o código abaixo faz o mesmo serviço.
>>> def x2():
... return reg + reg
Abração,
Senra
Rodrigo Senra
______________
rsenra @ acm.org
http://rodrigo.senra.nom.br
Leandro Lameiro
> poder computacional do que uma mdt. Pelo que eu li a unica vantagem é
> que os computadores quanticos são extremamente paralelos, fazendo
> problemas que levariam muito tempo (tipo o tempo do universo) levarem
> bem pouco (tipo alguns dias ou em alguns casos segundos).
Nenhum computador consegue computar tudo que uma máquina de turing
computa. Máquinas de Turing tem fita infinita, algo que provavelmente
nunca existirá.
Mesmo a máquina de Turing, que parece absurdamente simples é
completamente abstrata e não tem nenhum correspondente real.
Segundo a wiki (
http://en.wikipedia.org/wiki/Turing_Machine#Comparison_with_real_machines
)
"Turing machines would actually only be equivalent to a machine that
had an unlimited amount of storage space."
Que cara chato! rs
Abraços
Leandro Lameiro
>
>
> --
> Leonardo Santagada (http://www.lomohomes.com/retype)
>
> "Documentation is like sex: When it is good, it is VERY good; and when
> it's bad, it's still better than nothing at all." (Dick Brandon)
>
>
Nilton Volpato
[...]
> > Agora cuidado, o dominio dos problemas que podem ser
> > resolvidos recursivamente é maior do que o dos iterativos, isto é, NÃO
> > é possivel representar todos os programas recursivos em iterativos.
>
> Interessante Leo ! Eu confesso não sou da área de teoria, então
Eu sou :) Faço doutorado em teoria na unicamp/ic.
> vc teria alguma referência para este resultado ?
Dizer "o domínio de problemas que podem ser resolvidos recursivamente
é maior do que os iterativos" é certamente um erro. A frase correta
deveria ser, "num modelo computacional Turing-completo XYZ o domínio
de problemas que podem ser resolvidos recursivamente é maior do que os
iterativos".
Para provar que a primeira frase é falsa é só fornecer um método
formal para transformar qualquer algoritmo definido recursivamente num
algoritmo iterativo. Esse método existe, é similar aquele que eu usei
no email anterior.
Já para provar a segunda afirmação, basta encontrar um modelo
computacional que é Turing-completo no qual não é possível resolver
alguns problemas iterativamente. Esse modelo que o Leonardo mostrou é
um bom candidato para isso. Mas tem um mais amplamente conhecido, o
cálculo lambda[1]. O cálculo lambda é um sistema formal para avaliação
de funções Turing-completo, que usa apenas chamadas de funções, na
verdade tudo é uma função (exceto os identificadores). No cálculo
lambda é evidente que não dá pra resolver alguns problemas
iterativamente, pois não há iteração, e devemos usar apenas chamadas
de função (e recursão).
Entretanto o conjunto de *problemas* que podem ser resolvidos por cada
um dos métodos é exatamente o mesmo. Uma vez que tanto o cálculo
lambda, como uma máquina de Turing são Turing-completos, isto é, têm
poder computacional equivalente ao de uma máquina de Turing.
Outra coisa, se aquele modelo do Leonardo (ML) fosse mais poderoso que
uma máquina de Turing (MT) (iterativa, claro), não seria possível
fazer uma redução de qualquer algoritmo descrito nesse modelo para uma
descrição equivalente (i.e., que dá o mesmo resultado) numa MT. Como é
possível fazer essa redução, isso já prova que o conjunto de problemas
resolvidos pelo ML está contido ou é igual ao resolvido por uma MT, ou
seja ML não fornece poder computacional adicional em relação à MT.
[...]
> Afinal, tudo que é computável hoje por algum computador (exceto talvez
> algum experimento quântico) seria computável -- em teoria -- por uma
> máquina de Turing, e na máquina de Turing não há suporte explícito para
> recursão (pois não tem função nenhuma definida lá para chamar a si
> mesma).
Por uma coinciência, minha área de pesquisa é computação quântica.
Como estamos discutindo apenas computabilidade (isto é, se é possível
resolver o problema ou não, independente do tempo de computação),
posso dizer que o poder computacional de um computador quântico é o
mesmo que de uma máquina de Turing. Por exemplo, mesmo com um
computador quântico não seria possível resolver o problema da parada.
Sinto desapontar os que esperavam que o python v 3915.1alpha pudesse
oferecer maior poder em termos de computabilidade.
Agora em termos de eficiência é outra história, é muito provável que
um computador quântico resolva (e já resolve) problemas de maneira
assintoticamente muito mais rápida que um computador digital clássico.
É isso pessoal, espero ter menos confundido do que explicado.
[1] Isso que originou o nome das funções anônimas em diversas
linguagens, como o lambda do python ou lisp.
Abraços,
-- Nilton
Nilton Volpato
modelo formal teórico e uma implementação física desse modelo.
Máquinas de Turing, circuitos quânticos, máquinas de Turing quânticas,
autômatos de pilha, etc. são todos modelos formais teóricos, têm
memória infinita e não se conta o tempo em segundos (mas em número de
operações básicas)
Pentium 4, computadores digitais, computadores mecânicos movidos à
engrenagens, maquina de Babbage, ábaco, etc. são implementações
físicas de algum modelo e estão sujeitas às limitações impostas pelas
leis da física, têm memória finita e levam um tempo que pode ser
medido em segundos para executar qualquer operação básica.
Ao compará-los devemos comparar apenas modelos teóricos com modelos
teóricos ou modelos físicos com modelos físicos. Mas sabendo que um
modelo físico é uma aproximação (devido às limitações físicas) de um
modelo teórico.
Em 10/09/05, Leandro Lameiro<lam...@gmail.com> escreveu:
> > Só estou chutando, mas acho q nem os computadores quanticos tem mais
> > poder computacional do que uma mdt. Pelo que eu li a unica vantagem é
> > que os computadores quanticos são extremamente paralelos, fazendo
> > problemas que levariam muito tempo (tipo o tempo do universo) levarem
> > bem pouco (tipo alguns dias ou em alguns casos segundos).
É uma concepção errônea comum achar que os computadores quânticos são
paralelos no sentido tradicional, algumas operações podem ser
aplicadas em paralelo, mas o resultado da computação não se torna
disponível para o mundo clássico. Esse tipo de paralelismo por si só
não adicionaria poder computacional aos computadores quânticos. As
regras de análise de algoritmos e notações assintóticas ainda se
aplicam. Por exemplo fatoração de inteiros é feita usando O(2^n)
operações num computador clássico e O(n^3) operações num computador
quântico, por isso é mais rápido. (n é o número de bits do número
sendo fatorado)
> Nenhum computador consegue computar tudo que uma máquina de turing
> computa.
Se você estiver comparando um computador físico com uma máquina de
turing, tudo bem. Mas se estiver comparando uma máquina de turing
quântica (MTQ) com uma máquina de turing (MT), você está enganado,
pois a MTQ computa tudo que a MT computa. Também é verdade que a MT
computa tudo que a MTQ computa. O que pode mudar é o tempo que demora
pra fazer isso.
> Máquinas de Turing tem fita infinita, algo que provavelmente
> nunca existirá.
Certamente nunca existirá. Já que existem limites para a armazenação
de informação no espaço[1]. Por exemplo, estima-se[2] que um
computador de 1 kg, ocupando 1 litro teria no máximo 2.12e31 e seria
capaz de realizar 1e19 operações por bit por segundo.
[...]
É isso. Abraços,
-- Nilton
[1] http://www.crystalinks.com/holouniverse1.html
[2] http://arstechnica.com/wankerdesk/01q2/limits/limits-1.html