Entwickler-Ecke :: Thema anzeigen - 2D Array Index ausrechnen

Bergmann89 - Fr 09.06.17 21:47
Titel: 2D Array Index ausrechnen

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:

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:

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

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

Horst_H - Mo 12.06.17 10: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.

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

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

Quelltext

1:
2:
3:
4:
5:

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

AbsIdxToRelLev braucht allein schon 0.439 Sekunden

Bergmann89 - Di 13.06.17 17:01

Hallo,

so hab ich's gemacht:

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

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!