Zugriffsgeschwindigkeit auf mehrdimensionale Arrays

[jfheins]

Du könntest einfach mal versuchen single statt double zu benutzen sofern dir dessen Genauigkeit reicht - dann ist das ganze nurnoch halb so groß ;)

Ansonsten kann ich nur nochmal fragen: Wieviel Arbeitsspeicher hat der Rechner denn?

Oder ne ganz verrückte idee: Du könntest das ganze Zeug auf die GPU auslagern - gerade wenn die Probleme stark parallelisierbar sind, sind moderne GPUs um eine vielfaches schneller als x86-CPUs ;)

[xcs]

Ich hab 4 GB RAM und Windows XP (also 32 Bit).
Würde es was bringen, eine 64Bit-Version zu benutzen?

[xcs]

Aber um noch einmal auf das ursprüngliche Problem zurückzukommen:

Weiß jemand, wie genau bei der Programmausführung der Array-Zugriff funktionert (Pointer / Adressierung etc.)

Das Phänomen tritt schon bei sehr kleinen Arraygrößen auf:

Delphi-Quellcode:

implementation

{$R *.dfm}

var
  array1 : array[0..50,  0..4,  0..4, 0..50,  0..4,  0..4] of double;
  array2 : array[0..50, 0..14, 0..14, 0..50, 0..14, 0..14] of double;

procedure TForm1.Button1Click(Sender: TObject);
var
  i,j,k,l,m,n : integer;
  start1, ende1, start2, ende2 : int64;
  performance_factor : double;
begin

  queryperformancecounter(start1);
  for i := 0 to 50 do for j := 0 to 2 do for k := 0 to 2 do
  for l := 0 to 50 do for m := 0 to 2 do for n := 0 to 2 do
  begin
    array1[i,j,k,l,m,n] := array1[i,j,k,l,m,n] + i*j*k*l*m*n;
  end;
  queryperformancecounter(ende1);

  queryperformancecounter(start2);
  for i := 0 to 50 do for j := 0 to 2 do for k := 0 to 2 do
  for l := 0 to 50 do for m := 0 to 2 do for n := 0 to 2 do
  begin
    array2[i,j,k,l,m,n] := array2[i,j,k,l,m,n] + i*j*k*l*m*n;
  end;
  queryperformancecounter(ende2);

  performance_factor := (ende2-start2)/(ende1-start1);

  showMessage(floattostr(performance_factor));
end;

Probiert es mal aus. Schon hier ist der Unterschied von einem Faktor 2-5 zu erkennen (das kann entscheiden, ob ich 1 Tag oder 5 Tage warten muss, bis mein Rechner fertig ist). Bei größeren Arrays bis zu Faktor 10...

[jfheins]

Normalerweise geht das ungefähr so:

array[12] wird zu (@array + 12)^

und array[1, 4] wird zu (@array + 1 * <länge 2.Dimension> + 4)^

Oder so ähnlich. Auf jeden Fall sollte der Zugriff auf ein beliebiges Element in O(1) erfolgen also in konstanter Zeit (= unabhängig von der Menge der Daten)

[Medium]

Zitat:

Zitat von xcs

Das Phänomen tritt schon bei sehr kleinen Arraygrößen auf:

So "sehr klein" sind die gar nicht.
array1: 13.005.000 Bytes (~12,4 MB)
array2: 1.053.405.000 Bytes (~0,89 GB)

In deiner 6(!)-fach Schleife kommst du letztlich auf immerhin 210.681 Durchläufe. Das ist zunächst mal nicht so übermäßig viel, aber wenn dann auch noch im Speicher geswapped werden muss (was bei ca. 1GB auch passieren kann wenn man 4GB RAM hat) kann das durchaus mal etwas dauern.

Über wie viele Sekunden für je eine solche Schleife reden wir hier eigentlich? Evtl. lässt sich daraus ja zumindest ableiten ob da grundsätzlich nicht etwas schief läuft.


Edit: Und ich habe noch immer nicht verstanden was du vor hast. Die meisten sind hier vermutlich maximal Hobbyphysiker (unterstelle ich einfach mal ganz frech), und können mit den Fachtermini bestenfalls erahnen was da abgeht. Zumindest geht's mir so :?. Auch ging nicht so wirklich daraus hervor, was du am Ende nun haben/machen willst. Das ist hier u.U. wichtig, da man je nach Zweck noch immer ganz anders optimieren kann.

[Blup]

