Autor Beitrag
Bergmann89
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
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)
BeitragVerfasst: 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:
ausblenden 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:
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1734
Erhaltene Danke: 311

[Win NT] 5.1 x86 6.1 x64
[Delphi] 7 PE, 2006, 10.1 Starter, Lazarus - [C#] VS Exp 2012 - [Android API 15] VS Com 2015, Eclipse, AIDE - [C++] Builder 10.1
BeitragVerfasst: Fr 09.06.17 21:29 
Guten Abend Bergmann89,

warum keine for..to Schleife, die einen temporären Wert mit jeden Durchlauf um das 4fache vergrößert?

_________________
„Politicians are put there to give you the idea that you have freedom of choice. You don’t. You have no choice. You have owners. They own you. They own everything." (George Denis Patrick Carlin)
cryptnex
ontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 23
Erhaltene Danke: 5



BeitragVerfasst: Fr 09.06.17 21: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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
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)
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
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)
BeitragVerfasst: So 11.06.17 13:56 
So, ich hab's mal ausprobiert. Es gibt einen Teilerfolg :)

ausblenden 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 :)
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1734
Erhaltene Danke: 311

[Win NT] 5.1 x86 6.1 x64
[Delphi] 7 PE, 2006, 10.1 Starter, Lazarus - [C#] VS Exp 2012 - [Android API 15] VS Com 2015, Eclipse, AIDE - [C++] Builder 10.1
BeitragVerfasst: So 11.06.17 19:52 
Wäre gut zu wissen, wie du das geschafft. Eine kurze Erklärung mit/ohne Codefragment/e würde mir gefallen. ;)

_________________
„Politicians are put there to give you the idea that you have freedom of choice. You don’t. You have no choice. You have owners. They own you. They own everything." (George Denis Patrick Carlin)
cryptnex
ontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 23
Erhaltene Danke: 5



BeitragVerfasst: So 11.06.17 21:08 
user profile iconBergmann89 hat folgendes geschrieben Zum zitierten Posting springen:
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: :beer:
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1603
Erhaltene Danke: 222

WIN7,PuppyLinux
FreePascal,Lazarus,TurboDelphi
BeitragVerfasst: Mo 12.06.17 09:53 
Hallo,

nur als kleine Bemerkung, wie man auf die Formel von user profile iconcryptnex 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.
ausblenden 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 =?
ausblenden 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 ).
ausblenden volle Höhe 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..15of 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
ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
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)
BeitragVerfasst: Di 13.06.17 16:01 
Hallo,

so hab ich's gemacht:
ausblenden volle Höhe 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^^

Für diesen Beitrag haben gedankt: cryptnex, Horst_H