array befüllen

hi,

habe fragen zu folgendem codestück:

int n = 5120;
int* arr = new int[n*n];
for( int i = 0; i < n; i++ )
{
    for( int j = 0; j < n; j++ )
    {
        if( i == j )
        {
            arr[i*n + j] = 0;
        }
        else
        {
            arr[i*n + j] = 42;   // Beispielwert
        }
    }
}

erstens braucht es genau 100MB speicher, was aber stimmen sollte, habs ausgerechnet. kann ich da was sparen? die eingesetzten werte sind alle unter 1000.
zweitens dauert es ganz schön lange, 3-4 sec. grob geschätzt. kann ich das irgendwie beschleunigen?

für tipps und tricks stehts dankbar
mfg
yuri

Javaner

Speicher: Benutze unsigned short
Laufzeit: Anstatt mehr als 26 Millionen mal die Abfrage
auf i==j zu durchlaufen, fülle erst alle Elemente mit deinem Beispielwert
und gehe dann eine separate Schleife (5120-mal) durch, die die Diagonale füllt.

danke,

also etwa so?

int n = 5120;
int nSquare = n*n;
unsigned short* arr = new unsigned short[nSquare];
for( int i = 0; i < nSquare; i++ )
{
    arr[i] = 42;   // Beispielwert
}
for( int i = 0; i < n; i++ )
{
    arr[i*n + i] = 0;
}

hab den compiler grad nicht zur hand, konnte es also noch nicht testen.

btw: gibt es für arrays keine möglichkeit, sie mit standardwerten zu initialisieren, wie das bei stl vector möglich ist?

mfg
yuri

Javaner

yuri schrieb:

also etwa so?
...

Genau!

yuri schrieb:

gibt es für arrays keine möglichkeit, sie mit standardwerten zu initialisieren

Doch! Dafür gibt es die Funktion setmem(...)

LordJaxom

memset, aber macht nix

cool danke,

bin dann mal gespannt, obs so wie oben jetzt schneller geht.

setmem() wird intern wohl auch nen for loop haben oder?

mfg
yuri

volkard

yuri schrieb:

for( int i = 0; i < n; i++ )
{
    arr[i*n + i] = 0;
}

int step=n+1;
for( int i = 0; i < square; i+=step )
{
    arr[i] = 0;
}

Javaner

Es hat eine for-loop allerdings (mit ziemlicher Sicherheit) ist
es auf Assembler-Ebene geschrieben und bis zum geht nicht mehr
optimiert. (Z.B. füllen möglichst vieler Register mit deinem Wert
und direktes Schreiben dieser Registerinhalte direkt in den Speicher, ...)

Simon2

yuri schrieb:

cool danke,

bin dann mal gespannt, obs so wie oben jetzt schneller geht.

setmem() wird intern wohl auch nen for loop haben oder?

mfg
yuri

gute memset()-implementierungen (C-Header <string.h> ) nutzen direkt Möglichkeiten des Systems und sind rasant schnell.

Gruß,

Simon2.

camper

yuri schrieb:

btw: gibt es für arrays keine möglichkeit, sie mit standardwerten zu initialisieren, wie das bei stl vector möglich ist?

per new[] ist nur defaultinitialisierung ist möglich (bei PODs mit klammern hinter dem []-ausdruck, sonst implizit). auch std::vector u.a. benutzen zur initialisierung eine schleife. der trick ist hier, die defaultinitialisierung auch für nicht-PODs zu vermeiden und operator new direkt aufzurufen. die initialisierung erfolgt dann per placement new (und da jedes element einzeln initialisiert wird, kann damit prinzipiell auch jeder beliebe konstruktor benutzt werden).
memset ist im allgemeinen keine gute wahl und sollte nur in low-level routinen, die direkt mit char-arrays arbeiten, genutzt werden.

volkard schrieb:

...

super dankeschön

@camper: wie würdest du es lösen ohne memset? es ist ziemlig low-levlig.

mfg
yuri

volkard

ich fürchte, das nochmalige durchrutschen sollte vermieden werden (wegen ram-langsamheit), indem es zu sowas wird:

array[0]=0;
for(diagpos=n+1;diagpos<square;diagpos+=n+1){
   for(int i=diagpos-n;i<diagpos;++i)
      array[i]=42;
   array[diagpos]=0;
}

Javaner

volkard schrieb:

[cpp]...

Also das mag ja effizient sein (und hoffentlich auch effektiv ),
wäre mir persönlich allerdings zu unverständlich.

volkard schrieb:

[cpp]...

Volkard, du bist ein genie. danke.

Javaner schrieb:

wäre mir persönlich allerdings zu unverständlich.

nö, wieso?

also nochmal wegen der standardwerte. ich möcht das array mit maximalwerten füllen (65536 für short) und die diagonalen mit 0, um dann nur die werte zu ändern, die relevant sind. (es geht um eine matrix zum auslesen der distanz, maxwert == unerreichbar)
ist memset hier wirklich nicht zu empfehlen, oder kommt obige version von Volkard mit optimierung (/Ox) aufs gleiche raus?

mfg
yuri

Javaner

Probier's aus!

Ich würde sagen, daß memset + eine Schleife über nur 5200 Indizes
schneller ist.

ok,

wie gesagt, hab meinen compiler grad nicht dabei
werd's aber heut abend ausprobieren, und dann berichten.

hab grad mal geggogelt, wie memset aussehn muss. das geht aber nicht nur mit char strings oder? weil sonst bringt mir das ja nichts.

mfg
yuri

Simon2

Hi,

char ist (leider) in C auch das Pendant für "byte" und taucht deswegen oft auch da auf, wo "roher Speicher" gemeint ist.

Das Problem dürfte wohl eher sein, dass als Parameter "nur 1 Byte" zu Verfügung steht. In Deinem konkreten Fall (Maximalwert) dürfte das aber gehen:
(echte C++er besser weggucken)

unsigned short* arr = new unsigned short[n*n];
memset(arr, 0xFF, n*n*sizeof(unsigned short));

Gruß,

Simon2.

sorry, ich hab den ursprünglichen codeteil falsch im kopf gehabt.
die werte sollten mit einem zufallswert befüllt werden, aber jeweils an zwei stellen [i][j] und [j][i], also quasi gespiegelt an der diagonale, die auf null steht. (logisch: a ist von b gleichweit weg wie b von a)
das dauert 8 sekunden, mit einer zuweisung aber nur 1 sekunde. wie kommt das?
den code hab ich grad getestet:

int n = 5120;
int* arr = new int[n*n];
for( int i = 0; i < n; i++ )
{
    for( int j = 0; j < n; j++ )
    {
        if( i == j )
        {
            arr[i*n + j] = 0;
        }
        else
        {
            arr[i*n + j] = 42;   // Beispielwert
            arr[j*n + i] = 42;   // Beispielwert
        }
    }
}
delete[] arr

hab jetzt noch gar nicht eure vorschläge ausprobiert, weil mich das grad sehr wundert.

mfg
yuri

hmnömjöm..egal

resultate (durchschnitt aus 10 messungen in einem loop):

1. memset + for über 5120 von Simon2
473ms

2. for verschachtelt 2. vorschlag von volkard
484ms

3. for nacheinander 1. vorschlag von volkard
500ms

4. if else meine ursprüngliche lösung
513ms

es bringt tatsächlich was
ich glaub das memset lass ich weg, 11ms ist solch übler c-code nicht wert :p

danke trotzdem für eure ideen, ich hab wieder mal gelernt abstrakter vorzugehn

mfg
yuri

obige Reihenfolge ohne Störungen
1. 340ms
2. 340ms
3. 340ms
4. 357ms
..und wenns jemand interessiert:
5. 370ms
6. 370ms

int n = 5120;
		int nSquare = n*n;
		//5.
		std::vector< int > arr( nSquare, 42 );
		int diagStep = n + 1;
		for( int i = 0; i < nSquare; i+=diagStep )
		{
			arr[i] = 0;
		}

int n = 5120;
		int nSquare = n*n;
		//6.
		std::vector< int > arr( nSquare, 42 );
		int diagStep = n + 1;
		for( std::vector< int >::iterator i = arr.begin(); i < arr.end()-1; 
			      i+=diagStep )
		{
			(*i) = 0;
		}

die stl lebe hoch

so und jetzt lass ich euch

Simon2

yuri schrieb:

...
ich glaub das memset lass ich weg, 11ms ist solch übler c-code nicht wert :p ...

Gute Entscheidung !
(auch wenn ich beruflich viel mit C mache und seine Stärken durchaus zu schätzen weiß)

yuri schrieb:

obige Reihenfolge ohne Störungen
...
die stl lebe hoch
...

"... Dreiiiiiimal hooooch !"

Danke für die Messungen. Sind sehr interessant.
(Welche "Störungen" hattest Du denn ? )

Gruß,

Simon2.