2 LinkedLists vertauschen

Anfängerfragen zum Programmieren mit PureBasic.
Benutzeravatar
Regenduft
Beiträge: 574
Registriert: 25.03.2008 15:07
Wohnort: THE LÄÄÄND!

2 LinkedLists vertauschen

Beitrag 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.
PureBasic 5.73 LTE x86/x64 | Windows 7 (x64)
Drago
Beiträge: 148
Registriert: 02.02.2010 18:22
Computerausstattung: Win XP SP3, AMD Sempron (MMX) 1.2 GHz, 512 MB, Nvidia GeForce FX 5200, 128 MB, DirectX 9.0c
Wohnort: Westerwald

Re: 2 LinkedLists vertauschen

Beitrag 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() )
Zuletzt geändert von Drago am 01.11.2012 12:21, insgesamt 1-mal geändert.
Benutzeravatar
Regenduft
Beiträge: 574
Registriert: 25.03.2008 15:07
Wohnort: THE LÄÄÄND!

Re: 2 LinkedLists vertauschen

Beitrag von Regenduft »

Danke für die schnelle Antwort, aber da ist meine FirstElement()-MergeLists()-SplitList()-Combo doch sehr viel schneller...
PureBasic 5.73 LTE x86/x64 | Windows 7 (x64)
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8808
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 64 GB DDR4-3200
Ubuntu 24.04.2 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken

Re: 2 LinkedLists vertauschen

Beitrag 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
Benutzeravatar
PMV
Beiträge: 2765
Registriert: 29.08.2004 13:59
Wohnort: Baden-Württemberg

Re: 2 LinkedLists vertauschen

Beitrag 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
alte Projekte:
TSE, CWL, Chatsystem, GameMaker, AI-Game DLL, Fileparser, usw. -.-
Benutzeravatar
Regenduft
Beiträge: 574
Registriert: 25.03.2008 15:07
Wohnort: THE LÄÄÄND!

Re: 2 LinkedLists vertauschen

Beitrag 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
PureBasic 5.73 LTE x86/x64 | Windows 7 (x64)
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8808
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 64 GB DDR4-3200
Ubuntu 24.04.2 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken

Re: 2 LinkedLists vertauschen

Beitrag 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.
Benutzeravatar
Regenduft
Beiträge: 574
Registriert: 25.03.2008 15:07
Wohnort: THE LÄÄÄND!

Re: 2 LinkedLists vertauschen

Beitrag 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
Zuletzt geändert von Regenduft am 09.11.2012 22:04, insgesamt 2-mal geändert.
PureBasic 5.73 LTE x86/x64 | Windows 7 (x64)
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 7028
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: 2 LinkedLists vertauschen

Beitrag 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.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benutzeravatar
Regenduft
Beiträge: 574
Registriert: 25.03.2008 15:07
Wohnort: THE LÄÄÄND!

Re: 2 LinkedLists vertauschen

Beitrag 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.
PureBasic 5.73 LTE x86/x64 | Windows 7 (x64)
Antworten