DeleteMapElement()

Für allgemeine Fragen zur Programmierung mit PureBasic.
Benutzeravatar
Josh
Beiträge: 1028
Registriert: 04.08.2009 17:24

Re: DeleteMapElement()

Beitrag von Josh »

@STARGÅTE:
Ich glaub dir ja normal viel, aber hier glaub ich dir nicht alles :mrgreen:
STARGÅTE hat geschrieben:Das Langsame ist hier nicht das Löschen der Elemente mit DeleteMapElement() sondern das "unnatürliche" durchlaufen der Map mit ForEach oder NextMapElement().
Wenn alleine das Durchlaufen mit ForEach verantwortlich wäre, dann müsste das ForEach auch ohne Löschbefehle in der Schleife schon langsam sein. Ist aber nicht der Fall, ForEach ist richtig schnell
STARGÅTE hat geschrieben:Mit deinem Testcode änderst du sowohl die Anzahl der Slots als auch die Anzahl der Elemente, somit werden zwei Parameter des Tests verändert!
Verstehe ich nicht. Die Anzahl der Slots gebe ich beim NewMap Befehl mit an und die ändert sich nie. Wenn dem so wäre, dann dürfte folgender Code nicht schneller sein als der Code, den ich mit meinem ersten Posting veröffentlicht habe:

Code: Alles auswählen

EnableExplicit

#cntMax = 30000

