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

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group