Autor |
Beitrag |
Bergmann89
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: Fr 09.06.17 21:47
Hallo Leute
ich habe ein 2D Array, dessen zweite Dimension mit jedem Schritt der ersten Dimension um das 4-fache wächst. Ich würde dieses 2D Array jetzt gern durch ein normales Array ersetzen und suche eine möglichst effiziente Variante den absoluten Index des Arrays auszurechnen, wenn ich das Level und den Relativen Index gegeben habe, bzw möchte ich Level und relativen Index ausrechnen wenn ich den absoluten Index gegeben habe. Zur Übersichtlichkeit hier eine kleine Tabelle:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| Level | Start Index | Relative Index | Global Index ------|-------------|------------------------|---------------------------------------- 0 | 0 | 0, 1, 2, 3 | 0, 1, 2, 3 1 | 4 | 0, 1, 2, 3, 4, 5, 6, 7 | 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, .... 2 | 20 | 0, 1, 2, 3, 4, 5, ... | 20, 21, 22, 23, 24, 25, 26, 27, ... 3 | 84 | 0, 1, 2, 3, 4, 5, ... | 84, 85, 86, 87, 88, 89, 90, 91, ... 4 | 340 | 0, 1, 2, 3, 4, 5, ... | 340, 341, 342, 343, 344, 345, 346, ... 5 | 1364 | ... | ... 6 | 5460 | ... | ... ... | ... | ... | ... |
Der Start Index wächst immer um die Länge des letzten Arrays an. Sprich für Level 5 ist der Start Index 0 + 4 + 16 + 64 + 256 + 1024 = 1364 oder anders ausgedrückt: 4^0 + 4^1 + 4^2 + 4^3 + 4^4 + 4^5 - 1 oder als Summe: (\sum_{i=1}^5 4^i)-1
Ich habe bereits einen Algorithmus, mit dem ich die gewünschten Informationen ermitteln kann, aber ich bin mir fast sicher, dass man die mit ein wenig Mathe auch direkt ausrechnen kann. So ist es zur Zeit gelöst:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| AbsIndex -> RelIndex + Level: Level = 0 RelIndex = AbsIndex c = 4 while (RelIndex >= c) RelIndex = RelIndex - c c = c shiftleft 2 // optimierte Version von *4 done
RelIndex + Level -> AbsIndex: c = 4 AbsIndex = 0 while (Level > 0) AbsIndex = AbsIndex or c // optimierte Version von +c, weil es kein Übertrag gibt Level = Level - 1 c = c shiftleft 2 // optimierte Version von *4 done AbsIndex = AbsIndex + RelIndex |
MfG & Thx Bergmann
_________________ Ich weiß nicht viel, lern aber dafür umso schneller^^
|
|
Frühlingsrolle
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: Fr 09.06.17 22:29
- Nachträglich durch die Entwickler-Ecke gelöscht -
|
|
cryptnex
Beiträge: 23
Erhaltene Danke: 5
|
Verfasst: Fr 09.06.17 22:50
Hi!
Sei R der relative Index und N das Level, dann könnte man den Absolut Index A auch so direkt berechnen:
A(R,N) := (\sum_{i=1}^\text{N} 4^i) + R = 4/3(4^\text{N} - 1) + R.
Beispiel, sei N = 3 und R = 4, dann folgt A = 88.
Die Umkehrung muss man sich dann noch einmal überlegen:
Angenommen R sei Null, dann ist
N(A) := \text{floor}{\ln(3\cdot A + 4)/(2\cdot \ln(2))} - 1
und der Relativindex ergibt sich dann aus
R(A,N(A)) := A - 4/3(4^\text{N(A)} - 1),
wenn Dir das hilft. Da musst Du nun schauen, ob das nun performanter ist oder nicht.
MfG
Für diesen Beitrag haben gedankt: Bergmann89
|
|
Bergmann89
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: Sa 10.06.17 07:29
@Frühlingsrolle: Genau das mach ich doch jetzt schon?! Ich denke mit einer einfachen Formel sind die Informationen schneller ausgerechnet, als mit der Schleife.
@cryptnex: Perfekt, Danke! Sowas hab ich gesucht. Performance muss ich jetzt mal messen. Wenn ich paar Werte hab meld ich mich nochma
_________________ Ich weiß nicht viel, lern aber dafür umso schneller^^
|
|
Bergmann89
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: So 11.06.17 14:56
So, ich hab's mal ausprobiert. Es gibt einen Teilerfolg
Quelltext 1: 2: 3: 4:
| Translate Index To Meta - Total: 1,10 s; Average: 0,022 us TranslateEx Index To Meta - Total: 3,33 s; Average: 0,067 us Translate Meta To Index - Total: 1,08 s; Average: 0,022 us TranslateEx Meta To Index - Total: 0,39 s; Average: 0,008 us |
TranslateEx ist die Implementierung mit den Formeln, Translate ist meine alte Implementierung. Meta ist die Kombination aus Level und relativem Index. Index ist der absolute Index.
Wie man sieht frisst das ln in der einen Implementierung haufen Zeit. Es ist sogar langsamer als meine ursprüngliche Version. Die Berechnung das absoluten Index ist dafür mehr als 50% schneller
Mal sehn, vlt find ich für das ln auch noch ne schnellere Lösung...
€: Ich hab nochmal ein wenig optimiert und ein paar LUTs eingebaut. Jetzt passts
Quelltext 1: 2: 3: 4:
| Translate Index To Meta - Total: 1,12 s; Average: 0,022 us TranslateEx Index To Meta - Total: 0,44 s; Average: 0,009 us Translate Meta To Index - Total: 1,08 s; Average: 0,022 us TranslateEx Meta To Index - Total: 0,38 s; Average: 0,008 us |
MfG Bergmann
_________________ Ich weiß nicht viel, lern aber dafür umso schneller^^
Für diesen Beitrag haben gedankt: cryptnex
|
|
Frühlingsrolle
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: So 11.06.17 20:52
- Nachträglich durch die Entwickler-Ecke gelöscht -
|
|
cryptnex
Beiträge: 23
Erhaltene Danke: 5
|
Verfasst: So 11.06.17 22:08
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 12.06.17 10:53
Hallo,
nur als kleine Bemerkung, wie man auf die Formel von cryptnex kommt.
Das ist die Zinseszinsformel.
q^0+q^1+q^2...+q^n = (q^(n+1)-1)/(q-1)| <= Polynomdivison
jetzt noch 1 == q^0 abziehen, weil der erste Index nicht 1 sondern 0 ist.
Quelltext 1: 2: 3: 4:
| ->sum=q^(n+1)-1)/(q-1) -1 sum =(q^(n+1)-1)-(q-1))/(q-1) | Hauptnenner sum =(q^(n+1)-q)/(q-1) | im Zähler ein q rausziehen sum =(q^n-1) * q/(q-1) | Formel von cryptnex |
Und die Umkehrung welches n bei sum =?
Quelltext 1: 2: 3: 4:
| sum =(q^n-1) * q/(q-1) | q^n freistellen (sum*(q-1)/q)+1 = q^n | logarithmieren ln((sum*(q-1)/q)+1)= n*ln(q)| / ln(q) n = ln( sum*(q-1)/q +1)/ln(q) |
Das Sum wäre hier A,q=4
n(A) = floor(ln(A*3/4+1)/ln(4))// ln(4) == ln(2^2) = 2*ln(2)
Test n(5460) = 6 , passt doch und eine -1 gespart
Gruß Horst
P.S
Es wäre dennoch schön, die optimierte Version zu sehen
Noch ein Edit.Es scheinen etwa 50 Mio Durchläufe bei den Zeitangaben zu sein.
Ich habe jetzt Hin- und Rückumwandlung in die Test-Schleife gepackt, wobei RelLevToAbsIdx viel zu schnell ist ( 0.16 s für 50 Mio ).
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41:
| {$IFDEF FPC} {$MODE DELPHI}{$ELSE}{$APPTYE CONSOLE}{$ENDIF} const q = 4; cLUT :array[0..15] of LongInt =(0,4,20,84,340,1364,5460,21844,87380,349524,1398100, 5592404,22369620,89478484,357913940,1431655764); type tErgRec = record erRel,erLev : LongInt; end;
function RelLevToAbsIdx(A:tErgRec):NativeInt; Begin result := cLUT[A.erlev]+A.erRel; end;
function AbsIdxToRelLev(AbsIdx :NativeInt):tErgRec; var lev:nativeInt; Begin lev:= 1; while cLUT[lev]<AbsIdx do inc(lev); dec(lev); result.erRel:= AbsIdx-cLUT[lev]; result.erLev := lev; end; const runden = 50*1000*1000; var i : NativeInt; ErgRec:tErgRec; Begin For i := 1 to runden do IF i <> RelLevToAbsIdx(AbsIdxToRelLev(i)) then writeln('aergerlich'); ErgRec:= AbsIdxToRelLev(runden); writeln(runden:10,' -> Level ',ErgRec.erlev,' , rel. Index ',ErgRec.erRel); end. |
Mit freepascal für Linux 64-Bit auf Haswell i3-3,5 Ghz
Quelltext 1: 2: 3: 4: 5:
| real 0m0.609s user 0m0.607s sys 0m0.000s
AbsIdxToRelLev braucht allein schon 0.439 Sekunden |
Für diesen Beitrag haben gedankt: cryptnex
|
|
Bergmann89
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: Di 13.06.17 17:01
Hallo,
so hab ich's gemacht:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58:
| type TLevel = 0..15; TQuadtreeIndex; TMeta = packed record Level: TLevel; RelativeIndex: Cardinal end;
const LEVEL_START_INDEX: array[TLevel] of Cardinal = ( $00000000, $00000004, $00000014, $00000054, $00000154, $00000554, $00001554, $00005554, $00015554, $00055554, $00155554, $00555554, $01555554, $05555554, $15555554, $FFFFFFFF );
function Translate(aIndex: TQuadtreeIndex): TMeta; begin if (aIndex >= LEVEL_START_INDEX[12]) then begin if (aIndex >= LEVEL_START_INDEX[15]) then result.Level := 15 else if (aIndex >= LEVEL_START_INDEX[14]) then result.Level := 14 else if (aIndex >= LEVEL_START_INDEX[13]) then result.Level := 13 else result.Level := 12; end else if (aIndex >= LEVEL_START_INDEX[8]) then begin if (aIndex >= LEVEL_START_INDEX[11]) then result.Level := 11 else if (aIndex >= LEVEL_START_INDEX[10]) then result.Level := 10 else if (aIndex >= LEVEL_START_INDEX[ 9]) then result.Level := 9 else result.Level := 8; end else if (aIndex >= LEVEL_START_INDEX[4]) then begin if (aIndex >= LEVEL_START_INDEX[ 7]) then result.Level := 7 else if (aIndex >= LEVEL_START_INDEX[ 6]) then result.Level := 6 else if (aIndex >= LEVEL_START_INDEX[ 5]) then result.Level := 5 else result.Level := 4; end else if (aIndex >= LEVEL_START_INDEX[0]) then begin if (aIndex >= LEVEL_START_INDEX[ 3]) then result.Level := 3 else if (aIndex >= LEVEL_START_INDEX[ 2]) then result.Level := 2 else if (aIndex >= LEVEL_START_INDEX[ 1]) then result.Level := 1 else result.Level := 0; end; result.RelativeIndex := aIndex - LEVEL_START_INDEX[result.Level]; end;
function Translate(aLevel: TLevel; const aRelIndex: Cardinal): TQuadtreeIndex; begin result := LEVEL_START_INDEX[aLevel] + aRelIndex; end; |
MfG Bergmann
_________________ Ich weiß nicht viel, lern aber dafür umso schneller^^
Für diesen Beitrag haben gedankt: cryptnex, Horst_H
|
|
|