PureBoard

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

2 LinkedLists vertauschen

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

Seite 1 von 2

2 LinkedLists vertauschen

Verfasst: 01.11.2012 11:14
von Regenduft
Hallo Leutz,

Ich versuche gerade krampfhaft 2 komplette LinkedLists zu vertauschen ohne herumzutricksen. Ich bin mir ziemlich sicher, dass das mit PureBasic irgendwie geht und ich nur auf dem Schlauch stehe!
Mit Arrays geht das ja ganz einfach und problemlos:

Code: Alles auswählen

Dim a.s(1)
Dim b.s(1)

a(0) = "a0"
a(1) = "a1"

b(0) = "b0"
b(1) = "b1"

Swap a(), b()

Debug "== a =="
Debug a(0)
Debug a(1)

Debug "== b =="
Debug b(0)
Debug b(1)
Dass das Vertauschen mit Listen nicht so funktionieren kann wie mit Arrays sollte klar sein, da ja Listen keinen Index in der Klammer führen und somit die gleiche Syntax lediglich zum Vertauschen des jeweils aktuellen Elementes der beiden Listen führt.

Im Moment zweckentfremde ich MergeLists() und SplitList() um das gewünschte Ergebnis zu erhalten, allerdings bin ich generell kein Freund von Zweckentfremdungen und außerdem - wie gesagt - bin ich der Überzeugung dass PureBasic das doch irgendwie von Haus aus können muss!

Code: Alles auswählen

