DeleteMapElement()

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

DeleteMapElement()

Beitrag von Josh »

Habe ich da einen Denkfehler oder steckt da in DeleteMapElement() ein Fehler. Das Löschen der Mapeinträge dauert ca. 40x so lange wie das Anlegen. Das Verhältnis verschlimmert sich sogar noch, wenn ich #cntMax erhöhe.

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()
ForEach MyMap()
  DeleteMapElement (MyMap())
 ;NextMapElement (MyMap())
Next
time2 = ElapsedMilliseconds() - time2


MessageRequester ("", "" + time1 + #CRLF$ + time2)
Wenn ich NextMapElement() auskommentiere, dann stimmen die Zeiten wieder. Allerdings wird dann logischerweise nur jedes zweite Element gelöscht.

Getestet Win7
Benutzeravatar
silbersurfer
Beiträge: 174
Registriert: 06.07.2014 12:21

Re: DeleteMapElement()

Beitrag von silbersurfer »

Wenn ich NextMapElement() auskommentiere, dann stimmen die Zeiten wieder. Allerdings wird dann logischerweise nur jedes zweite Element gelöscht.
Hallo Josh, ich habe zwar noch nicht Maps verwendetet aber das verhalten sollte ja ähnlich wie von Listen sein,
die Scheife geht doch alle vorhanden Einträge der Map durch, also sollte "DeleteMapElement (MyMap())" doch jeden Eintrag löschen und nicht jeden zweiten.
NextMapElement(Map()) wird ja nicht in einer Foreach schleife verwendet diese ist ja spezial für Maps-listen gedacht sondern in normalen schleifen
EDIT: ok jetzt habe nach dem zweiten mal durchlesen verstanden was was du meinst, aber wenn du alle Einträge Löschen willst warum nutzt du dann nicht ClearMap() ?

Code: Alles auswählen

ForEach MyMap()
  DeleteMapElement (MyMap())
 ;NextMapElement (MyMap())
Next
Intel Quad Core 3,2 Ghz - GTX 1060 - BlitzBasic Plus 1.48 , PureBasic 5.70 LTS / Aktuelles Projekt PureCommander
Benutzeravatar
Josh
Beiträge: 1028
Registriert: 04.08.2009 17:24

Re: DeleteMapElement()

Beitrag von Josh »

silbersurfer hat geschrieben:... aber wenn du alle Einträge Löschen willst warum nutzt du dann nicht ClearMap() ?
Im richtigen Programm steht in der ForEach-Schleife noch eine If-Abfrage.
Benutzeravatar
silbersurfer
Beiträge: 174
Registriert: 06.07.2014 12:21

Re: DeleteMapElement()

Beitrag von silbersurfer »

Im richtigen Programm steht in der ForEach-Schleife noch eine If-Abfrage.
Achso, ja dann sieht es so aus das es wirklich an deletemap liegt, denn auch in einer normalen Schleife ist er so langsam.

Code: Alles auswählen

  ResetMap(MyMap())
  While NextMapElement(MyMap())
    DeleteMapElement (MyMap())
  Wend
ist auch bei 480 ms
Intel Quad Core 3,2 Ghz - GTX 1060 - BlitzBasic Plus 1.48 , PureBasic 5.70 LTS / Aktuelles Projekt PureCommander
matbal
Beiträge: 246
Registriert: 30.03.2011 20:53

Re: DeleteMapElement()

Beitrag von matbal »

Mich würde interessieren, warum das Löschen so extrem viel langsamer ist als das Anlegen der Elemente. Interessant ist nämlich, daß das Löschen der Map-Elemente in einer For-Schleife genauso schnell ist wie das Anlegen der Map-Elemente.

Ein Workaround wäre: Ich sammle zuerst die Keys der Elemente, die ich löschen will, in einer Liste. Danach lösche ich die Elemente mit diesen Keys. Das geht bei mir deutlich schneller.

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()
; ForEach MyMap()
;   DeleteMapElement (MyMap())
;  ;NextMapElement (MyMap())
; Next


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


NewList key.s()
ForEach MyMap()
   AddElement(key()) : key() = MapKey(MyMap()) 
Next
ForEach key()
   DeleteMapElement(MyMap(), key())
Next 
FreeList(key())

;Debug MapSize(MyMap())

time2 = ElapsedMilliseconds() - time2 


MessageRequester ("", "" + time1 + #CRLF$ + time2)
Benutzeravatar
Bisonte
Beiträge: 2427
Registriert: 01.04.2007 20:18

Re: DeleteMapElement()

Beitrag von Bisonte »

Josh hat geschrieben: Wenn ich NextMapElement() auskommentiere, dann stimmen die Zeiten wieder. Allerdings wird dann logischerweise nur jedes zweite Element gelöscht.

Getestet Win7
Die Aussage widerlege ich :
Ich lass dein Beispiel durchlaufen und zeige im MsgReq noch die MapSize mit an.

Code: Alles auswählen

ForEach MyMap()
  DeleteMapElement (MyMap())
Next

Anlegen : 4ms
Löschen : 130ms
MapElemente : 0

Code: Alles auswählen

ForEach MyMap()
  DeleteMapElement (MyMap())
  NextMapElement()
Next

Anlegen : 4ms
Löschen : 1ms
MapElemente : 15000 (also die Hälfte)

Aber nichtsdestotroz würde ich matbal's Variante wählen, wenn nicht die ganze Map gelöscht werden soll.
PureBasic 6.04 LTS (Windows x86/x64) | Windows10 Pro x64 | Asus TUF X570 Gaming Plus | R9 5900X | 64GB RAM | GeForce RTX 3080 TI iChill X4 | HAF XF Evo | build by vannicom​​
Benutzeravatar
HeX0R
Beiträge: 2954
Registriert: 10.09.2004 09:59
Computerausstattung: AMD Ryzen 7 5800X
96Gig Ram
NVIDIA GEFORCE RTX 3060TI/8Gig
Win10 64Bit
G19 Tastatur
2x 24" + 1x27" Monitore
Glorious O Wireless Maus
PB 3.x-PB 6.x
Oculus Quest 2
Kontaktdaten:

Re: DeleteMapElement()

Beitrag von HeX0R »

Bisonte hat geschrieben:
Josh hat geschrieben: Wenn ich NextMapElement() auskommentiere, dann stimmen die Zeiten wieder. Allerdings wird dann logischerweise nur jedes zweite Element gelöscht.

Getestet Win7
Die Aussage widerlege ich :
Eigentlich hast Du eher die Aussage bewiesen.
Dieses "auskommentiere" ist das Wort in besagter Behauptung, das glaube ich jeden hier (kurzzeitig) verwirrt hat.
Hätte man auch geschickter formulieren können :lol:
Benutzeravatar
Josh
Beiträge: 1028
Registriert: 04.08.2009 17:24

Re: DeleteMapElement()

Beitrag von Josh »

HeX0R hat geschrieben:Hätte man auch geschickter formulieren können :lol:
Ja, hätte man definitiv :lol: Z.b.: ausauskommentieren, entauskommentieren .... :mrgreen:

Das Fatale an der ganzen Gschicht ist, dass die Zeit zum löschen zum Quadrat der Einträge steigt:

Code: Alles auswählen

   1k Einträge        1 ms
  10k Einträge       58 ms
 100k Einträge     5606 ms
1000k Einträge   564731 ms
Und was noch komisch ist, mit Debugger geht das löschen ungefähr 25% schneller als bei ausgeschalteten Debugger :|
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: DeleteMapElement()

Beitrag von STARGÅTE »

@Josh:

Das Langsame ist hier nicht das Löschen der Elemente mit DeleteMapElement() sondern das "unnatürliche" durchlaufen der Map mit ForEach oder NextMapElement(). Mit deinem Testcode änderst du sowohl die Anzahl der Slots als auch die Anzahl der Elemente, somit werden zwei Parameter des Tests verändert!

Eine Map ist nun mal keine Liste, somit gibt es keine Verbindung zwischen den Elementen, und daher wird der gesamte Map-Space komplett (jeder Slot) nach Elementen durchsucht.
Daraus folgt logischerweise, dass ForEach MyMap() je länger dauert, je höher die Anzahl der Slots ist, und nicht (nicht nur) je mehr Elemente es gibt.

Du kannst also das Durchlaufen der Map beschleunigen, indem nur nicht so viele Slots reservierst.
Es ist sowieso nicht sinnvoll genauso viele Slots anzulegen wie du Elemente hast, da es so oder so zu Kollisionen kommen kann.
Wenn du Stattdessen nur 1/10 an Slots reservierst, steigt AddMapElement() nur um
etwa 40%, dafür ist "ForEach" halt 10 mal schneller.

Überlege dir noch mal genau, was du eigentlich brauchst:
- Eine Liste mit Verknüpfungen zwischen den Elementen für schnelles Durchlaufen der Liste?
- Ein Array wo es exakt ein Slot pro Element gibt und ein schneller Direkter Zugriff gewährt ist?
- Eine Map bei es eine unbekannte Menge an Elementen Gibt, direkter Zugriff verlangt wird aber kein Durchlaufen der Elemente.

Ich verwende auch gerne Mischformen:
Ich lege eine Map mit den Elementen an und eine Liste mit Pointern zu diesen Elementen (oder auch andersherum). So kann ich beide Vorteile nutzen.
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
helpy
Beiträge: 635
Registriert: 29.08.2004 13:29

Re: DeleteMapElement()

Beitrag von helpy »

Code: Alles auswählen

For i = 1 To #cntMax
  DeleteMapElement(MyMap(), "x" + i)
Next
Das ist die schnellste Methode die Elemente einzeln zu löschen ;-)
Windows 10
PB Last Final / (Sometimes testing Beta versions)
Antworten