Matrix spiegelnd füllen

stimpleton

Grob gesagt:
Der Prozessor holt sich immer ein paar Befehler im Voraus.
Bei einem Sprungbefehl (hier: if) teilen sich die Wege und er verfolgt den Pfad, der ihm am wahrscheinlichsten vorkommt.
Ist dieser Tip falsch, so muß er auf den anderen umschwenken und das dauert dann.

Evtl. bist Du sogar schneller, wenn Du die Diagonalwerte doppelt schreibst.
Das erspart die Sprungvorhersage. Das geht aber auch sicher anders besser...

Ne das hab ich schon probiert. Ohne die if Abfrage ist es immernoch lahm.
Liegts daran, dass ich die Werte mit ner for Schleife übergebe?

Wie könnte es denn anders gehen?
get(2,5) muss einfach das gleiche ergeben wie get(5,2)

camper

da es hier um des 'befüllen' geht, gehe ich mal von einem regulären zugriffsmuster (linear) aus. in diesem falle spiel die sprungvorhersage keine rolle. für große N wird allerdings array[y*N+x] weit auseinanderliegende adressen betreffen, und das ist ein problem, wenn der L1 (und ggf. L2) cache nicht groß genug ist, um das array zu enthalten. ein bisschen mehr müsste man hier schon über die aufrufende funktion wissen.

Hum, naja
Habs einfach mal getestet mit N = 1024 und 4096 und short als Typ.
Gibt ja schon einige MB, gut möglich das mein kleiner alter Prozi nicht genug Cash hat, aber wer hat das schon
Habe in 2 verschachtelten for Schleifen von 0 bis N-1 alle Werte zufällig befüllt. Das entspricht nicht dem Original Fall, aber ich wollt halt mal testen.

Egal, ich teste einfach, welche Zahl groesser ist und fülle dann nur ein Feld.
Danke trotzdem

langsam ist so furchtbar relativ, was genau ist bei dir langsam (bitte in Zahlen mit Einheiten)?

finix

Ach so... "wenn ich den zweiten Zugriff". Hab ich komplett dran vorbei gelesen, dachte du meinst den else-Zweig.

Vielleicht wär

void set( int x, int y, int val )
{
  if (x < y) {
    array[((x*(x+1))/2)+y] = val;
  } else {
    array[((y*(y+1))/2)+x] = val;
  }
}

was für dich?

stimpleton

Du testest die Release-Version nehme ich an? (Könnte ja sein...)

Morgen

Ja, teste die Release Version.

Ja, langsam ist relativ, und zwar so:

for( int i = 0; i < N; ++i )
{
    for( int j = 0; j < N; ++j )
    {
        set( i, j, Zufallszahl );
    }
}

Mit

void set( int x, int y, int val )
{
    array[y*N+x] = val;
}

ist es relativ langsamer als mit

void set( int x, int y, int val )
{
    array[x*N+y] = val;
}

und zwar mehr als 2x (keine Einheit :p)

finix, zu dem Schluss bin ich dann auch gekommen.
Aber deine Berechnung des Array Index kapier ich nicht
Machs jetzt so:

for( int i = 0; i < N; ++i )
{
    for( int j = 0; j <= i; ++j )
    {
        set( i, j, Zufallszahl );
    }
}

void set( int x, int y, int val )
{
    array[x*N+y] = val;
}
int get( int x, int y )
{
    if( x <= y )
        return array[x*N+y];
    else
        return array[y*N+x];
}

Der Rest der Matrix liegt brach, aber ich glaub ist einfacher so, als eine halbe zu implementieren.

Danke euch allen
und tschüss

finix

Eski Moe schrieb:

finix, zu dem Schluss bin ich dann auch gekommen.
Aber deine Berechnung des Array Index kapier ich nicht

Du kannst deine Spiegelmatrix einfach mit Hilfe einer Dreiecksmatrix implementieren.

Statt

{ v11, v12, v13,
  v21, v22, v23,
  v31, v32, v33 }

speicherst du nur

{ v11,
  v21, v22,
  v31, v32, v33 }