ven. 29 octobre 2010, 12h32
Gregory Adam
atoutfox.public.association
Re: Récursivité et stack space
Stack/Queue = pile ou on peut sauver son contexte pour le recharger apres
Stack = LIFO
http://en.wikipedia.org/wiki/Stack_(data_structure)
Queue = FIFO
http://en.wikipedia.org/wiki/Queue_(data_structure)
Stack: operations:
- Push(xx)
- Pop(@m.xx) or Pop()
Queue: operations
- Enqueue(item)
- Dequeue(@m.item)
Une implementation simple des deux
local stackObj
stackObj = createObject('Stack')
?m.stackObj.Push(1)
?m.stackObj.Push(2)
?m.stackObj.Push(3)
?m.stackObj.Push(4)
local x
?m.stackObj.Pop(@m.x)
?x && 4
?m.stackObj.Pop(@m.x)
?x && 3
?m.stackObj.Pop(@m.x)
?x && 2
?m.stackObj.Pop(@m.x)
?x && 1
meme excersice avec Queue
local queueObj
queueObj = createObject('Queue')
?m.queueObj.Enqueue(1)
?m.queueObj.Enqueue(2)
?m.queueObj.Enqueue(3)
?m.queueObj.Enqueue(4)
?m.queueObj.Dequeue(@m.x)
?x && 1
?m.queueObj.Dequeue(@m.x)
?x && 2
?m.queueObj.Dequeue(@m.x)
?x && 3
?m.queueObj.Dequeue(@m.x)
?x && 4
*===============================================================================
*===============================================================================
*===============================================================================
define class Stack as CollectionBase
*-------------------------------------------------------------------------------
function Push(v)
=m.this.Add(m.v)
endfunc
*-------------------------------------------------------------------------------
function Pop(v)
if( empty(m.this.Count) )
return FALSE
endif
v = m.this.Item(m.this.Count)
=m.this.Remove(m.this.Count)
endfunc
*-------------------------------------------------------------------------------
function Peek(v)
if( empty(m.this.Count) )
return FALSE
endif
v = m.this.Item(m.this.Count)
endfunc
*-------------------------------------------------------------------------------
*-------------------------------------------------------------------------------
enddefine
*===============================================================================
*===============================================================================
*===============================================================================
*===============================================================================
*===============================================================================
*===============================================================================
define class Queue as CollectionBase
*-------------------------------------------------------------------------------
function EnQueue(v)
=m.this.Add(m.v)
endfunc
*-------------------------------------------------------------------------------
function DeQueue(v)
if( empty(m.this.Count) )
return FALSE
endif
v = m.this.Item(1)
=m.this.Remove(1)
endfunc
*-------------------------------------------------------------------------------
function Peek(v)
if( empty(m.this.Count) )
return FALSE
endif
v = m.this.Item(1)
endfunc
*-------------------------------------------------------------------------------
enddefine
*===============================================================================
*===============================================================================
*===============================================================================
*===============================================================================
*===============================================================================
*===============================================================================
define class CollectionBase as Collection
*-------------------------------------------------------------------------------
function Clear()
=m.this.Remove(-1)
endfunc
*-------------------------------------------------------------------------------
function Empty()
return empty(m.this.Count)
endfunc
*-------------------------------------------------------------------------------
enddefine
*===============================================================================
*===============================================================================
*===============================================================================
Gregory
__
"luc Gilot" wrote in message news:iae653$1mri$1@news.niouzes.net...
Merci pour vos réponses.
* Changer le nb de variables ne change rien (non plus que de diminuer la
longueur de leurs noms ou de celui de la fonction récursive : il fallait
quand même essayer...)
* Grégory qu'est-ce qu'un stack ou queue ?
Luc
"luc Gilot" <luc.gilot@limoog.net> a écrit dans le message de news:
iae0jb$1ivi$1@news.niouzes.net...
> Bonjour
>
> Je dois écrire un programme très récursif (environ 2000 niveaux de
> profondeur).
> Un premier réglage de STACKSIZE = ... dans config.fpw m'a permis d'éviter
> le message "Trop de DO imbriqués" à une profondeur de 119.
> J'arrive maintenant à une profondeur de 437 avec un message "Espace pile
> insiffisant"
>
> Comment augmenter la taille de la pile, ou faire en sorte qu'elle se
> remplisse moins vite (à part en ne faisant plus de récursivité!) ?
>
> Luc
>
Permalink : http://www.atoutfox.org/nntp.asp?ID=0000004275