Der Witz daran ist das z.B. wenn ich den Index 1205381 habe nicht 1 Mio. Einträge füllen muss sondern nur der Eintrag 1205381 erstellt wird. Hat natürlich zur Folge das jeder Eintrag mehr Platz im Speicher braucht als bei einem klassischem, ist also eher nicht dazu geeignet wenn man ein Array von 0 - ... füllen will. Das ganze basiert auf Ebenen. Jede Ebene umfast die Zahlen 0 - 9. Ist die Zahl größer wird eine Eben tiefer gegangen. 1205381 währe auf Ebene 1-8-3-5-0-2-1 (Tiefe 7).
Das Array ist trotzdem sehr schnell, wobei es die Möglichkeit gibt die Zahl vor dem Indexen zu drehen, was sich wie folgt auswirkt:
Bereich: 0 - 10 Mio, ohne drehen hat geschrieben:Schreiben & Erstellen: Zugriffe: 6958942.00/Sek
Lesen: Zugriffe: 8097166.00/Sek
Aufräumen: 0.44 sek
Bereich: 0 - 10 Mio, mit drehen hat geschrieben:Schreiben & Erstellen: Zugriffe: 4849660.50/Sek
Lesen: Zugriffe: 5333333.50/Sek
Aufräumen: 0.19 sek
Bereich: 10 Mio - 20 Mio, ohne drehen hat geschrieben:Schreiben & Erstellen: Zugriffe: 2006420.50/Sek
Lesen: Zugriffe: 3315649.75/Sek
Aufräumen: 12.77 sek
Man sieht, bei kleineren Zahlen drückt das drehen auf die Performance, bei höheren verbessert es sie.Auf jedem Fall bringt das drehen eine bessere Speichernutzung und eine schneller Aufräumzeit (im 2. Test 75x fach schneller!)Bereich: 10 Mio - 20 Mio, mit drehen hat geschrieben:Schreiben & Erstellen: Zugriffe: 4050222.75/Sek
Lesen: Zugriffe: 4384042.00/Sek
Aufräumen: 0.17 sek
Viel Spaß damit, Gruß cxAlex:
PS: Währe froh wenn jemand testen könnte ob der x64 - DrehCode funktioniert, hab hier leider keine Möglichkeit das zu testen.
Code: Alles auswählen
; ------------------------------------------------------------------------------------
; Intelligentes Array
; Author: Alexander Aigner
; PB 4.3+ x86/x64
; ------------------------------------------------------------------------------------
Structure IArray_Data ; Daten Element
*Next.IArray ; Tiefere Ebene
Value.i ; Eintrag
EndStructure
Structure IArray_Holder ; Array Holder
Entry.IArray_Data[10]
EndStructure
Structure IArray ; Array Main - Struktur
IArray.IArray_Holder
EndStructure
Procedure New_IArray() ; Neues Array anlegen
Protected *IArray = AllocateMemory(SizeOf(IArray))
ProcedureReturn *IArray
EndProcedure
Procedure TurnVal(Val) ; (x86, x64)
CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
!MOV EAX, dword[p.v_Val]
!MOV EBX, 10
!MOV ECX, 0
!@@:
!OR EAX, EAX
!JZ @f
!IMUL ECX, EBX
!CDQ
!IDIV EBX
!ADD ECX, EDX
!JMP @b
!@@:
!MOV EAX, ECX
ProcedureReturn
CompilerElse
!MOV RAX, qword[p.v_Val]
!MOV RBX, 10
!MOV RCX, 0
!@@:
!OR RAX, RAX
!JZ @f
!IMUL RCX, RBX
!CDQ
!IDIV RBX
!ADD RCX, RDX
!JMP @b
!@@:
!MOV RAX, RCX
ProcedureReturn
CompilerEndIf
EndProcedure
Procedure IArray_Set(*IArray.IArray, Index.i, Value.i) ; Eintrag setzen
Protected *IArrayEntry.IArray_Data, *cur.IArray_Holder
*cur = @*IArray\IArray
; Probeweise auskommntieren:
Index = TurnVal(Index)
; Element finden
Repeat
; Aktuelles Element
*IArrayEntry = @*cur\Entry[Index%10]
Index/10
If Index ; Weiter in die Tiefe
If Not *IArrayEntry\Next ; Noch nicht angelegt?
*IArrayEntry\Next = AllocateMemory(SizeOf(IArray))
EndIf
; eine Ebene tiefer gehen
*cur = *IArrayEntry\Next\IArray
EndIf
Until Not Index
; Eintrag schreiben
*IArrayEntry\Value = Value
EndProcedure
Procedure IArray_Get(*IArray.IArray, Index.i)
Protected *IArrayEntry.IArray_Data, *cur.IArray_Holder
; Probeweise auskommntieren:
Index = TurnVal(Index)
; Element finden ( Siehe oben)
*cur = @*IArray\IArray
Repeat
*IArrayEntry = @*cur\Entry[Index%10]
Index/10
If Index
If Not *IArrayEntry\Next
; Eintrag gibts noch nicht
ProcedureReturn 0
EndIf
*cur = *IArrayEntry\Next\IArray
EndIf
Until Not Index
; Wert lesen
ProcedureReturn *IArrayEntry\Value
EndProcedure
; Freigabe Procedure ist hoch-rekursiv, kann etwas länger dauern...
Procedure _IArray_FreeSub(*IData.IArray_Holder)
For i = 0 To 9
If *IData\Entry[i]\Next
_IArray_FreeSub(@*IData\Entry[i]\Next\IArray)
EndIf
Next
FreeMemory(*IData)
EndProcedure
; Array freigeben
Procedure IArray_Free(*IArray.IArray)
_IArray_FreeSub(*IArray)
EndProcedure
#SCNT = 10000000
#CNT = 20000000
IArray = New_IArray()
t = ElapsedMilliseconds()
For i = #SCNT To #CNT
IArray_Set(IArray, i, i*2)
Next
t1 = ElapsedMilliseconds()-t
t = ElapsedMilliseconds()
For i = #SCNT To #CNT
IArray_Get(IArray, i)
Next
t2 = ElapsedMilliseconds()-t
t = ElapsedMilliseconds()
IArray_Free(IArray)
t3 = ElapsedMilliseconds()-t
MessageRequester("test", "Gesamt: Einträge: " + Str(#CNT-#SCNT) + Chr(13) + "Schreiben & Erstellen: Zugriffe: " + StrF((#CNT-#SCNT)/t1*1000, 2) + "/Sek" + Chr(13) + "Lesen: Zugriffe: " + StrF((#CNT-#SCNT)/t2*1000, 2) + "/Sek" + Chr(13) + "Aufräumen: " + StrF(t3/1000, 2) + " sek")
