2D Array Index ausrechnen

Bergmann89 · Verfasst: Fr 09.06.17 20:47

Hallo Leute :wave:

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:

markieren

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 $0 + 4 + 16 + 64 + 256 + 1024 = 1364$ oder anders ausgedrückt: 4^0 + 4^1 + 4^2 + 4^3 + 4^4 + 4^5 - 1 $4^0 + 4^1 + 4^2 + 4^3 + 4^4 + 4^5 - 1$ oder als Summe: (\sum_{i=1}^5 4^i)-1 $(\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:

markieren

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^^

Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

cryptnex · Beiträge: 23 Erhaltene Danke: 5

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 $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

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

Bergmann89 · Verfasst: Sa 10.06.17 06:29

@Frühlingsrolle: Genau das mach ich doch jetzt schon?! :gruebel:

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 · Verfasst: So 11.06.17 13:56

So, ich hab's mal ausprobiert. Es gibt einen Teilerfolg

markieren

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

markieren

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^^

Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

cryptnex · Beiträge: 23 Erhaltene Danke: 5

Bergmann89 hat folgendes geschrieben :

Die Berechnung das absoluten Index ist dafür mehr als 50% schneller

€: Ich hab nochmal ein wenig optimiert und ein paar LUTs eingebaut. Jetzt passts

Freut mich! :zustimm:

Horst_H · Verfasst: Mo 12.06.17 09:53

Hallo,

nur als kleine Bemerkung, wie man auf die Formel von user profile icon

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.

markieren

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 =?

markieren

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 ).

markieren

Delphi-Quelltext

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;
  //Startindices der Level
  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
  //InitLUTPowLevel;
  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

markieren

Quelltext

1:
2:
3:
4:
5:

real  0m0.609s
user  0m0.607s
sys  0m0.000s

AbsIdxToRelLev braucht allein schon 0.439 Sekunden

Bergmann89 · Verfasst: Di 13.06.17 16:01

Hallo,

so hab ich's gemacht:

markieren

Delphi-Quelltext

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 = (
    {  0 } $00000000,
    {  1 } $00000004,
    {  2 } $00000014,
    {  3 } $00000054,
    {  4 } $00000154,
    {  5 } $00000554,
    {  6 } $00001554,
    {  7 } $00005554,
    {  8 } $00015554,
    {  9 } $00055554,
    { 10 } $00155554,
    { 11 } $00555554,
    { 12 } $01555554,
    { 13 } $05555554,
    { 14 } $15555554,
    { 15 } $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^^

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme