Lineare Liste für BB

Übersicht BlitzBasic Codearchiv

Neue Antwort erstellen

ToeB

Betreff: Lineare Liste für BB

BeitragMi, Jun 20, 2012 13:25
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich weiß, in BlitzBasic ist es eigl. Unnötig lineare Listen zu schreiben, und vor allem ziemlich umständlich und man muss ein wenig tricksen. Aber dennoch kann man vor allem bei GUI's damit einen ziemlichen Geschwindigkeitsvorteil erlangen (Bis zu 20x Schneller)! Denn mit der Lib unten kann man wie im Beispiel zu sehen ist einfach die Gadgets in einer solchen Liste abspeichern und muss nicht immer alle durchlaufen um die zu finden, welche zu dem Fenster gehören. Das ganze bietet schon kleine Funktionen für Liste erstellen, Link ans Ende hinzufügen, Link an den Anfang hinzufügen, Link löschen, Liste zählen und mittels der ID entweder den Link oder nur den Wert des links abfragen.

Hier erstmal die Lib:
BlitzBasic: [AUSKLAPPEN]
Type TList
Field link_head.TLink
Field count
End Type

Type TLink
Field value
Field list.Tlist
Field link_next.TLink
Field link_prev.TLink
End Type


Function CreateList.TList( )
Local list.TList = New TList
list\count = 0
Return list
End Function

Function ListAddLast.TLink( List.TList, value )
Local link.TLink = New TLink
link\value = value
link\list = list
If List\link_head = Null Then
List\link_head = link
List\count = 1
Else
Local start.TLink = List\link_head
Repeat
If start\link_next = Null Then
start\link_next = link
link\link_prev = start
List\count = List\count + 1
Exit
EndIf
start = start\link_next
Until start = Null
EndIf
Return link
End Function

Function ListAddFirst.TLink( List.TList, value )
Local link.TLink = New TLink
link\value = value
link\list = list
If List\link_head = Null Then
List\link_head = link
List\count = 1
Else
link\link_next = List\link_head
List\link_head\link_prev = link
List\link_head = link
List\count = List\count + 1
EndIf
Return link
End Function

Function RemoveLink( Link.TLink )
If link <> Null Then
Local del = False
If link = link\list\link_head Then
link\list\link_head = link\list\link_head\link_next
del = True
Else
If link\link_next <> Null Then
link\link_next\link_prev = link\link_prev
EndIf
If link\link_prev <> Null Then
link\link_prev\link_next = link\link_next
EndIf
del = True
EndIf
If del Then
link\List\count = link\List\count - 1
Delete link
EndIf
EndIf
End Function

Function CopyList.TList( list.TList )
Local nList.TList = CreateList( )
Local start.Tlink = list\link_head
While start <> Null
ListAddLast( nList, start\value )
start = start\link_next
Wend
Return nList
End Function


Function PrintList( List.TList )
Local start.TLink = List\link_head
Local count = 1
DebugLog "Liste: "
While start <> Null
DebugLog " "+count+".: "+start\value
start = start\link_next
count = count + 1
Wend
End Function


Function CountList( List.TList )
Return List\count
End Function

Function GetValueByID( List.TList, ID )
Local start.TLink = List\link_head
For i = 2 To ID
start = start\link_next
Next
If start <> Null Then
Return start\value
Else
Return 0
EndIf
End Function

Function GetLinkByID.TLink( List.TList, ID )
Local start.TLink = List\link_head
For i = 2 To ID
start = start\link_next
Next
Return start
End Function


Und hier das GUI beispiel:
BlitzBasic: [AUSKLAPPEN]
Include "LinkedList.bb"

Type Parent
Field childlist.TList
Field x, y, w, h
End Type

Type Child
Field p.parent, l.TLink
Field x, y, w, h
End Type


Graphics 800, 600, 16, 2

Local w1.parent = CreateParent( 100, 100,400, 300 )
Local w2.parent = CreateParent( 200, 400, 500, 200 )

AddChild( w1, 50, 50, 100, 20 )
AddChild( w1, 50, 75, 100, 20 )
AddChild( w1, 50, 100, 100, 20 )

AddChild( w2, 50, 50, 100, 20 )
r.child = AddChild( w2, 100, 75, 100, 20 )
AddChild( w2, 150, 100, 100, 20 )

For i = 1 To 100
CopyParent( w1 )
CopyParent( w2 )
Next