Um auf die ursprüngliche Fragestellung zurück zu kommen, hier mein Test:

Delphi-Quellcode:

const
 x=50; y=14; z=14; // Variante 1
// x=1274; y=2; z=2; // Variante 2
var
 mein_Array : array[0..x,0..y,0..z,0..x,0..y,0..z] of double;

procedure TForm1.Button1Click(Sender: TObject);
var
  i, j, k, l, m, n, idx: integer;
  x1, x2: LongWord;
begin
  Button1.Caption := '';
  x1 := GetTickCount;
  for i := 0 to x do
    for j := 0 to y do
      for k := 0 to z do
        for l := 0 to x do
          for m := 0 to y do
            for n := 0 to z do
              mein_Array[i,j,k,l,m,n] := i * j * k * l * m * n;
  x2 := GetTickCount;
  Button1.Caption := IntToStr(x2 - x1);
end;

Vor dem Test einer Variante habe ich Windows jeweils neu gestartet.
Die Funktion wurde nach jedem Programmstart 8 mal wiederholt aufgerufen.

Code:

Durchlauf          1  |   2  |   3  |   4  |   5  |   6  |   7  |   8
-----------------------------------------------------------------------
Variante 1
1.Programmstart  15,0 | 82,3 | 17,8 |  2,1 |  1,5 |  1,7 |  1,5 |  1,3
2.Programmstart  12,5 | 53,5 |  4,6 |  1,7 |  1,3 |  1,3 |  1,3 |  1,2

Variante 2
1.Programmstart  15,7 | 85,3 | 24,0 |  2,5 |  1,8 |  1,7 |  1,7 |  1,7
2.Programmstart  11,1 | 37,6 |  3,9 |  1,9 |  1,7 |  1,6 |  1,7 |  1,7

Beide Varianten von x,y,z sind in etwa gleich schnell.
Entscheident ist hier das Auslagern des Speichers durch Windows.

In der Variante 2 müssen allerdings deutlich mehr innere Schleifen initialisiert werden.
Das könnte die geringen Zeitabweichungen erklären.

[himitsu]

jupp, vom Zugriff auf die Elemente sollte bei der For-Schleifchen-Kombination eh alle Elemente in der selben Reinfolge und auch noch sequentiell erfolgen ... bei beiden Varianten.

für dieses hier

Delphi-Quellcode:

for i := 0 to x do
  for j := 0 to y do
    for k := 0 to z do
      for l := 0 to x do
        for m := 0 to y do
          for n := 0 to z do
            mein_Array[i,j,k,l,m,n] := i * j * k * l * m * n;

und falls ich mich jetzt nicht vertan hab, 'ne Variante mit nur einer Schleife

Delphi-Quellcode:

type PDoubleArray = array[0..0] of Double;

for f := 0 to (x+1) * (y+1) * (z+1) * (x+1) * (y+1) * (z+1) do
begin

//g := f;
//i := g mod (z+1);  g := g div (z+1);
//j := g mod (y+1);  g := g div (y+1);
//k := g mod (x+1);  g := g div (x+1);
//l := g mod (z+1);  g := g div (z+1);
//m := g mod (y+1);  g := g div (y+1);
//n := g mod (x+1);  g := g div (x+1);

  i := f mod (z+1);  g := f div (z+1);
  j := g mod (y+1);  g := g div (y+1);
  k := g mod (x+1);  g := g div (x+1);
  l := g mod (z+1);  g := g div (z+1);
  m := g mod (y+1);  n := g div (y+1);

  PDoubleArray(@mein_Array)[f] := i * j * k * l * m * n;
end;

[Blup]

Wenn die Membran eine sehr dünne Ebene ist und das restliche Medium weitgehend homogen, dürfte epsilon_r ja nur davon abhängen, ob die Membran zwischen den beiden Punkten liegt?
Diesen Term könnte man dann relativ leicht bestimmen:
(4*PI*epsilon_0*epsilon_r)

Der andere Term beschreibt nur den Abstand zwischen dem Punkt [i,j,k] und dem Punkt [l,m,n]:
sqrt(sqr(pos_x[i,j,k]-pos_x[l,m,n]) + sqr(pos_y[i,j,k]-pos_y[l,m,n]) + sqr(pos_z[i,j,k]-pos_z[l,m,n])

Um diese Berechnung zu sparen, würde ich(wie schon gesagt) eine extra Array erstellen, das genau diesen relativen Abstand enthält.
Abstand[i - l, j - m, k - n]