Pointer und #PB_Any direkt als MapKey verwenden
Re: Pointer und #PB_Any direkt als MapKey verwenden
wenn er memory alloziiert z.b. für ein oop objekt, und die addresse noch eben in eine map packt, dann kann er in anderen methoden des objektes leicht ein IsObjekt() implementieren um pointer zu verifizieren.
<edit>
mein lokaler test war übrigens fehlerhaft. Hex() ist bei kleineren zahlen nur ein kleines bisschen langsamer als Str(), bei grösseren zahlen aber etwas schneller. getestet ohne map.
der test mit map ist bei mir wieder schneller mit Str() wenn man die anzahl der slots erhöht.
<edit>
mein lokaler test war übrigens fehlerhaft. Hex() ist bei kleineren zahlen nur ein kleines bisschen langsamer als Str(), bei grösseren zahlen aber etwas schneller. getestet ohne map.
der test mit map ist bei mir wieder schneller mit Str() wenn man die anzahl der slots erhöht.
Re: Pointer und #PB_Any direkt als MapKey verwenden
Verwende ich auch zum Beispiel bei Modul NetworkData die Server und Clients zu verwalten.
Somit kann ich die zurückgegebene ServerID dazu verwenden um zusätzlich Informationen zum Server zu verwalten (Threads, Callbacks, etc)
Somit kann ich die zurückgegebene ServerID dazu verwenden um zusätzlich Informationen zum Server zu verwalten (Threads, Callbacks, etc)
Alles ist möglich, fragt sich nur wie...
Projekte ThreadToGUI / EventDesigner V3 / OOP-BaseClass-Modul
Downloads auf MyWebspace / OneDrive
Projekte ThreadToGUI / EventDesigner V3 / OOP-BaseClass-Modul
Downloads auf MyWebspace / OneDrive
Re: Pointer und #PB_Any direkt als MapKey verwenden
Je nach Anzahl der Kollisionen ist die eine schneller, oder die andere.
Bei 10-facher Slotanzahl für 10 Millionen Einträge (also 100 Millionen Slots)
sind beide Varianten bei mir manchmal sogar auf die Millisekunde identisch.
Mit Hex() gewinnt man also leider gar nichts. Da hilft nur eine native
Implementierung, die Integer als Keys erlaubt.
Du musst ein Schritt weiter denken Stargate. Natürlich macht es keinen
Sinn als Wert den Schlüssel selber zu nehmen, aber das ist doch nur ein
abstraktes Beispiel. In realen Umständen ist der Schlüsssel eine Zahl und
der Wert eine andere.
MFG PMV
Bei 10-facher Slotanzahl für 10 Millionen Einträge (also 100 Millionen Slots)
sind beide Varianten bei mir manchmal sogar auf die Millisekunde identisch.
Mit Hex() gewinnt man also leider gar nichts. Da hilft nur eine native
Implementierung, die Integer als Keys erlaubt.
Du musst ein Schritt weiter denken Stargate. Natürlich macht es keinen
Sinn als Wert den Schlüssel selber zu nehmen, aber das ist doch nur ein
abstraktes Beispiel. In realen Umständen ist der Schlüsssel eine Zahl und
der Wert eine andere.
MFG PMV
Re: Pointer und #PB_Any direkt als MapKey verwenden
Ich hab mal deine Idee aufgegriffen und ich denke ich habs verbessert:
der Trick ist, zwei Integer zu schreiben. Beim ersten setzt du das erste Bit immer auf 1 und beim zweiten setzt nimmst du nur das erste Bit und setzt das zweite auf 1. Damit sind alle Bits von Ursprung vorhanden.
Der Code funktioniert nur mit unicode.
Edit: Bringt leider nicht so viel: ca. 1600ms vs 2200ms auf der Bürokrücke in der Arbeit.
Code: Alles auswählen
CompilerIf #PB_Compiler_Unicode=#False
Debug "NÖNÖ"
End
CompilerEndIf
Threaded _handlestring.s
Threaded *_g1.integer,*_g2.integer
CompilerIf SizeOf(integer)=4
#_handlemask=$11111111
#_handleadd= $22222222
CompilerElseIf SizeOf(integer)=8
#_handlemask=$1111111111111111
#_handleadd= $2222222222222222
CompilerElse
CompilerError("Unbekannter Integertyp")
End
CompilerEndIf
;das muss jetzt in jeden neuen Thread!
Procedure INIT_Handlestring()
_handlestring=Space(SizeOf(integer))
*_g1=@_handlestring
*_g2=@_handlestring+SizeOf(integer)
EndProcedure
INIT_Handlestring()
NewMap Value.i()
start = ElapsedMilliseconds()
For i = 1 To 200000
Gadget = i
*_g1\i= (i | #_handlemask)
*_g2\i= (i & #_handlemask) | #_handleadd
If Value(_handlestring) = 0
value()=i
Else
err.s+"FehlerStruc1 "
EndIf
Next
time1 = ElapsedMilliseconds() - start
ClearMap(Value())
start = ElapsedMilliseconds()
For i = 1 To 200000
Gadget = i
If Value(Hex(i))=0
value()= i
Else
err.s+"FehlerSTR1 "
EndIf
Next
time2 = ElapsedMilliseconds() - start
r1.s = "Zeit für kleine Zahlen" + #LF$ + "Struct: " + Str(time1) + #LF$ + "String: " + Str(time2)
ClearMap(Value())
start = ElapsedMilliseconds()
For i = 100000000 To 100200000
Gadget = i
*_g1\i= (i | #_handlemask)
*_g2\i= (i & #_handlemask) | #_handleadd
If Value(_handlestring)=0
value()= i
Else
err.s+"FehlerStruc2 "
EndIf
Next
time1 = ElapsedMilliseconds() - start
ClearMap(Value())
start = ElapsedMilliseconds()
For i = 100000000 To 100200000
Gadget = i
If Value(Hex(i))=0
value()= i
Else
err.s+"FehlerSTR2 "
EndIf
Next
time2 = ElapsedMilliseconds() - start
r1 + #LF$ + #LF$ + "Zeit für große Zahlen (Pointer, #PB_Any)" + #LF$ + "Struct: " + Str(time1) + #LF$ + "String: " + Str(time2)+#LF$+err
MessageRequester("Result", r1)
Der Code funktioniert nur mit unicode.
Edit: Bringt leider nicht so viel: ca. 1600ms vs 2200ms auf der Bürokrücke in der Arbeit.
CodeArchiv Rebirth: Deutsches Forum Github Hilfe ist immer gern gesehen!
Re: Pointer und #PB_Any direkt als MapKey verwenden
Wobei, wenn man die Testbedingungen ändert (Werte in Extrembereich + zufällige Reihenfolge) und getrennt erstellung und suchen testet, dann sieht es schon anders aus:
Die Struc-Lösung ist ca. 40% schneller hier auf der Krücke.
edit: Selbst wenn man das in eine Procedure packt ist es ungefähr genauso schnell!
und oh, ganz lustig:
wenn man xmap statt bin benutzt, dann ist es zu der anderen lösung grob 1% langsamer.... dafür fast gleich zu benutzen. Damit deutlich schneller als Bin...
Code: Alles auswählen
Structure sortdata
index.i
random.i
EndStructure
CompilerIf SizeOf(integer)=4
#_handlemask=$11111111
#_handleadd= $22222222
CompilerElseIf SizeOf(integer)=8
#_handlemask=$1111111111111111
#_handleadd= $2222222222222222
CompilerElse
CompilerError("Unbekannter Integertyp")
End
CompilerEndIf
Procedure findmap(Map ma.sortdata(),i)
Static _handlestring.s
Static *_g1.integer,*_g2.integer
If *_g1=0
_handlestring=Space(SizeOf(integer))
*_g1=@_handlestring
*_g2=@_handlestring+SizeOf(integer)
EndIf
*_g1\i= (i | #_handlemask)
*_g2\i= (i & #_handlemask) | #_handleadd
ma(_handlestring)
EndProcedure
;Testdaten erstellen
;wir füllen die Liste Testdata() mit einer Indexzahl (fortlaufend) und eine zufallszahl
;anschließend sortieren wir die liste nach der Zufallszahl
;die so gewürfelte Liste nutzen wir, um beide listen mit den gleichen Zahlen
;in der gleichen Reihenfolge zu füllen.
testT1=ElapsedMilliseconds()
#num=40000
CompilerIf #PB_Compiler_Processor=#PB_Processor_x86
#max=2147483647
CompilerElse
#max=9223372036854775807
CompilerEndIf
NewList testdata.sortdata()
For i = -#num To #num
AddElement(testdata())
testdata()\index=i
testdata()\random=Random(#max)
Next
For i = #max-#num To #max
AddElement(testdata())
testdata()\index=i
testdata()\random=Random(#max)
Next
For i = -#max To -(#max-#num)
AddElement(testdata())
testdata()\index=i
testdata()\random=Random(#max)
Next
SortStructuredList(testdata(),#PB_Sort_Ascending,OffsetOf(sortdata\random),#PB_Integer)
testt2=ElapsedMilliseconds()
err.s=""
;Test 1 mit BIN als index. Map füllen
t1=ElapsedMilliseconds()
NewMap test.sortdata()
ForEach testdata()
i=testdata()\index
test(Hex(i))\index=i
Next
t2=ElapsedMilliseconds()
;Test 2 mit BIN als Index. Map abfragen und überprüfen
ForEach testdata()
i=testdata()\index
If test(Hex(i))\index<>i
err.s+"Fehler Map"
EndIf
Next
t3=ElapsedMilliseconds()
;test 3 mit "findmap"/Struc. Map füllen
u1=ElapsedMilliseconds()
NewMap test2.sortdata()
ForEach testdata()
i=testdata()\index
findmap(test2(),i)
test2()\index=i
Next
u2=ElapsedMilliseconds()
;Test 4 mit "findmap"/struc. Map abfragen und überprüfen
ForEach testdata()
i=testdata()\index
findmap(test2(),i)
If test2()\index<>i
err.s+"Fehler List"
EndIf
Next
u3=ElapsedMilliseconds()
;Und alles ausgeben
MessageRequester("test","Testdaten erzeugen:"+Str(testt2-testt1)+" Count:"+ListSize(testdata())+#LF$+
"Bin gen:"+Str(t2-t1)+" find:"+Str(t3-t2) +" Count:"+MapSize(test())+#LF$+
"Struc gen:"+Str(u2-u1)+" find:"+Str(u3-u2)+" Count:"+MapSize(test2())+#LF$+
"Gen:"+StrD(100-100.0/(t2-t1)*(u2-u1),2)+"% find:"+StrD(100-100.0/(t3-t2)*(u3-u2),2)+"%")
edit: Selbst wenn man das in eine Procedure packt ist es ungefähr genauso schnell!
und oh, ganz lustig:
Code: Alles auswählen
CompilerIf #PB_Compiler_Processor=#PB_Processor_x86
#_handlemask=$11111111
#_handleadd= $22222222
CompilerElse
#_handlemask=$1111111111111111
#_handleadd= $2222222222222222
CompilerEndIf
Procedure.s XMap(i)
Static _handlestring.s
Static *_g1.integer,*_g2.integer
If *_g1=0
_handlestring=Space(SizeOf(integer))
*_g1=@_handlestring
*_g2=@_handlestring+SizeOf(integer)
EndIf
*_g1\i= (i | #_handlemask)
*_g2\i= (i & #_handlemask) | #_handleadd
ProcedureReturn _handlestring
EndProcedure
Zuletzt geändert von GPI am 31.08.2017 00:05, insgesamt 1-mal geändert.
CodeArchiv Rebirth: Deutsches Forum Github Hilfe ist immer gern gesehen!
Re: Pointer und #PB_Any direkt als MapKey verwenden
Irgendwie hast du nur 40000 Einträge. Stelle ich diesen auf 200000 Einträge wird dein code nie fertig
Der mit Hex ist immer noch ein kleines Stück schneller als mit String.
Braucht bei mir etwa 500 Millisekunden die 200000 Einträge durchzuführen führen
Geht also mit Hex schon schnell genug. Jeder andere Code der nicht in ASM geschrieben ist, ist langsamer...
Der mit Hex ist immer noch ein kleines Stück schneller als mit String.
Braucht bei mir etwa 500 Millisekunden die 200000 Einträge durchzuführen führen
Code: Alles auswählen
Define r1.s
NewMap ValueH.i(2048)
NewMap ValueS.i(2048)
start = ElapsedMilliseconds()
For i = 1 To 200000
ValueH(Hex(i)) = i
Next
time1 = ElapsedMilliseconds() - start
start = ElapsedMilliseconds()
For i = 1 To 200000
ValueS(Str(i)) = i
Next
time2 = ElapsedMilliseconds() - start
r1 = "Zeit für kleine Zahlen anlegen" + #LF$ + "Hex: " + Str(time1) + #LF$ + "String: " + Str(time2)
r1 + #LF$ + "Count of Map Hex: " + Str(MapSize(ValueH()))
r1 + #LF$ + "Count of Map String: " + Str(MapSize(ValueS()))
ClearMap(ValueH())
ClearMap(ValueS())
start = ElapsedMilliseconds()
For i = 1 To 200000
a = Random(60000000, 10000000)
ValueH(Hex(a)) = a
Next
time1 = ElapsedMilliseconds() - start
start = ElapsedMilliseconds()
For i = 1 To 200000
a = Random(60000000, 10000000)
ValueS(Str(a)) = a
Next
time2 = ElapsedMilliseconds() - start
r1 + #LF$ + #LF$ + "Zeit für große Zahlen anlegen (Pointer, #PB_Any)" + #LF$ + "Hex: " + Str(time1) + #LF$ + "String: " + Str(time2)
a = 0
start = ElapsedMilliseconds()
For i = 1 To 200000
If FindMapElement(ValueH(), Hex(Random(60000000, 10000000)))
a + 1
EndIf
Next
time1 = ElapsedMilliseconds() - start
a = 0
start = ElapsedMilliseconds()
For i = 1 To 200000
If FindMapElement(ValueS(), Str(Random(60000000, 10000000)))
a + 1
EndIf
Next
time2 = ElapsedMilliseconds() - start
r1 + #LF$ + #LF$ + "Zeit für suchen große Zahlen (Pointer, #PB_Any)" + #LF$ + "Zeit: " + Str(time1) + #LF$ + "String: " + Str(time2)
r1 + #LF$ + #LF$ + "Count of Map Hex: " + Str(MapSize(ValueH()))
r1 + #LF$ + "Count of Map String: " + Str(MapSize(ValueS()))
MessageRequester("Result", r1)
Alles ist möglich, fragt sich nur wie...
Projekte ThreadToGUI / EventDesigner V3 / OOP-BaseClass-Modul
Downloads auf MyWebspace / OneDrive
Projekte ThreadToGUI / EventDesigner V3 / OOP-BaseClass-Modul
Downloads auf MyWebspace / OneDrive
Re: Pointer und #PB_Any direkt als MapKey verwenden
Dein Testcode finde ich ehrlich gesagt seltsam.
zum einen fügst du in die Map nur immer neue Zahlen/MapKey rein, zum anderen sind die immer linear aufsteigend. Für mich ein ungünstiges Szenario. Dafür würde ich eine Linked List nehmen, ist deutlich schneller. Der Gag ist doch, das "I" nicht einfach reinkommt.
Darum erstelle ich erstmal eine LInked List Testdata() mit einer Index-Zahl und einer Randomzahl. ich wähle als Index die Zahl von -#num bis +#num, -#max bis -(#max-#min) und (#max-min) bis #max. Jede Zahl bekommt eine Zufallszahl zugewiesen.
Jetzt wird die Structur nach der Zufallszahl sortiert.
Ich benutzte dann einfach eine simple ForEach-Next-Schleife um mit den Indexzahlen als MapKey die Maps zu füllen.
Was die Mapfüllung angeht, teste ich hier zwei Szenarien. Generierung und Abfrage. Bei der Generierung gibt es den Eintrag nicht und muss angelegt werden. Ich geh davon aus, dass das deutlich langsamer ist als ein einfaches raussuchen. In der ersten Schleife wird also nur gefüllt.
In der zweiten Schleife wird in der Map abgefragt und gleichzeitig überprüft, ob das richtige Element erwischt wurde.
Übrigens werden bei meinen Beispielcode 160.003 Einträge erzeugt, nicht 40.000
Warum mein Code so "Langsam" ist gegenüber deinen, ist schnell geklärt: Dadurch, das ich willkürlich und nicht in Reihe MapKeys verwende, dauert es bei mir länger. Das ist ein Problem der MAP-Befehle, nicht der MapKey-Erstellung.
Und braucht hier jetzt (32 bit)
Testdaten erzeugen: 32ms
Bin Gen:3050ms, find 2939ms
Struc Gen:1996ms, find 2010ms
Unter 64 Bit
Testdaten erzeugen: 62ms
Bin Gen:3900ms, find 3527ms
Struc Gen:2972ms, find 2945ms
Ich editiere gleich den Post eins drüber mit einer besseren Ausgabe und kommentaren.
Edit: Aber probier mal die Methode XMAP() gegen BIN() aus. Bei deinen Code ist er ungefähr gleich schnell bis hin zu schneller. Bei meinen Code mit gewürfelten MapKeys ist er deutlich schneller.
Ich denke mal, das die MAP-Routinen meinen XMAP-String lieber mag, da er immer gleich lang ist (in Gegensatz zu HEX()) und sich vermutlich leichter sortieren lässt. Er dürfte auch kürzer sein. Das macht wohl den großen Unterschied.
zum einen fügst du in die Map nur immer neue Zahlen/MapKey rein, zum anderen sind die immer linear aufsteigend. Für mich ein ungünstiges Szenario. Dafür würde ich eine Linked List nehmen, ist deutlich schneller. Der Gag ist doch, das "I" nicht einfach reinkommt.
Darum erstelle ich erstmal eine LInked List Testdata() mit einer Index-Zahl und einer Randomzahl. ich wähle als Index die Zahl von -#num bis +#num, -#max bis -(#max-#min) und (#max-min) bis #max. Jede Zahl bekommt eine Zufallszahl zugewiesen.
Jetzt wird die Structur nach der Zufallszahl sortiert.
Ich benutzte dann einfach eine simple ForEach-Next-Schleife um mit den Indexzahlen als MapKey die Maps zu füllen.
Was die Mapfüllung angeht, teste ich hier zwei Szenarien. Generierung und Abfrage. Bei der Generierung gibt es den Eintrag nicht und muss angelegt werden. Ich geh davon aus, dass das deutlich langsamer ist als ein einfaches raussuchen. In der ersten Schleife wird also nur gefüllt.
In der zweiten Schleife wird in der Map abgefragt und gleichzeitig überprüft, ob das richtige Element erwischt wurde.
Übrigens werden bei meinen Beispielcode 160.003 Einträge erzeugt, nicht 40.000
Warum mein Code so "Langsam" ist gegenüber deinen, ist schnell geklärt: Dadurch, das ich willkürlich und nicht in Reihe MapKeys verwende, dauert es bei mir länger. Das ist ein Problem der MAP-Befehle, nicht der MapKey-Erstellung.
Und braucht hier jetzt (32 bit)
Testdaten erzeugen: 32ms
Bin Gen:3050ms, find 2939ms
Struc Gen:1996ms, find 2010ms
Unter 64 Bit
Testdaten erzeugen: 62ms
Bin Gen:3900ms, find 3527ms
Struc Gen:2972ms, find 2945ms
Ich editiere gleich den Post eins drüber mit einer besseren Ausgabe und kommentaren.
Edit: Aber probier mal die Methode XMAP() gegen BIN() aus. Bei deinen Code ist er ungefähr gleich schnell bis hin zu schneller. Bei meinen Code mit gewürfelten MapKeys ist er deutlich schneller.
Ich denke mal, das die MAP-Routinen meinen XMAP-String lieber mag, da er immer gleich lang ist (in Gegensatz zu HEX()) und sich vermutlich leichter sortieren lässt. Er dürfte auch kürzer sein. Das macht wohl den großen Unterschied.
CodeArchiv Rebirth: Deutsches Forum Github Hilfe ist immer gern gesehen!
Re: Pointer und #PB_Any direkt als MapKey verwenden
Dein XMap ist etwas Schneller als Hex. Ca 10%
Habe deinen Code mal auf Threadsafe umgebaut
Habe deinen Code mal auf Threadsafe umgebaut
Code: Alles auswählen
;-TOP
; Comment: Stringkey aus Integer
; Author1: GPI
; Author2: mk-soft
; Date: 31.08.2017
CompilerIf #PB_Compiler_Processor=#PB_Processor_x86
#_handlemask=$11111111
#_handleadd= $22222222
Structure udtXMap
StructureUnion
key.i[2]
CompilerIf #PB_Compiler_Unicode
s.s{4}
CompilerElse
s.s{8}
CompilerEndIf
null.w
EndStructureUnion
EndStructure
CompilerElse
#_handlemask=$1111111111111111
#_handleadd= $2222222222222222
Structure udtXMap
StructureUnion
key.i[2]
CompilerIf #PB_Compiler_Unicode
s.s{8}
CompilerElse
s.s{16}
CompilerEndIf
null.w
EndStructureUnion
EndStructure
CompilerEndIf
Procedure.s XMap(i)
Protected r1.udtXMap
r1\key[0] = (i | #_handlemask)
r1\key[1] = (i & #_handlemask) | #_handleadd
ProcedureReturn r1\s
EndProcedure
Alles ist möglich, fragt sich nur wie...
Projekte ThreadToGUI / EventDesigner V3 / OOP-BaseClass-Modul
Downloads auf MyWebspace / OneDrive
Projekte ThreadToGUI / EventDesigner V3 / OOP-BaseClass-Modul
Downloads auf MyWebspace / OneDrive
- NicTheQuick
- Ein Admin
- Beiträge: 8679
- Registriert: 29.08.2004 20:20
- Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti - Wohnort: Saarbrücken
- Kontaktdaten:
Re: Pointer und #PB_Any direkt als MapKey verwenden
Ihr habt mich dazu inspiriert einfach eine eigene Map zu schreiben, die von Integer auf Integer mapt. Ob die schneller ist als eure, kann ich nicht sagen, da ich es nicht getestet habe. Aber Verbesserungspotential ist definitiv noch drin.
Eine zu niedrige Bucketgröße wirkt sich fatal aus. Und mit Debugger ist es wirklich sehr sehr langsam.
Code: Alles auswählen
EnableExplicit
DeclareModule MapI2I
EnableExplicit
Interface MapI2I
free.i()
set.i(key.i, value.i)
unset.i(key.i)
get.i(key.i)
is.i(key.i)
bucketsUsed.i()
elements.i()
EndInterface
Declare newMapI2I(buckets.i)
EndDeclareModule
Module MapI2I
EnableExplicit
Structure entry
key.i
value.i
*next.entry ; Wird zu beginn auf 1 gesetzt um zu signalisieren, dass das Element noch nicht existiert und Speicherplatz zu sparen
EndStructure
Structure entries
entry.entry[0]
EndStructure
Structure table
*vTable
buckets.i
bucketsUsed.i
elements.i
*entries.entries
EndStructure
; Siehe https://stackoverflow.com/a/12996028/4239139
CompilerIf SizeOf(Integer) = 4
Macro hash(x)
x = ((x >> 16) ! x) * $45d9f3b
x = ((x >> 16) ! x) * $45d9f3b
x = (x >> 16) ! x
EndMacro
CompilerElse
Macro hash(x)
x = (x ! (x >> 30)) * $bf58476d1ce4e5b9
x = (x ! (x >> 27)) * $94d049bb133111eb
x = x ! (x >> 31);
EndMacro
CompilerEndIf
Procedure newMapI2I(buckets.i)
Protected *this.table, i.i
If buckets < 1
ProcedureReturn #False
EndIf
*this = AllocateStructure(table)
If Not *this
ProcedureReturn #False
EndIf
With *this
\vTable = ?vTable_mapI2I
\buckets = buckets.i
\bucketsUsed = 0
\elements = 0
\entries = AllocateMemory(SizeOf(entry) * buckets, #PB_Memory_NoClear)
If Not \entries
FreeStructure(*this)
ProcedureReturn #False
EndIf
For i = 0 To buckets - 1
\entries\entry[i]\next = 1
Next
EndWith
ProcedureReturn *this
EndProcedure
Procedure.i free(*this.table)
Protected i.i, *entry.entry, *nextEntry.entry
With *this
For i = 0 To *this\buckets - 1
If \entries\entry[i]\next <> 1
*entry = \entries\entry[i]\next
While *entry
*nextEntry = *entry\next
FreeMemory(*entry)
*entry = *nextEntry
Wend
EndIf
Next
FreeMemory(\entries)
FreeStructure(*this)
EndWith
EndProcedure
Procedure.i is(*this.table, key.i)
Protected *entry.entry, bucket.i = key
hash(bucket)
bucket % *this\buckets
*entry = @*this\entries\entry[bucket]
If *entry\next = 1
ProcedureReturn #False
EndIf
While *entry
If *entry\key = key
ProcedureReturn #True
EndIf
*entry = *entry\next
Wend
ProcedureReturn #False
EndProcedure
Procedure.i get(*this.table, key.i)
Protected *entry.entry, bucket.i = key
hash(bucket)
bucket % *this\buckets
*entry = @*this\entries\entry[bucket]
If *entry\next = 1
ProcedureReturn #False
EndIf
While *entry
If *entry\key = key
ProcedureReturn *entry\value
EndIf
*entry = *entry\next
Wend
ProcedureReturn #False
EndProcedure
Procedure.i set(*this.table, key.i, value.i)
Protected *entry.entry, bucket.i = key, *lastEntry.entry
hash(bucket)
bucket % *this\buckets
*entry = @*this\entries\entry[bucket]
*lastEntry = *entry
If *entry\next = 1
*this\bucketsUsed + 1
Else
Repeat
If *entry\key = key
*entry\value = value
*this\elements + 1
ProcedureReturn *entry
EndIf
*lastEntry = *entry
*entry = *entry\next
Until Not *entry
EndIf
If *lastEntry\next = 1
*lastEntry\key = key
*lastEntry\value = value
*lastEntry\next = 0
*this\elements + 1
ProcedureReturn *lastEntry
Else
*lastEntry\next = AllocateMemory(SizeOf(entry), #PB_Memory_NoClear)
If Not *lastEntry\next
ProcedureReturn #False
EndIf
*lastEntry\next\key = key
*lastEntry\next\value = value
*lastEntry\next\next = 0
*this\elements + 1
ProcedureReturn *lastEntry\next
EndIf
EndProcedure
Procedure.i unset(*this.table, key.i)
Protected *entry.entry, bucket.i = key, *firstEntry.entry, *previousEntry.entry
hash(bucket)
bucket % *this\buckets
*entry = @*this\entries\entry[bucket]
*firstEntry = *entry
*previousEntry = *entry
If *entry\next = 1
ProcedureReturn #False
EndIf
While *entry
If *entry\key = key
If *entry = *firstEntry
If *entry\next = 0
; Der einzige Eintrag der LinkedList soll gelöscht werden
*this\bucketsUsed - 1
*entry\next = 1
Else
; Der erste Eintrag der LinkedList soll gelöscht werden und es folgt noch mindestens ein weiterer
*entry\key = *entry\next\key
*entry\value = *entry\next\value
*entry\next = *entry\next\next
EndIf
*this\elements - 1
ProcedureReturn #True
Else
; Der zweite oder einer der nachfolgenden Einträge soll gelöscht werden.
*previousEntry\next = *entry\next
FreeMemory(*entry)
*this\elements - 1
ProcedureReturn #True
EndIf
EndIf
*previousEntry = *entry
*entry = *entry\next
Wend
ProcedureReturn #False
EndProcedure
Procedure.i bucketsUsed(*this.table)
ProcedureReturn *this\bucketsUsed
EndProcedure
Procedure.i elements(*this.table)
ProcedureReturn *this\elements
EndProcedure
DataSection
vTable_mapI2I:
Data.i @free(), @set(), @unset(), @get(), @is(), @bucketsUsed(), @elements()
EndDataSection
EndModule
OpenConsole()
Define buckets.i = 100000
Define myMap.MapI2I::MapI2I = MapI2I::newMapI2I(buckets)
Define i.i, max = 1000000, key.i
; Erstelle ganz viele Element
RandomSeed(123)
For i = 1 To max
key.i = Random(1 << 16) + i << 16
If Not myMap\set(key, i)
PrintN("Oh oh. Konnte Element mit key " + key + " nicht anlegen.")
EndIf
Next
PrintN("Momentan genutzte Buckets: " + myMap\bucketsUsed() + " (" + StrD(100.0 * myMap\bucketsUsed() / buckets, 2) + ~"%)\nDurchschnittliche Elemente pro Bucket: " + StrD(myMap\elements() / myMap\bucketsUsed(), 2) + "%")
; Überprüfe ihren Inhalt
RandomSeed(123)
For i = 1 To max
key.i = Random(1 << 16) + i << 16
If myMap\get(key) <> i
PrintN("i=" + key + " sollte den Wert " + i + " haben, hat aber " + myMap\get(key))
EndIf
Next
; Lösche die Hälfte
RandomSeed(123)
For i = 1 To max
key.i = Random(1 << 16) + i << 16
If i & 1
If Not myMap\unset(key)
PrintN("Nanu? Wieso existiert der Eintrag " + key + " nicht?")
EndIf
EndIf
Next
PrintN("Momentan genutzte Buckets: " + myMap\bucketsUsed() + " (" + StrD(100.0 * myMap\bucketsUsed() / buckets, 2) + ~"%)\nDurchschnittliche Elemente pro Bucket: " + StrD(myMap\elements() / myMap\bucketsUsed(), 2) + "%")
; Überprüfe Löschung und die Existenz der restlichen
RandomSeed(123)
For i = 1 To max
key.i = Random(1 << 16) + i << 16
If myMap\is(key) And i & 1
PrintN("oh oh. Key " + key + " sollte nicht mehr existieren.")
ElseIf Not myMap\is(key) And i & 1 = 0
PrintN("oh oh. Key " + key + " sollte noch existieren.")
EndIf
Next
myMap\free()
PrintN("Ende Gelände.")
Input()
CloseConsole()
Re: Pointer und #PB_Any direkt als MapKey verwenden
@NicTheQuick
Also...
Ohne debugger etwa 40% schneller, mit debugger etwa 4 mal langsamer
Habe zum testen die Slot von Map auch auf 10000 gestellt.
Legt so aber leider noch Duplikate an. Somit prüfe ich das vorher mit Map\Is(). Kann aber so nicht das Value ändern.
Das Flag #PB_Map_ElementCheck (Default) und #PB_Map_NoElementCheck zu Map\Set() hinzufügen und dann ins Code,Tipp und Tricks
Also...
Ohne debugger etwa 40% schneller, mit debugger etwa 4 mal langsamer
Habe zum testen die Slot von Map auch auf 10000 gestellt.
Legt so aber leider noch Duplikate an. Somit prüfe ich das vorher mit Map\Is(). Kann aber so nicht das Value ändern.
Das Flag #PB_Map_ElementCheck (Default) und #PB_Map_NoElementCheck zu Map\Set() hinzufügen und dann ins Code,Tipp und Tricks
Alles ist möglich, fragt sich nur wie...
Projekte ThreadToGUI / EventDesigner V3 / OOP-BaseClass-Modul
Downloads auf MyWebspace / OneDrive
Projekte ThreadToGUI / EventDesigner V3 / OOP-BaseClass-Modul
Downloads auf MyWebspace / OneDrive