Repeat
Local ms = MilliSecs( )
DrawParents2( )
Local time = MilliSecs() - ms
Text 0, 0, "Time Normal: "+time+" ms"
ms = MilliSecs( )
DrawParents( )
time = MilliSecs() - ms
Text 0, 15, "Time LinkeList: "+time+" ms"
Flip
Cls
Until KeyHit( 1 )
End


Function CreateParent.Parent( x, y, w, h )
Local p.parent = New parent
p\x = x
p\y = y
p\w = w
p\h = h
p\childlist = CreateList( )
Return p
End Function

Function CopyParent.Parent( copy.parent )
Local p.parent = New parent
p\x = copy\x
p\y = copy\y
p\w = copy\w
p\h = copy\h
p\childlist = CreateList( )
Local count = CountList( copy\childlist )
For i = 1 To count
Local c.child = Object.child( GetValueByID( copy\childlist, i ) )
CopyChild( c, p )
Next
Return p
End Function

Function CopyChild( copy.child, p.parent )
Local c.child = New child
c\x = copy\x
c\y = copy\y
c\w = copy\w
c\h = copy\h
c\p = p
c\l = ListAddLast( p\childlist, Handle( c ) )
End Function

Function AddChild.Child( p.parent, x, y, w, h )
Local c.child = New child
c\x = x
c\y = y
c\w = w
c\h = h
c\p = p
c\l = ListAddLast( p\childlist, Handle(c) )
Return c
End Function

Function DrawParents( )
Local p.parent
Local countp = 0
For p = Each parent
countp = countp + 1
Color( 255, 64, 64 )
Rect p\x, p\y, p\w, p\h, 0
Local count = CountList( p\childlist )
;Text 0, countp*13, "Count("+countp+"): "+count
Color( 64, 255, 64 )
For i = 1 To count
Local c.child = Object.child( GetValueByID( p\childlist, i ) )
Rect p\x+c\x, p\y+c\y, c\w, c\h, 0
Next
Next
End Function


Function DrawParents2( )
Local p.parent
For p = Each parent
Color( 255, 64, 64 )
Rect p\x, p\y, p\w, p\h, 0
Color( 64, 255, 64 )
For c.child = Each child
If c\p = p Then
Rect p\x+c\x, p\y+c\y, c\w, c\h, 0
EndIf
Next
Next
End Function


DrawParents2 ist hierbei übrigens die am häufigsten benutze Variante, die langsamste.

Ich hoffe das kann irgendwer gebrauchen !

Lg, Tobias
Religiöse Kriege sind Streitigkeiten erwachsener Männer darum, wer den besten imaginären Freund hat.
Race-Project - Das Rennspiel der etwas anderen Art
SimpleUDP3.0 - Neuste Version der Netzwerk-Bibliothek
Vielen Dank an dieser Stelle nochmal an Pummelie, welcher mir einen Teil seines VServers für das Betreiben meines Masterservers zur verfügung stellt!

KnorxThieus

BeitragMi, Jun 20, 2012 16:47
Antworten mit Zitat
Benutzer-Profile anzeigen
Das versteh ich nicht.

Geschwindigkeitsvorteil klingt zwar gut, aber was macht dein Programm da?

MfgG
Version: BlitzPlus / Blitz+

ToeB

BeitragMi, Jun 20, 2012 17:46
Antworten mit Zitat
Benutzer-Profile anzeigen
Also..

Normal wird ja Blitz intern jedes neue Object eines Types in einer Liste gespeichert sodass man in einer For..Each schleife ALLE abfragen kann.

Das Problem hierbei ist bei einer Gui, dass man wenn man Buttons bspw. auf ein Fenster legen möchte, und diesen Button dann auf ein Fenster malen will, man alle Buttons durchgehen muss um zu prüfen welcher jetzt auf dem Fenster liegen soll (Siehe Funktion DrawParents2). Das kann aber bei sehr vielen Fenstern und vielen Buttons sehr langsam werden.

Meine Lineare Liste ist praktisch eine selber geschriebene Liste für Types (Da man hierbei auch nur das Handle abspeichert, kann man auch mehrere Types in eine Liste schreiben, bspw. Buttons, Textfelder usw.). Der Vorteil ist hierbei, dass das Fenster eine Liste der Gadgets hat, welche darauf angezeigt werden sollen und muss dann auch nur diese durchgehen.

Speicherschonend wäre natürlich, dem fenster jeweils einen Zeiger auf einen Start-Gadget zu geben und in dem Gadget selber dann immer das jeweils nächste zu speichern:
BlitzBasic: [AUSKLAPPEN]
Type Window
Field button.button
End Type

Type button
Field nextbutton.button
End Type


