Aktuelle Zeit: 28.02.2020 01:05

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]




Ein neues Thema erstellen Auf das Thema antworten  [ 19 Beiträge ]  Gehe zu Seite Vorherige  1, 2
Autor Nachricht
 Betreff des Beitrags: Re: DeleteMapElement()
BeitragVerfasst: 07.09.2019 16:16 
Offline
Benutzeravatar

Registriert: 04.08.2009 17:24
@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:
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.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: DeleteMapElement()
BeitragVerfasst: 07.09.2019 17:36 
Offline

Registriert: 25.03.2013 09:59
@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:
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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: DeleteMapElement()
BeitragVerfasst: 07.09.2019 18:56 
Offline
Kommando SG1
Benutzeravatar

Registriert: 01.11.2005 13:34
Wohnort: Glienicke
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:
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:
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.

_________________
Bild
 
BildBildBild


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: DeleteMapElement()
BeitragVerfasst: 09.09.2019 21:05 
Offline
Benutzeravatar

Registriert: 04.08.2009 17:24
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.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: DeleteMapElement()
BeitragVerfasst: 25.11.2019 23:24 
Offline
Benutzeravatar

Registriert: 04.08.2009 17:24
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:
#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$)


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: DeleteMapElement()
BeitragVerfasst: 25.11.2019 23:57 
Offline

Registriert: 27.11.2016 18:13
Wohnort: Erzgebirge
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: MX Linux 19 / Windows 10 / Mac OS 10.15.2 / Android 7.0 ;)


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: DeleteMapElement()
BeitragVerfasst: 26.11.2019 00:10 
Offline
Kommando SG1
Benutzeravatar

Registriert: 01.11.2005 13:34
Wohnort: Glienicke
ich erhalte:
Zitat:
---------------------------

---------------------------
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:
#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$)

_________________
Bild
 
BildBildBild


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: DeleteMapElement()
BeitragVerfasst: 26.11.2019 00:36 
Offline
Benutzeravatar

Registriert: 04.08.2009 17:24
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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: DeleteMapElement()
BeitragVerfasst: 26.11.2019 00:39 
Offline

Registriert: 27.11.2016 18:13
Wohnort: Erzgebirge
Na dann ist ja alles ok!

Assemblertechnisch sieht das unter Linux wie folgt aus:

(STARGÅTE-Code) - PureBasic 5.71 x64 Linux
Code:
; 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: MX Linux 19 / Windows 10 / Mac OS 10.15.2 / Android 7.0 ;)


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 19 Beiträge ]  Gehe zu Seite Vorherige  1, 2

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 3 Gäste


Sie dürfen keine neuen Themen in diesem Forum erstellen.
Sie dürfen keine Antworten zu Themen in diesem Forum erstellen.
Sie dürfen Ihre Beiträge in diesem Forum nicht ändern.
Sie dürfen Ihre Beiträge in diesem Forum nicht löschen.

Suche nach:
Gehe zu:  

 


Powered by phpBB © 2008 phpBB Group | Deutsche Übersetzung durch phpBB.de
subSilver+ theme by Canver Software, sponsor Sanal Modifiye