Macro SwapLists(ListA, ListB)
  FirstElement(ListA)
  MergeLists(ListB, ListA, #PB_List_Before)
  SplitList(ListA, ListB, #False)
EndMacro

NewList a.s()
NewList b.s()

AddElement(a()): a() = "a0"
AddElement(a()): a() = "a1"

AddElement(b()): b() = "b0"
AddElement(b()): b() = "b1"

SwapLists(a(), b())

Debug "== a =="
ForEach a()
  Debug a()
Next

Debug "== b =="
ForEach b()
  Debug b()
Next
Diese Methode ist zwar nicht besonders "schmutzig", birgt aber Nachteile:
  • Ich kann aus dem Macro keine Prozedur stricken, da dies eine Beschränkung des Datentypes mit sich bringen würde.
  • Im Vergleich zum Swap (wie beim Array) geht etwas an Performance verloren (wenn auch minimal - 3 Prozeduraufrufe mit insg. 7 Parameterübergaben ist langsamer als das Vertauschen von zwei Zeigern).
Ich wäre also Dankbar wenn mir jemand auf die Sprünge helfen könnte!

Um der Frage "Wozu das ganze überhaupt?" vorwegzugreifen: Ich habe eine Prozedur in welcher ich recht komplizierte (im Sinne von "unübersichtliche") Aktionen mit einer als Parameter übergebenen Liste durchführe. Einzelne Elementinhalte werden verändert und gleichzeitig deren Position innerhalb der Liste. Der Einfachheit zu liebe erstelle ich eine zweite lokale Liste, verschiebe jedes abgearbeitete Element in diese zweite Liste und vertausche vor dem Prozedurenende die beiden Listen, was gleichzeitig dazu führt, dass überflüssige Elemente in der lokalen Liste landen und automatisch freigegeben werden.

Re: 2 LinkedLists vertauschen

Verfasst: 01.11.2012 12:01
von Drago

Code: Alles auswählen

Structure Pos
     x.f
     y.f
EndStructure

NewList List1.Pos()
NewList  List2.Pos()
NewList Container.Pos()

CopyList( List1(), Container() )
CopyList( List2(), List1() )
CopyList( Container(), List2() )

Re: 2 LinkedLists vertauschen

Verfasst: 01.11.2012 12:21
von Regenduft
Danke für die schnelle Antwort, aber da ist meine FirstElement()-MergeLists()-SplitList()-Combo doch sehr viel schneller...

Re: 2 LinkedLists vertauschen

Verfasst: 01.11.2012 23:12
von NicTheQuick
Ein bisschen komplizierter, aber wenn man Strukturen und Pointer nutzt, kann man damit ja LinkedLists sozusagen wrappen. Hier ein unsinniges Beispiel:

Code: Alles auswählen

Structure MyList
	List l.s()
EndStructure

Procedure Do(*pInput.Integer)
	Protected *input.MyList = *pInput\i
	Protected *tmp.MyList = AllocateMemory(SizeOf(MyList))
	InitializeStructure(*tmp, MyList)
	
	ForEach *input\l()
		If (Left(*input\l(), 1) = "+")
			If AddElement(*tmp\l())
				*tmp\l() = *input\l()
			EndIf
		EndIf
	Next
	
	;Listen tauschen
	;alte löschen
	ClearStructure(*input, MyList)
	FreeMemory(*input)
	;neue zuweisen
	*pInput\i = *tmp
EndProcedure

Define *list1.MyList = AllocateMemory(SizeOf(MyList))
InitializeStructure(*list1, MyList)

AddElement(*list1\l()) : *list1\l() = "-1"
AddElement(*list1\l()) : *list1\l() = "+1"
AddElement(*list1\l()) : *list1\l() = "-9"
AddElement(*list1\l()) : *list1\l() = "+5"
AddElement(*list1\l()) : *list1\l() = "+31"
AddElement(*list1\l()) : *list1\l() = "-12"

Do(@*list1)

ForEach *list1\l()
	Debug *list1\l()
Next

Re: 2 LinkedLists vertauschen

Verfasst: 02.11.2012 13:48
von PMV
Wenns unbedingt richtig schnell sein muss, würde ich den Ansatz verfolgen:
Wenn man die PB interne Struktur von LinkedListen kennt, könnte man
das tauschen kompletter Listen nur durch das Ändern weniger Werte
innerhalb dieser Struktur bewerkstelligen. :D

MFG PMV

Re: 2 LinkedLists vertauschen

Verfasst: 02.11.2012 18:12
von Regenduft
@PMV: Ja! Genau! Ich bin immernoch verblüfft, dass das nicht per PB-Schlüsselwort oder -Funktion funktioniert!

@NicTheQuick: Gute Idee! ... glaube ich ... bin mir nämlich nicht ganz sicher, ob ich Dich richtig verstanden habe ...
Egal, ob Du's so gemeint hast oder nicht, habe ich mal einen recyclebaren Schuh draus gestrickt: :mrgreen:

Code: Alles auswählen

EnableExplicit

Macro NewStrucList(ListName, DataType)
  CompilerIf Defined(__StrucList#DataType, #PB_Structure) = #False
    Structure __StrucList#DataType
      List l.DataType()
    EndStructure
  CompilerEndIf
  Define *ListName.__StrucList#DataType
  *ListName = AllocateMemory(SizeOf(__StrucList#DataType))
  InitializeStructure(*ListName, __StrucList#DataType)
EndMacro

Macro DebugStrucList
  Debug "======================="
  Debug "-- a --"
  ForEach *a\l()
    Debug *a\l()
  Next
  Debug "-- b --"
  ForEach *b\l()
    Debug *b\l()
  Next
  Debug "======================="
EndMacro

NewStrucList(a, s)
NewStrucList(b, s)

AddElement(*a\l()): *a\l() = "a0"
AddElement(*a\l()): *a\l() = "a1"

AddElement(*b\l()): *b\l() = "b0"
AddElement(*b\l()): *b\l() = "b1"

DebugStrucList

Debug "Swap *a, *b"
Swap *a, *b

DebugStrucList

Re: 2 LinkedLists vertauschen

Verfasst: 02.11.2012 19:44
von NicTheQuick
Ja, so hab ich's gemeint. Das ist halt auf jeden Fall eine saubere Lösung, nur halt leider nicht ganz so schön.

Re: 2 LinkedLists vertauschen

Verfasst: 09.11.2012 01:34
von Regenduft
PMV hat geschrieben:Wenn man die PB interne Struktur von LinkedListen kennt, könnte man
das tauschen kompletter Listen nur durch das Ändern weniger Werte
innerhalb dieser Struktur bewerkstelligen. :D
Ich mime Dir mal die bezaubernde Jeannie *zwinker-nick*. So! :wink:
Könnte sogar sein (muss aber nicht), dass mein SwapLists() schneller ist als die "Strukturlistenlösung", da PB beim Verwenden von Swap einen ewig langen ASM-Code erstellt und fleißig rum-pusht und -popt. Könnte aber auch ein Zeichen dafür sein, wie schlecht mein ASM-Code ist... :lol:
Natürlich ist der Code mit äußerster Vorsicht zu genießen! Von der Verwendung in Projekten (vor allem nach PB-Updates) rate ich dringenst ab! ... Über fleißiges Testen von besonders Mutigen würde ich mich trotzdem freuen, genau wie Tipps von FASM-Spezies, da ich dort blutiger Anfänger bin!
EDIT: Aktuell wird bei einem Aufruf von FreeList() oder NewList - in Verbindung mit einer von zwei getauschten Listen - genau die flasche Liste freigegeben bzw. neuerstellt!

Code: Alles auswählen

; ==========================================================
; Regenduft 2012 - Dieser Code ist Gemeingut (Public Domain)
; Von der Verwendung in Projekten wird abgeraten!
; Läuft mit PB 5.00 x86/x64, evtl. auch mit PB 4.xx
; ==========================================================

EnableExplicit
EnableASM

Macro DebugList
  Debug "--- CurrentElements ---"
  Debug "a() = "+a()
  Debug "b() = "+b()
  Debug "--- a() ---"
  ForEach a()
    Debug a()
  Next
  Debug "--- b() ---"
  ForEach b()
    Debug b()
  Next
EndMacro

Macro _SwapLists_AsStr_DoubleQuote
  "
EndMacro

Macro _SwapLists_AsStr(Ausdruck)
  _SwapLists_AsStr_DoubleQuote#Ausdruck#_SwapLists_AsStr_DoubleQuote
EndMacro

Macro SwapLists(ListA, ListB, ListA_is_Global=#True, ListB_is_Global=#True)
  
  ; Compilerfehlermeldungen
  CompilerIf Defined(ListA, #PB_LinkedList) = 0
    CompilerError "Liste muss zuvor definiert worden sein: "+_SwapLists_AsStr(ListA)+"()"
  CompilerEndIf
  CompilerIf Defined(ListB, #PB_LinkedList) = 0
    CompilerError "Liste muss zuvor definiert worden sein: "+_SwapLists_AsStr(ListB)+"()"
  CompilerEndIf
  CompilerIf Defined(t_#ListA, #PB_Variable)
    CompilerError "Kollision zwischen ASM-Listenname und Variablenname: "+_SwapLists_AsStr(t_#ListA)
  CompilerEndIf
  CompilerIf Defined(t_#ListB, #PB_Variable)
    CompilerError "Kollision zwischen ASM-Listenname und Variablenname: "+_SwapLists_AsStr(t_#ListB)
  CompilerEndIf
  
  ; FASM-Direktiven für einfachen x86/x64-Code
  ; (wegen Übersichtlichkeit innerhalb Macro)
  CompilerIf #PB_Integer = #PB_Quad
    ! xax equ rax
    ! xcx equ rcx
    ! xdx equ rdx
    ! SwapListsOffset1 equ 8  ; Antikollisionsnamensgebung ;-)
    ! SwapListsOffset2 equ 24 ; Antikollisionsnamensgebung ;-)
  CompilerElse
    ! xax equ eax
    ! xcx equ ecx
    ! xdx equ edx
    ! SwapListsOffset1 equ 4  ; Antikollisionsnamensgebung ;-)
    ! SwapListsOffset2 equ 12 ; Antikollisionsnamensgebung ;-)
  CompilerEndIf
  
  ; Zeiger zum ListA-Header
  CompilerIf ListA_is_Global
    LEA xcx, [t_#ListA] 
  CompilerElse
    LEA xcx, [p.t_#ListA]
  CompilerEndIf
  
  ; Zeiger zum ListB-Header
  CompilerIf ListB_is_Global
    LEA xdx, [t_#ListB]
  CompilerElse
    LEA xdx, [p.t_#ListB]
  CompilerEndIf
  
  ; "ListInfo" tauschen
  MOV xax, [xcx]
  XCHG xax, [xdx]
  MOV [xcx], xax
  
  ; "CurrentElement" tauschen
  MOV xax, [xcx + SwapListsOffset1]
  XCHG xax, [xdx + SwapListsOffset1]
  MOV [xcx + SwapListsOffset1], xax
  
  ; "CurrentElementInHeader" tauschen
  MOV xcx, [xcx]
  MOV xdx, [xdx]
  MOV xax, [xcx + SwapListsOffset2]
  XCHG xax, [xdx + SwapListsOffset2]
  MOV [xcx + SwapListsOffset2], xax
  
EndMacro

NewList a.s()
AddElement(a()) : a() = "a1"
AddElement(a()) : a() = "a2"
AddElement(a()) : a() = "a3"
AddElement(a()) : a() = "a4"

NewList b.s()
AddElement(b()) : b() = "b1"
AddElement(b()) : b() = "b2"
AddElement(b()) : b() = "b3"
AddElement(b()) : b() = "b4"

; Fehlermeldungstests
; ===================
;Define t_a
;Define t_b
;SwapLists(bla, b)
;SwapLists(a, bla)

DebugList

SwapLists(a, b)
Debug ""
Debug "==============="
Debug "SwapLists(a, b)"
Debug "==============="
Debug ""

DebugList

Re: 2 LinkedLists vertauschen

Verfasst: 09.11.2012 11:00
von STARGÅTE
Irgendwie wird noch nicht "richtig" getauscht.

Wenn ich nach dem Tauschen (im Falle des Beispielcodes) FreeList(a()) aufrufe, dann wird dabei die b-Liste kaputt gemacht.

Re: 2 LinkedLists vertauschen

Verfasst: 09.11.2012 21:59
von Regenduft
Hmmm... Einfach mal ein Verdacht aus dem Bauch heraus: PureBasic legt eine Objektliste an (denke nicht, dass es eine extra LinkedList-Liste gibt), welche dann auf den falschen Header zeigt. Darum wird dann bei "FreeList()" und "NewList" die falsche List bearbeitet.

Das es eine "Objektliste" überhaupt gibt habe ich natürlich mal irgendwo gelesen. Ich meine, dass ich auch irgendwo mal einen Code für das "registrieren von fremdem Gadgets in PB" (oder so ähnlich) gesehen hatte. Muss ich mal suchen. Das könnte vielleicht einen Anhaltspunkt liefern... und nochmal mit "/commented" kompilieren und die "PureBasic.asm" in Ruhe durchgehen, wobei da aber meine Assemblerkenntnisse wahrscheinlich zu ungenügend sind um etwas zu finden...

PS: Eine Umwegslösung könnte sein eine eigene "Rücksetzliste" zu führen, was ich aber für ein "Thema verfehlt" halten würde.
Alle Zeiten sind UTC+02:00
Seite 1 von 2

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de