PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

sehr einfacher Stapel

https://www.purebasic.fr/german/viewtopic.php?t=29023

Seite 1 von 1

sehr einfacher Stapel

Verfasst: 11.07.2015 13:51
von uweb
Da auch diese Lösung sehr einfach ist und ich mich damit nicht in Tips&Tricks traue formuliere ich es wieder einmal als Frage :
Hat jemand Verbesserungsvorschläge ?

Code: Alles auswählen

; very simple LIFO (LastInFirstOut) based on fix array - no dynamic allocation
; e.g. for Thread-Pool
Global LIFO_Elements = 5, LIFO_Fields=42 ; Base1 because 0 is used by LIFO
Global Dim LIFO(LIFO_Elements,LIFO_Fields) 

Macro LIFO_FirstAvailable : LIFO(0,0) : EndMacro
Macro LIFO_NexAvailable(x) : LIFO(x,0) : EndMacro
Macro LIFO_push(x) : LIFO_NexAvailable(x) = LIFO_FirstAvailable : LIFO_FirstAvailable = x : EndMacro
Macro LIFO_pop(x) : LIFO_FirstAvailable = LIFO_NexAvailable(x) : LIFO_NexAvailable(x) = 0 : EndMacro

; ->>>> LIFO_push(random but only poped) & LIFO_pop(only LIFO_FirstAvailable)

;- Test
#poped = 0
#pushed = 1
#LIFO_TestField = 1

Macro DebugLIFO
      Debug Str(LIFO_FirstAvailable)+"    "+Str(LIFO_NexAvailable(1))+"  "+Str(LIFO_NexAvailable(2))+"  "+Str(LIFO_NexAvailable(3))+"  "+Str(LIFO_NexAvailable(4))+"  "+Str(LIFO_NexAvailable(5))
EndMacro