Und somit kann man dann alle Buttons auf dem fenster so abfragen:
BlitzBasic: [AUSKLAPPEN]
start = window.button
While start <> Null
DrawButton( start )
start = start\nextbutton
Wend


Aber das wäre vom code her ein wenig unübersichtlich..

Lg, Tobias
Religiöse Kriege sind Streitigkeiten erwachsener Männer darum, wer den besten imaginären Freund hat.
Race-Project - Das Rennspiel der etwas anderen Art
SimpleUDP3.0 - Neuste Version der Netzwerk-Bibliothek
Vielen Dank an dieser Stelle nochmal an Pummelie, welcher mir einen Teil seines VServers für das Betreiben meines Masterservers zur verfügung stellt!

Propellator

BeitragMi, Jun 20, 2012 19:10
Antworten mit Zitat
Benutzer-Profile anzeigen
Was du da übrigens ansprichst nennt sich "Linked List" oder auf Deutsch "doppelt verknüpfte Liste", den Begriff "lineare Liste" habe ich noch nie gehört, und scheint auch nicht häufig zu sein.
Propellator - Alles andere ist irrelephant.
Elefanten sind die Könige der Antarktis.

ToeB

BeitragMi, Jun 20, 2012 20:29
Antworten mit Zitat
Benutzer-Profile anzeigen
Ja du hast schon Recht, normalerweise nennt sich das LinkedList. Lineare Listen wären dann Listen, welche direkt in der Klasse (Oder in Pascal im Record) selbst gehandelt werden, und es immer nur ein Nachfolger gespeichert wird, nie der Vorgänger. Deswegen auch Linear Wink

Lg, Tobias
Religiöse Kriege sind Streitigkeiten erwachsener Männer darum, wer den besten imaginären Freund hat.
Race-Project - Das Rennspiel der etwas anderen Art
SimpleUDP3.0 - Neuste Version der Netzwerk-Bibliothek
Vielen Dank an dieser Stelle nochmal an Pummelie, welcher mir einen Teil seines VServers für das Betreiben meines Masterservers zur verfügung stellt!

BladeRunner

Moderator

BeitragMi, Jun 20, 2012 20:33
Antworten mit Zitat
Benutzer-Profile anzeigen
Da muss ich widersprechen:
Eine Linked List ist das was Du bescheibst, Toeb- eine Liste die nur je den nächsten Link kennt.
Eine doppelt verkettete Liste wie Du sie hier implementiert hast nennt sich doubly linked list.
Wir hatten es vorhin schon im Chat wegen der Bezeichnungen, war ein interessantes Gespräch.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI

Stolzer Gewinner des BAC#48, #52 & #92

ToeB

BeitragMi, Jun 20, 2012 23:26
Antworten mit Zitat
Benutzer-Profile anzeigen
Hab mal gegoogled und dabei den Artikel unter dem Namen "Lineare Listen ..." Gefunden. Dort wird das gleich Prinzip erklärt:

http://www.tu-chemnitz.de/wirt.../lists.htm
http://www.leda-tutorial.org/d...02s03.html


Anscheinend gibt es nur vom Begriff her einen Unterschied, gemeint ist wohl das gleiche ..

Lg, Tobias
Religiöse Kriege sind Streitigkeiten erwachsener Männer darum, wer den besten imaginären Freund hat.
Race-Project - Das Rennspiel der etwas anderen Art
SimpleUDP3.0 - Neuste Version der Netzwerk-Bibliothek
Vielen Dank an dieser Stelle nochmal an Pummelie, welcher mir einen Teil seines VServers für das Betreiben meines Masterservers zur verfügung stellt!

KnorxThieus

BeitragFr, Jun 22, 2012 9:21
Antworten mit Zitat
Benutzer-Profile anzeigen
@ToeB: Achso, für GUI...

Und mit Types kenne ich mich leider überhaupt noch nicht aus Embarassed

mfg
Version: BlitzPlus / Blitz+

BladeRunner

Moderator

BeitragFr, Jun 22, 2012 9:26
Antworten mit Zitat
Benutzer-Profile anzeigen
Toeb, danke für die Links. Klar, wenn man unterscheiden will zwischen linearer Struktur und einem verzweigenden Container wie einem Baum macht das Sinn, allerdings glaube ich dass der Begriff Liste als solches Ja schon die Linearität beinhaltet. Aber das ist Haarespalterei Wink
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI

Stolzer Gewinner des BAC#48, #52 & #92

Neue Antwort erstellen


Übersicht BlitzBasic Codearchiv

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group