NewMap MyMap (#cntMax)
Define time1, time2
Define i


time1 = ElapsedMilliseconds()
For i = 1 To #cntMax
  AddMapElement (MyMap(), "x" + i)
Next
time1 = ElapsedMilliseconds() - time1

time2 = ElapsedMilliseconds()
While MapSize (MyMap())
  ForEach MyMap()
    DeleteMapElement (MyMap())
    NextMapElement (MyMap())
  Next
Wend
time2 = ElapsedMilliseconds() - time2


MessageRequester ("", "" + time1 + #CRLF$ + time2)
NeNe, da ist irgendwo in Pb der Hund drin. Wenn etwas zum löschen das 100fache, 1000fache oder noch mehr an Zeit benötigt als zum Anlegen, da kann was nicht stimmen.
Omi
Beiträge: 143
Registriert: 25.03.2013 09:59

Re: DeleteMapElement()

Beitrag von Omi »

@Josh
Ich glaube STARGATE :wink:
Ich denke das gewählte Verfahren mit ForEach erfordert jeweils ein interne (evtl. exponentiell steigende) zeitfressende Umorganisation in PB.

Beim Verfahren wie es auch Helpy gepostet hat sieht's zeitlich ganz anders aus.

Code: Alles auswählen

EnableExplicit

#cntMax = 30000

NewMap MyMap (#cntMax)
Define time1, time2
Define i


time1 = ElapsedMilliseconds()
For i = 1 To #cntMax
  AddMapElement (MyMap(), "x" + i)
Next
time1 = ElapsedMilliseconds() - time1

time2 = ElapsedMilliseconds()

For i = 1 To #cntMax
  DeleteMapElement (MyMap(), "x" + i)
Next
time2 = ElapsedMilliseconds() - time2

MessageRequester ("", "Add: " + time1 + "ms" + #CRLF$ + "Delete: " + time2 + "ms")
Ich bekomm hier leicht variierende 10 + 8 ms.
PureBasic Linux-API-Library: http://www.chabba.de
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: DeleteMapElement()

Beitrag von STARGÅTE »

Das ForEach alleine dafür verantwortlich ist, habe ich nicht gesagt.

Fest steht aber, dass ForEach mit zunehmender Slot-Zahl langsammer wird, wie man hier schön sehen kann, ist der Zusammenhang linear, obwohl es keine Elemente gibt:

Code: Alles auswählen

Procedure ForEachMapElement(Size)
	
	Protected NewMap MyMap.i(Size)
	
	ForEach MyMap()
	Next
	
EndProcedure


OpenConsole()

For I = 10 To 25
	Time = ElapsedMilliseconds()
	ForEachMapElement(1<<I)
	PrintN("Size = "+Str(1<<I)+"  ::  "+Str(ElapsedMilliseconds()-Time)+" ms")
Next

Input()
Als nächstes muss man wissen, dass DeleteMapElement() mit angabe eines Keys und ohne Angabe eines Key zwei unterschiedliche Funktionen sind!
DeleteMapElement(MyMap(), KeyName) löscht das angesprochene Map-Element ohne ein gültiges Map-Element beizubehalten (MyMap() wird ungültig).
DeleteMapElement(MyMap()) löscht das angesprochene Map-Element und springt auf ein gültiges Map-Element oder an den Anfang der Map-Slots (MyMap bleibt außer beim löschen des ersten MapElements gültig!)

Code: Alles auswählen

NewMap MyMap.i(10)

AddMapElement(MyMap(), "Nummer A")
AddMapElement(MyMap(), "Nummer B")
AddMapElement(MyMap(), "Nummer C")
AddMapElement(MyMap(), "Nummer D")

ForEach MyMap()
	Debug MapKey(MyMap())
Next
Debug "---"
ResetMap(MyMap())
NextMapElement(MyMap())
NextMapElement(MyMap())
NextMapElement(MyMap())
Debug MapKey(MyMap())
DeleteMapElement(MyMap())
Debug MapKey(MyMap())

Debug "---"
DeleteMapElement(MyMap(), "Nummer B")
Debug MapKey(MyMap())
Was heißt das nun: Wenn du nun immer das "erste" Map-Element löschst, springt der "ForEach-Zeiger" immer an den Anfang und muss die komplette Slot-Liste wieder durchrennen. Somit wird ForEach durch das löschen der Elemente unglaublich langsam! Es entsteht so ein quadratische Laufzeit wie du es selber gemessen hast.
Durch dein zusätzliches NextMapElement() verhinderst du das Springen an den Anfang, weil Elemente übersprungen werden. Somit ist die Funktion dann schneller.
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
Josh
Beiträge: 1028
Registriert: 04.08.2009 17:24

Re: DeleteMapElement()

Beitrag von Josh »

STARGÅTE hat geschrieben:Was heißt das nun: Wenn du nun immer das "erste" Map-Element löschst, springt der "ForEach-Zeiger" immer an den Anfang und muss die komplette Slot-Liste wieder durchrennen.
Da hast du recht, da ist der Hund begraben. Wenn bei einer Annahme von 30k Slots und einer optimalen Keyverteilung von einem Key je Slot ausgehe, dann müsste Pb 450 Millionen mal (30k x 30k / 2) auf ein nächstes Element springen. Da ist es dann klar, wo die Zeit hin geht.
Benutzeravatar
Josh
Beiträge: 1028
Registriert: 04.08.2009 17:24

Re: DeleteMapElement()

Beitrag von Josh »

Ich muss das noch mal aufwärmen. Das was Stargate geschriebn hat, hab ich noch mit ein wenig Bauchweh hingenommen.

Was ich jetzt aber nicht kapiere, wie kann es sein, dass das löschen der Mapeinträge mit ClearMap() doppelt so lange dauert wie das Anlegen:

Code: Alles auswählen

#nboSlots = 1000000

time1 = ElapsedMilliseconds()
  NewMap MyMap$(#nboSlots)
time1 = ElapsedMilliseconds() - time1

time2 = ElapsedMilliseconds()
  For i = 1 To #nboSlots
    AddMapElement (MyMap$(), "" + i)
  Next
time2 = ElapsedMilliseconds() - time2

time3 = ElapsedMilliseconds()
  ClearMap (MyMap$())
time3 = ElapsedMilliseconds() - time3


time$ = "" + time1 + #CRLF$ + time2 + #CRLF$ + time3
MessageRequester ("", time$)
ccode_new
Beiträge: 1214
Registriert: 27.11.2016 18:13
Wohnort: Erzgebirge

Re: DeleteMapElement()

Beitrag von ccode_new »

Hallo Josh!

Wie testest du deinen Code ?

Beachtung von:

-laufende Prozesse die irgendetwas Ausbremsen. (Verlangsamung)
-laufende Virenscanner, etc.
-Ist der Debugger aus ?

Bei meinem Test auf meiner Hardware ist ClearMap() nie langsamer. (Test unter Linux (mit Linux-API) -daher vielleicht bedingt aussagekräftig)

0
211
138
Betriebssysteme: div. Windows, Linux, Unix - Systeme

no Keyboard, press any key
no mouse, you need a cat
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: DeleteMapElement()

Beitrag von STARGÅTE »

ich erhalte:
---------------------------

---------------------------
0
247
96
---------------------------
OK
---------------------------
Bei mir ist ClearMap schneller.
_______

Ich kann dein Bauchweh durchaus nachvollziehen.
Ich selbst konnte damals nicht nachvollziehen, warum das Löschen von Listenelementen so viel länger dauerte, wenn die Liste danach leer ist. Wie folgender Code zeigt, genügt ein "fake" Element am Anfang um das Löschen zu Beschleunigen!

Code: Alles auswählen

#nboSlots = 1000000

time1 = ElapsedMilliseconds()
	NewList MyList()
time1 = ElapsedMilliseconds() - time1

time2 = ElapsedMilliseconds()
	For i = 1 To #nboSlots
		AddElement(MyList())
		DeleteElement(MyList())
	Next
time2 = ElapsedMilliseconds() - time2

time3 = ElapsedMilliseconds()
	AddElement(MyList()) ; Fake Element
	For i = 1 To #nboSlots
		AddElement(MyList())
		DeleteElement(MyList())
	Next
time3 = ElapsedMilliseconds() - time3

time$ = "" + time1 + #CRLF$ + time2 + #CRLF$ + time3
MessageRequester ("", time$)
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
Josh
Beiträge: 1028
Registriert: 04.08.2009 17:24

Re: DeleteMapElement()

Beitrag von Josh »

Alles ok. Habe gerade an einem alten Nicht-Unicode Programm in 5.46 gearbeitet:
0
383
755

Auf den aktuellen Pb-Versionen ist alles ok, da bekomme ich folgende Werte:
0
365
115

Habe nicht auf die Version geachtet, wusste allerdings auch nicht, dass sich zwischen diesen Versionen etwas an den Maps geändert hat.


@Stargate
Interessantes Beispiel
ccode_new
Beiträge: 1214
Registriert: 27.11.2016 18:13
Wohnort: Erzgebirge

Re: DeleteMapElement()

Beitrag von ccode_new »

Na dann ist ja alles ok!

Assemblertechnisch sieht das unter Linux wie folgt aus:

(STARGÅTE-Code) - PureBasic 5.71 x64 Linux

Code: Alles auswählen

; Code:
l_code:
; #nboSlots = 1000000
; 
; time1 = ElapsedMilliseconds()
  CALL   PB_ElapsedMilliseconds
  MOV    qword [v_time1],rax
; NewList MyList()
  PUSH   qword [t_MyList]
  POP    rdi
  CALL   PB_FreeList
  MOV    rcx,21
  XOR    rdx,rdx
  LEA    rsi,[t_MyList]
  MOV    rdi,8
  CALL   PB_NewList
; time1 = ElapsedMilliseconds() - time1
  CALL   PB_ElapsedMilliseconds
  MOV    r15,rax
  SUB    r15,qword [v_time1]
  MOV    qword [v_time1],r15
; 
; time2 = ElapsedMilliseconds()
  CALL   PB_ElapsedMilliseconds
  MOV    qword [v_time2],rax
; For i = 1 To #nboSlots
  MOV    qword [v_i],1
  JMP   _ForSkipDebug1
_For1:
_ForSkipDebug1:
  MOV    rax,1000000
  CMP    rax,qword [v_i]
  JL    _Next2
; AddElement(MyList())
  PUSH   qword [t_MyList]
  POP    rdi
  CALL   PB_AddElement
; DeleteElement(MyList())
  PUSH   qword [t_MyList]
  POP    rdi
  CALL   PB_DeleteElement
; Next
_NextContinue2:
  INC    qword [v_i]
  JNO   _For1
_Next2:
; time2 = ElapsedMilliseconds() - time2
  CALL   PB_ElapsedMilliseconds
  MOV    r15,rax
  SUB    r15,qword [v_time2]
  MOV    qword [v_time2],r15
; 
; time3 = ElapsedMilliseconds()
  CALL   PB_ElapsedMilliseconds
  MOV    qword [v_time3],rax
; AddElement(MyList()) 
  PUSH   qword [t_MyList]
  POP    rdi
  CALL   PB_AddElement
; For i = 1 To #nboSlots
  MOV    qword [v_i],1
  JMP   _ForSkipDebug3
_For3:
_ForSkipDebug3:
  MOV    rax,1000000
  CMP    rax,qword [v_i]
  JL    _Next4
; AddElement(MyList())
  PUSH   qword [t_MyList]
  POP    rdi
  CALL   PB_AddElement
; DeleteElement(MyList())
  PUSH   qword [t_MyList]
  POP    rdi
  CALL   PB_DeleteElement
; Next
_NextContinue4:
  INC    qword [v_i]
  JNO   _For3
_Next4:
; time3 = ElapsedMilliseconds() - time3
  CALL   PB_ElapsedMilliseconds
  MOV    r15,rax
  SUB    r15,qword [v_time3]
  MOV    qword [v_time3],r15
; 
; time$ = "" + time1 + #CRLF$ + time2 + #CRLF$ + time3
Betriebssysteme: div. Windows, Linux, Unix - Systeme

no Keyboard, press any key
no mouse, you need a cat
Antworten