For i = 1 To 3
    Repeat : x = Random(5,1) : Until LIFO(x, #LIFO_TestField) = #poped
    Debug "" : Debug "0    1  2  3  4  5   "+Str(x) : DebugLIFO
    LIFO_push(x) : LIFO(x, #LIFO_TestField) = #pushed : DebugLIFO
Next
For i = 1 To 2
    x = LIFO_FirstAvailable
    Debug "" : Debug "0    1  2  3  4  5   -"+Str(x) : DebugLIFO  
    LIFO_pop(x) : LIFO(x, #LIFO_TestField) = #poped : DebugLIFO
Next
For i = 1 To 2
    Repeat : x = Random(5,1) : Until LIFO(x, #LIFO_TestField) = #poped
    Debug "" : Debug "0    1  2  3  4  5   "+Str(x) : DebugLIFO
    LIFO_push(x) : LIFO(x, #LIFO_TestField) = #pushed : DebugLIFO
Next
For i = 1 To 3
    x = LIFO_FirstAvailable
    Debug "" : Debug "0    1  2  3  4  5   -"+Str(x) : DebugLIFO  
    LIFO_pop(x) : LIFO(x, #LIFO_TestField) = #poped : DebugLIFO
Next

Re: sehr einfacher LastInFirstOut-Stapel

Verfasst: 11.07.2015 23:25
von uweb
Ich wollte noch ein wenig daran feilen.
Aber Macros innerhalb eines Macros zu definieren geht wohl nicht, oder?

Code: Alles auswählen

Macro LIFO(LIFO, Elements, Fields)
Global #LIFO_Elements = Elements, #LIFO_Fields = Fields ; Base1 because 0 is used by #LIFO
Global Dim #LIFO(#LIFO_Elements,#LIFO_Fields) 
Macro #LIFO_FirstAvailable : #LIFO(0,0) : EndMacro
Macro #LIFO_NexAvailable(x) : #LIFO(x,0) : EndMacro
Macro #LIFO_bag(x) : #LIFO_NexAvailable(x) = #LIFO_FirstAvailable : #LIFO_FirstAvailable = x : EndMacro
Macro #LIFO_unbag(x) : #LIFO_FirstAvailable = #LIFO_NexAvailable(x) : #LIFO_NexAvailable(x) = 0 : EndMacro
EndMacro

LIFO(MyTest, 5, 42)

Re: sehr einfacher LastInFirstOut-Stapel

Verfasst: 12.07.2015 10:09
von Nino
Nur ein paar Anmerkungen ...
uweb hat geschrieben:sehr einfacher LastInFirstOut-Stapel
Das ist ein Pleonasmus: Ein Stapel (engl. "stack") ist ja gerade dadurch definiert, dass er nach dem LIFO-Prinzip ("last in, first out") arbeitet.
Eine Datenstruktur, die stattdessen nach dem FIFO-Prinzip ("first in, first out") arbeitet, heißt Warteschlange.
Die Grundoperationen auf einem Stapel heißen nicht "bag" und "unbag", sondern "push" und "pop".

Und ja: Die Definition von Macros innerhalb von anderen Macros wird von PB (zumindest bis jetzt, d.h. Version 5.31) nicht unterstützt.

Re: sehr einfacher LastInFirstOut-Stapel

Verfasst: 12.07.2015 13:19
von uweb
Danke! Ich habe es geändert.

Re: sehr einfacher Stapel

Verfasst: 12.07.2015 17:52
von STARGÅTE
Also ich habe mir den Code nun zwei mal angeguckt, und mir ist auch durchaus klar, wie ein LIFO funktioniert,
dein Code ist für mich jedoch sehr Verwirrend.

In dein Stapel können scheinbar nur Werte gepusht werden, die innerhalb der Stapelgröße liegen.
Und du speichert garnicht den Wert selbst, sondern nur die Reihenfolge, wie die Felder des Stacks sortiert sind.
Und für was ist die 2. Dimension, zum ansprecher der verschiedenen Stacks?
Das ist doch eine völlig andere herangehensweise, als die, die bei einem LIFO verwendet wird, oder irre ich mich da?

Nach der Überschrift "sehr einfacher Stapel" wäre eine Lösung mittels Listen in meinen Augen am Einfachsten:

Code: Alles auswählen

Procedure.s Push(List Stack.s(), Value.s)
	AddElement(Stack()) : Stack() = Value
	ProcedureReturn Value
EndProcedure

Procedure.s Pop(List Stack.s())
	Protected Value.s
	If ListSize(Stack()) > 0
		Value = Stack()
		DeleteElement(Stack())
		ProcedureReturn Value
	EndIf
EndProcedure

Procedure.s Peek(List Stack.s())
	If ListSize(Stack()) > 0
		ProcedureReturn Stack()
	EndIf
EndProcedure


;- Example

Define NewList MyStack.s()

Debug Peek(MyStack()) ; Stack is empty
Push(MyStack(), "A")
Debug Peek(MyStack()) ; Top element is A
Push(MyStack(), "B")
Debug Pop(MyStack())  ; Pop element B
Push(MyStack(), "C")
Debug Pop(MyStack())  ; Pop element C
Debug Pop(MyStack())  ; Pop element A
Bezogen auf Geschwindigkeit wäre eine Lösung mit einem Array & Index natürlich schneller, aber der Code wäre ähnlich.

Aber deine Herangehensweise leuchtet mir nicht ein.

Re: sehr einfacher Stapel

Verfasst: 12.07.2015 18:37
von uweb
Danke fürs Feedback.
Nun sehe ich mal selbst wie notwendig es ist etwas mehr erklärenden Text mit zu liefern.
können scheinbar nur Werte gepusht werden, die innerhalb der Stapelgröße liegen
Ja (based on fix array), es geht um eine fixe Anzahl von Elementen die entweder im Stapel ruhen oder "aktiv" sind.
In meinem Fall sind es Threads die jeweils für einen Client zuständig sind und nach nach jedem Arbeitsschritt im Stapel auf Standby gehen.
Ich denke es gibt auch andere Anwendungen z.B. mit fixer Maximal-Anzahl : Undo-Schritte.
Die würden dann im Stapel ruhen oder wären einfach erledigt.
speichert garnicht den Wert selbst, sondern nur die Reihenfolge
Ja, die Werte sind ja von der jeweiligen Anwendung abhängig. In meinem Fall sind es Verbindungsdaten.
Der Test ist z.B. auch eine Anwendung. Da habe ich eines der Felder (#LIFO_TestField) genutzt - wenn auch nur um zu wissen ob ein Element "aktiv" ist.

Bei einer konkreten Anwendung würde man natürlich

Code: Alles auswählen

LIFO_push(x) : LIFO(x, #LIFO_Datenfeld) = value
in ein Macro zusammenfassen.
eine völlig andere herangehensweise ... eine Lösung mittels Listen ... mit einem Array & Index natürlich schneller, aber der Code wäre ähnlich
Um ehrlich zu sein : Ich weiß nicht was die übliche Herangehensweise ist.
Die statische Array-Größe und die Macros an Stelle von Proceduren habe ich eben wegen der Geschwindigkeit gewählt.
Es ist sicher nicht die Universal-Lösung, aber für eine fixe Größe scheint es mir sinnvoll.

Re: sehr einfacher Stapel

Verfasst: 13.07.2015 08:54
von mhs
uweb hat geschrieben:Um ehrlich zu sein : Ich weiß nicht was die übliche Herangehensweise ist.
Die statische Array-Größe und die Macros an Stelle von Proceduren habe ich eben wegen der Geschwindigkeit gewählt.
Es ist sicher nicht die Universal-Lösung, aber für eine fixe Größe scheint es mir sinnvoll.
Ein übliche herangehensweise ist eine einfach verkettete Liste. Oft weiss man gar nicht wieviele Elemente im Stapel landen und die Liste muss immer nur auf das darunterliegende Element zeigen und genau dafür eignet sich eine einfach verkettete Liste hervorragend.

Ich würde es so wie Stargate machen und einfach die PB Listen verwenden. Der Performanceunterschied wird in den meisten Fällen eh nicht so zum Tragen kommen und der Gewinn an Einfachheit und Geschwindigkeit beim Entwickeln überwiegt, aber das muss man je nach Fall abwägen.

Re: sehr einfacher Stapel

Verfasst: 13.07.2015 09:31
von Nino
uweb hat geschrieben:Um ehrlich zu sein : Ich weiß nicht was die übliche Herangehensweise ist.
Die übliche Weise, einen Stack zu implementieren, ist m.E. ungefähr das was Stargate gepostet hat.

Allerdings würde ich diese Prozedur

Code: Alles auswählen

Procedure.s Push(List Stack.s(), Value.s)
   AddElement(Stack()) : Stack() = Value
   ProcedureReturn Value
EndProcedure
so schreiben

Code: Alles auswählen

Procedure Push(List Stack.s(), Value.s)
   AddElement(Stack()) : Stack() = Value
EndProcedure
Es ist nicht nötig dass die Prozedur den selben Wert an den aufrufenden Programmteil zurückgibt, den sie gerade von eben diesem erhalten hat.

Re: sehr einfacher Stapel

Verfasst: 14.07.2015 07:25
von uweb
Danke für die Tips.
Im Moment werde ich für den konkreten Fall (fixe Größe) wegen der Geschwindigkeit noch meine Lösung nutzen.
Es ist aber gut eine universellere Lösung in der Hinterhand zu haben.

Re: sehr einfacher Stapel

Verfasst: 21.02.2016 02:18
von uweb
Da ich nun eine Warteschlange gebraucht habe wollte ich es diesmal etwas universeller angehen.
Ich spiele zur Zeit gerne mit Macros herum, kenne die maximale Größe und mag keine dynamischen Speicher.
Deswegen sieht das Ergebnis auf den ersten Blick ähnlich aus.
Diesmal habe ich mich aber dafür entschieden Indizes zu speichern statt die Position zu nutzen und nur die Reihenfolge in die Felder zu schreiben.
Ein weiterer Unterschied ist, dass es sich um einen Ring handelt den man als Stapel und als Warteschlange nutzen kann.

Im Nachhinein frage ich mich ob eine einfach Umsetzung als Muster für den jeweiligen Anwendungsfall nicht eine bessere Idee gewesen wäre als das "Universalmacro".
Vielleicht kann es ja trotzdem jemand brauchen.

Code: Alles auswählen

Macro Ring(Name, Elements) : Dim Name(Elements+2) : Name(0)=Elements : EndMacro ; Elements, First, Used, Datafields 
Macro RingElements (Name) : Name(0) : EndMacro
Macro RingFirst (Name)    : Name(1) : EndMacro
Macro RingUsed (Name)     : Name(2) : EndMacro
Macro RingFree (Name)  : RingElements (Name)-RingUsed (Name) : EndMacro
Macro RingNext (Name) : ((RingFirst (Name)+RingUsed (Name))%RingElements (Name))+3   : EndMacro
Macro RingLast (Name) : ((RingFirst (Name)+RingUsed (Name)-1)%RingElements (Name))   : EndMacro
Macro RingEnter (Name, Value): Name(RingNext (Name)) = Value : RingUsed (Name) =  RingUsed (Name) +1 : EndMacro ; use "If RingFree()"
Macro RingPush  (Name, Value): Name(RingNext (Name)) = Value : RingUsed (Name) =  RingUsed (Name) +1 : EndMacro ; use "If RingFree()"
Macro RingFront (Name) : Name(RingFirst (Name)+3) : EndMacro 
Macro RingTop   (Name) : Name(RingLast  (Name)+3) : EndMacro
Macro RingLeave  (Name): RingUsed (Name) =  RingUsed (Name)  -1 : RingFirst (Name) = ((RingFirst (Name)+1)%RingElements (Name)) : EndMacro ; use "If RingUsed"
Macro RingPop  (Name, Variable): Variable = RingTop (Name) : RingUsed (Name) =  RingUsed (Name)  -1 : EndMacro ; use "If RingUsed"

; Test
Macro RingTestA (Name, Operation)
  Debug "E   F   U         0   1   2   3   4"
  Debug Str(RingElements (Name))+"   "+Str(RingFirst (Name))+"   "+Str(RingUsed (Name))+"          "+Str(Name(3))+"   "+Str(Name(4))+"   "+Str(Name(5))+"   "+Str(Name(6))+"   "+Str(Name(7))+"         "+Operation
EndMacro

Macro RingTestB (Name)
  Debug Str(RingElements (Name))+"   "+Str(RingFirst (Name))+"   "+Str(RingUsed (Name))+"          "+Str(Name(3))+"   "+Str(Name(4))+"   "+Str(Name(5))+"   "+Str(Name(6))+"   "+Str(Name(7))
  Debug""
EndMacro

Macro NotPossible : Debug ">>> not possible !" : Debug "" : EndMacro

Ring(Test,5)

If RingFree(Test) : RingTestA (Test, "RingPush  (Test, 1)") : RingPush  (Test, 1) : RingTestB (Test) : Else  : RingTestA (Test, "RingPush  (Test, 1)") : NotPossible : EndIf
If RingFree(Test) : RingTestA (Test, "RingPush  (Test, 2)") : RingPush  (Test, 2) : RingTestB (Test) : Else  : RingTestA (Test, "RingPush  (Test, 2)") : NotPossible : EndIf
If RingFree(Test) : RingTestA (Test, "RingPush  (Test, 3)") : RingPush  (Test, 3) : RingTestB (Test) : Else  : RingTestA (Test, "RingPush  (Test, 3)") : NotPossible : EndIf
If RingFree(Test) : RingTestA (Test, "RingPush  (Test, 4)") : RingPush  (Test, 4) : RingTestB (Test) : Else  : RingTestA (Test, "RingPush  (Test, 4)") : NotPossible : EndIf
If RingFree(Test) : RingTestA (Test, "RingPush  (Test, 5)") : RingPush  (Test, 5) : RingTestB (Test) : Else  : RingTestA (Test, "RingPush  (Test, 5)") : NotPossible : EndIf
If RingFree(Test) : RingTestA (Test, "RingPush  (Test, 6)") : RingPush  (Test, 6) : RingTestB (Test) : Else  : RingTestA (Test, "RingPush  (Test, 6)") : NotPossible : EndIf
  
Debug Str(RingFront (Test))+"                                                   RingFront (Test)"     : Debug""
Debug Str(RingTop     (Test))+"                                                   RingTop   (Test)" : Debug""
  
If RingUsed(Test) : RingTestA (Test, "RingLeave (Test)") : RingLeave (Test) : Test(3) = 0 ; not necessary - only for demo
RingTestB (Test) : Else  : RingTestA (Test, "RingLeave (Test)") : NotPossible : EndIf
  
If RingUsed(Test) : RingTestA (Test, "RingPop   (Test, x)") : RingPop   (Test, x) : Test(7) = 0 ; not necessary - only for demo
Debug "x = "+Str(x) : RingTestB (Test) : Else  : RingTestA (Test, "RingPush  (Test, 6)") : NotPossible : EndIf

Debug Str(RingFront (Test))+"                                                   RingFront (Test)"     : Debug""
Debug Str(RingTop     (Test))+"                                                   RingTop   (Test)" : Debug""

If RingFree(Test) : RingTestA (Test, "RingEnter  (Test, 7)") : RingEnter  (Test, 7) : RingTestB (Test) : Else  : RingTestA (Test, "RingEnter  (Test, 7)") : NotPossible : EndIf
If RingFree(Test) : RingTestA (Test, "RingEnter  (Test, 8)") : RingEnter  (Test, 8) : RingTestB (Test) : Else  : RingTestA (Test, "RingEnter  (Test, 8)") : NotPossible : EndIf
Alle Zeiten sind UTC+02:00
Seite 1 von 1

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de