Brauche Optimierungshilfe :)

[hustbaer]

Also das ist ein Fall den du noch weit besser optimieren kannst. Hab erst heut Abend Zeit, aber wenn ich nicht vergesse poste ich dir nen schönes Beispiel...

Eine Frage vorweg: gibts ne Grenze für x_dim wo du in z.B. 90% aller Fälle drunter liegen wirst?

[Mati]

Hallo,
danke für eure Hilfe...bzw. wan noch kommt

das mit dem resize(0) und reserve speicher bringt leider fast nichts...macht sich um ca. 0.05 - 0.1 % bemerkbar...

Mit dem 90% ...leider nicht - x_dim ist natürlich die x-dimension der matrix und bleibt es auch - an der ändert sich nichts im gegensatz zum y_dim....

[hustbaer]

Naja das is mir schon klar. Ich meine bei deinen Matritzen, wenn da viele z.B. kleiner 100 Elemente breit sind, dann könnte man den Fall noch optimieren indem man da auf ne dynamische Speicheranforderung verzichtet...

[Mati]

hallo,

Hmm...von breite...
ja ...ich glaube es kommt durchaus vor dass die matrizen extrem groß in y - richtugn (also sehr viele Zeilen hat) aber dafür nur sehr klein (< 100) in x-richtung(also wenige spalten hat) vor.
Das kann sehr gut sein....würde sogar sagenn dass die dimensionen in x bei <50 liegen....
d.h es gibt matrizen die z.B dimension haben: 2000 x 5 (zeilen x spalten)

ABER: das muss nicht immer so sein ...würde jetzt pauschal sagen bei 90 % der fälle wie du es eben gemeint hast....

Das einzige was markant ist, ist dass sie dünnbesetzt sind. D.h. von denen ist höchsten 3% - 5% mit werten ungleich Null gefüllt. Aber
eben deshalb das ganze

[hustbaer]

Ich glaub ich hab mich da sowieso vertan weil du ja "zeilen" und "spalten" vertauscht hast. Das was bei mir jetzt "columns" ist muss klein sein, aber das ist bei dir ja y... von daher doof wenn das so gross wird . Aber egal.

----

Soda. Hab mir mal gescheit das Hirn verbogen, und das is dabei rausgekommen:
(Vorweg: ich hab "rows" und "columns" verwendet, und bei mir liegen die "rows" continuierlich in der Matrix, dafür entferne ich halt columns . Musst halt search & replace machen wenn dir die Namen nicht gefallen - hätte mir sonst zu sehr das Hirn verdreht.)

void MarkZeroColumns(double const* matrix, size_t rows, size_t columns, char* flags)
{
	if(!(rows && columns))
		return;

	assert(matrix && flags);

	double const* src = matrix;

	// process first row
	size_t c = 0;
	size_t n = columns;
	while(n--)
	{
		flags[c] = (*src == 0);
		++c; ++src;
	}

	// process remaining rows
	n = (rows - 1) * columns;
	c = 0;
	while(n--)
	{
		flags[c] &= (*src == 0);
		++c; ++src;
		if(c == columns)
			c = 0;
	}
}

// returns the new column count
size_t NukeColumns(double* matrix, size_t rows, size_t columns, char const* flags)
{
	if(!(rows && columns))
		return 0;

	assert(matrix && flags);

	int* dynamicBuffer = 0; // use guard instead if 'double' is changed to a UDT (operator = could throw)
	int* advance;

	// alloc temp space
	if(columns <= 1000)
		advance = static_cast<int*>(alloca((columns + 1) * sizeof(int)));
	else
	{
		dynamicBuffer = new int[columns + 1];
		advance = dynamicBuffer;
	}

	memset(advance, 0, (columns + 1) * sizeof(int));

	// make column advances
	size_t c = 0;
	size_t keep = 0; // nr. of columns to keep
	while(c < columns)
	{
		advance[keep]++;

		if(!flags[c])
		{
			// keep
			++keep;
		}
		++c;
	}

	if(keep && (keep != columns))
	{
		// make start ptr and fix advance
		double const* src = matrix + advance[0] - 1;
		advance[keep] += advance[0];
		++advance;

		// process all rows
		double* dest = matrix;
		size_t n = rows * keep;
		c = 0;
		while(n--)
		{
			*dest = *src;
			++dest;
			src += advance[c];
			++c;
			if(c == keep)
				c = 0;
		}
	}

	delete [] dynamicBuffer;

	return keep;
}

// returns the new column count
size_t NukeZeroColumnsAndOne(double* matrix, size_t rows, size_t columns, long andOne)
{
	if(!(rows && columns))
		return 0;

	assert(matrix);

	char* dynamicBuffer = 0;
	char* flags;

	// alloc temp space
	if(columns <= 1000)
		flags = static_cast<char*>(alloca(columns));
	else
	{
		dynamicBuffer = new char[columns];
		flags = dynamicBuffer;
	}

	size_t remainingColumns;

	try
	{
		MarkZeroColumns(matrix, rows, columns, flags);
		if((andOne >= 0) && (andOne < columns))
			flags[andOne] = 1;
		remainingColumns = NukeColumns(matrix, rows, columns, flags);
	}
	catch(...)
	{
		// TODO: should use guard instead, but I'm to lazy at the moment...
		delete [] dynamicBuffer;
		throw;
	}

	delete [] dynamicBuffer;
	return remainingColumns;
}

int main(int argc, char** argv)
{
	std::vector<double> m;
	size_t columns = 10;
	size_t rows = 10;

	srand(time(0));

	for(size_t r = 0; r < rows; r++)
	{
		for(size_t c = 0; c < columns; c++)
		{
			if((rand() % 100) < 93)
				m.push_back(0);
			else
				m.push_back((rand() * 10.0) / RAND_MAX);
		}
	}

	for(size_t r = 0; r < rows; r++)
	{
		for(size_t c = 0; c < columns; c++)
		{
			printf("%.2f", m[r * columns + c]);
			if((c + 1) < columns)
				printf(" | ");
		}
		printf("\n");
	}
	printf("\n");
	printf("\n");

	columns = NukeZeroColumnsAndOne(&m[0], rows, columns, -1);

	for(size_t r = 0; r < rows; r++)
	{
		for(size_t c = 0; c < columns; c++)
		{
			printf("%.2f", m[r * columns + c]);
			if((c + 1) < columns)
				printf(" | ");
		}
		printf("\n");
	}

	getch();
}

Die alloca Aufrufe sind bloss damit net wegen jedem kleinen dreck "new" verwendet werden muss, weil new is laaaangsam. Kannste auch rausnehmen, dann würde ich die beiden temp arrays aber gleich von nem std::vector holen, dann ist das auch gleich automatisch exception-safe. Also so quasi:

std::vector<int> buffer(columns + 1);
	int* advance = &buffer[0];
	// ...
	// und halt kein delete [] am Schluss, sollte klar sein :)

Wenn die Matritzen meist eher gross sind kannst du die alloca Optimierung rauswerfen, die greift dann sowieso kaum. Und wieviel stack space du opfern willst musst du selbst entscheiden, ich denke aber max. 1000 Elemente sollte ne vernünftige Grenze sein.

Wenn du's verwenden willst bitte teste es noch auf Herz und Nieren, ich bin grad erst fertig geworden und hab nur schnell so drübergeguckt - sieht gut aus, aber mehr als 5 Testläufe hab ich nicht gemacht.

BTW: den bösen conditional jump ("*src == 0") bringe ich aus der "mark" schleife nicht raus (will der compiler nicht wegmachen - wenns ints statt doubles wären würde er da "setcc" nehmen statt "jcc"), aber wenn sowieso fast alle werte 0 sind sollte es OK sein, dann müsste die jump prediction gut greifen.

p.S.: du kannst es natürlich auch so umbauen dass du den Funktionen nen scratch-space von aussen mitgibst - das würde ich evtl. machen wenn ich draufkommen würde dass zuviel Zeit in "new" draufgeht. z.B. einfach ne non-const Referenz auf nen std::vector, den kann die Funktion dann resizen wenn er zu klein ist, und sonst einfach verwenden. In der Klasse/dem Programmteil wo du die Funktion dann öfters aufrufst packst du den scratch-vector einfach als Member rein, so dass der nie freigegeben wird, und nur mit "resize" vergrössert wenn er zu klein ist. Bzw. der Einfachheit halber 2, einen für char, einen für int.

p.p.S.: den "*src == 0" Test musst du ggf. durch nen Epsilon Test ("fabs(*src) < epsilon") ersetzen - weiss nicht ob du wirklich bei nem double auf 0 testen willst

[*Cpp-Anfänger* 0]

Was hälst du davon, dass du den Strassen-Algorithmus verwendest....

[thordk]

Das einzige was markant ist, ist dass sie dünnbesetzt sind. D.h. von denen ist höchsten 3% - 5% mit werten ungleich Null gefüllt. Aber
eben deshalb das ganze

dann wähl lieber eine entsprechende repräsentation und bläh die matrizen nicht unnötig auf. bei dünn besetzten matrizen macht es sinn, eine form der repräsentation zu wählen, bei der ausschließlich werte ungleich 0 gespeichert werden, der gesamte rest wird einfach als 0 angenommen.

für deine überprüfungen lautet das dann:
markiere alle abstände > 1 für die erste spalte.
lösche alle markierungen N, für die in spalte n ein wert vorhanden ist.
wiederhole bis letzte spalte.
-> markierungen sind 0-zeilen.
verringere y-dim von matrix um anzahl markierungen.

[Mati]

Hallo,

vielen dank für eure regen antworten und vor allem auch an

@Hustbaer für seine Mühe code zu posten - ich werde ihn natürlich (net gleich) aber hoffentlich heute noch testen

@cpp-anfänger: eh ich finde nur schönhage-strassen für ganzzahlmultiplikation und strassen selbst ist für matrix multiplikationen gedacht....wenn du etwas anderes meinst...könntest du da noch genauer werden (evtl. kurzen Link posten?)

@thordk: vollkommen richtig. würde ich liebend gern machen - das !*@&% blöde ist nur dass ich später noch so schöne dinge wie ne qr-zerlegung auf der resultierenden matrix mache ...und dafür brauche ich halt auch einträge die null sind in einer zeile wo noch nicht-null elemente drin sind
Aber danke für die Idee....

[Mati]

@hustbaer: könntest du wenn du zeit hast ein wenig erklären was da passiert bei dir?
würde mir sehr helfen - ein blosses vertauschen von rows und columns passt - es funktioniert auch so...aber ne erklärung brauch ich noch

EDIT: MarkColumns habe ich jetzt kapiert....was heißt denn das andOne? Ist doch überflüssig oder nicht?

EDIT2:

diesen teil bräuchte ich noch etwas erklärt:

// make column advances 
    size_t c = 0; 
    size_t keep = 0; // nr. of columns to keep 
    while(c < columns) 
    { 
        advance[keep]++; 

        if(!flags[c]) 
        { 
             // keep 
            ++keep; 
        } 
        ++c; 
    } 

    if(keep && (keep != columns)) 
    { 
         // make start ptr and fix advance 
        double const* src = matrix + advance[0] - 1; 
        advance[keep] += advance[0]; 
        ++advance; 

         // process all rows 
        double* dest = matrix; 
        size_t n = rows * keep; 
        c = 0; 
        while(n--) 
        { 
            *dest = *src; 
            ++dest; 
            src += advance[c]; 
            ++c; 
            if(c == keep) 
                c = 0; 
        } 
    }

[hustbaer]

Könnte daran liegen dass die linux clib (gcc?) beleidigt ist wenn man mit alloca zuviel Speicher anfordert. Änder das von 1000 mal auf 10 oder so, und guck obs dann immer noch crasht bei grossen Matritzen. Ich werd das heute später noch überprüfen und den ganzen Code nochmal durchgehen. Genaue Erklärung folgt dann auch.

Schonmal soviel: die letzte Schleife kopiert so dass die doubles für die neue Matrix quasi "der Reihe nach" geschrieben werden, also geschrieben wird matrix[0], dann matrix[1], matrix[2], matrix[3] etc. - ganz egal welche columns gelöscht werden. Das ist gut weil cache misses beim schreiben viel teurer sind als beim lesen (die cache-row muss ja wieder zurückgeschrieben werden). Und dazu muss die Schleife wissen wie weit sie der "source" Zeiger nach jedem kopierten Wert weiterrücken muss, und natürlich muss man den "source" Zeiger zu Beginn auch auf den ersten nicht-zu-löschenden Wert setzen. Diese "Weiterspring-Weiten" sind im "advance" Array gespeichert. Natürlich könnte man die Schleife auch über die gesamte Matrix laufen lassen, und dann quasi jedesmal mit "if" checken ob die Column gelöscht wird oder nicht, aber ifs sind teuer und langsam und böse (*g*), und es macht ja auch wenig Sinn über die ganze Matritze drüberzupfeiffen wenn man doch bloss die Werte die man wirklich kopieren will einsammeln muss. Und da der Schreibe-Zeiger immer gleich auf mit oder vor dem Lese-Zeiger ist geht das auch ohne dass man sich seine Source-Werte überschreibt bevor man sie kopiert hat.

Ahja, wenn der Fehler nicht am alloca liegt würde es helfen wenn du den gesamten Callstack hier reinklatscht. Kenn mich bei Linux nich so aus, hab auch keins laufen, und auch die Sourcecodes nicht zur Hand.

Und das "NukeZeroColumnsAndOne" heisst lösche alle "alles null" Zeilen, und eine die per Index spezifiziert wird ("und eine": "and one"). Deine Funktion macht das ja auch so, dachte mir du wirst das wohl auch brauchen, sonst wäre das Parameter ja ziemlich Sinn-frei.

[Mati]

passt passt...es war ein fehler meinerseits...es funktioniert für beliebig große matrizen!!!

Vielen dank hustbaer....ich schaffe es nicht mehr zu profilen heute aber morgen sag ich auf alle fälle bescheid wie groß der speed up ist

jetzt verstehe ich nur noch nicht wie du dir die spungweiten merkst:

Sehr eleganz übrigens diese methodik....da muss ich noch um einiges fitter werden
großes dankeschön schon mal an dieser stelle....mein pointer-wissen steigt

// make column advances 
     size_t c = 0; 
     size_t keep = 0; // nr. of columns to keep 
     while(c < columns) 
     { 
         advance[keep]++; 

         if(!flags[c]) 
         { 
              // keep 
             ++keep; 
         } 
         ++c; 
     }

[hustbaer]

Mati schrieb:

...aber morgen sag ich auf alle fälle bescheid wie groß der speed up ist

(...)

jetzt verstehe ich nur noch nicht wie du dir die spungweiten merkst:

(...)

Naja, hoffentlich isses überhaupt schneller als deine Version (denke aber schon)

Also erstmal die Schleife läuft über alle Spalten der ausgangs Matrix drüber.
Anfangen in "advance" zu zählen tun wir mit "advance[0]" ("keep" ist der Index - ist an der Stelle kein guter Name, aber ich bin faul *pfeiff*). Nun wird "advance[keep]" in jedem Durchlauf um eins inkrementiert, und danach wird "keep" inkrementiert (also zum nächsten Element in advance umgeschaltet) wenn die aktuelle Spalte eine ist die übernommen werden soll. Das führt dazu dass nachdem die Schleife durchgelaufen ist in "advance" bestimmte "Distanzen" gesammelt sind, und "keep" die Anzahl der zu kopierenden Spalten enthält. Sagen wir mal "keep" ist 5. Advance sieht dann so aus:

advance[0] = ???
advance[1] = Distanz von der ersten zu kopierenden Spalte zur zweiten zu kopierenden Spalte
advance[2] = Distanz von der zweiten zu kopierenden Spalte zur dritten zu kopierenden Spalte
advance[3] = ... von der dritten zur vierten ...
advance[4] = ... von der vierten zur fünften ...
advance[5] = ???

Eine Distanz von 1 heisst dabei es ist die nächste Spalte, es wird also nix übersprungen (keine Spalte dazwischen ausgelassen). 1 ist also das Minimum. Soweit sollte es denke ich klar sein.

Was steht nun in "advance[0]" und "advance[5]". Hm. Also es gibt keine "nullte zu kopierende Spalte" - von daher muss da was anderes drinstehen. Gucken wir uns an was in "advance[0]" drin steht wenn wir gleich die erste Spalte der original Matrix kopieren wollen, bzw. was wenn wir erst die zweite kopieren wollen. Im ersten Fall (gleich die erste Spalte soll kopiert werden) steht in "advance[0]" eben 1 drin (zuerst wird "advance[0]" von 0 auf 1 inkrementiert, dann wird "keep" inkrementiert, womit der Wert von "advance[0]" sich nimmer ändern kann). Im zweiten Fall steht in "advance[0]" eben 2 drin, sollte auch klar sein.

-> In "advance[0]" steht die Spaltennummer der ersten zu kopierenden Spalte, bzw. anders ausgedrückt: die Distanz von der imaginären nullten Spalte der original Matrix zur ersten Spalte die kopiert werden soll. Oder noch anders gesagt: die Distanz von der letzten Spalte in der vorhergehenden Zeile zur ersten Spalte die kopiert werden soll in der neuen Zeile.

Und in "advance[5]"? Was relativ leicht ersichtlich ist: wenn die 5. zu kopierende Spalte auch die letzte in der original Matrix war, steht in "advance[5]" 0. Ich kürze hier etwas ab, und behaupte einfach: in "advance[5]" steht die Distanz von der letzten zu kopierenden Spalte zur letzten Spalte der original Matrix
(Wenn die letzte zu kopierende Spalte zugleich die überhaupt letzte Spalte ist dann ist diese Distanz eben 0)

So, was haben/können wir bis jetzt. Wir haben die Distanzen zwischen allen zu kopierenden Spalten 1 bis 5, fehlt nur noch die Distanz von 5 auf 1, also der Sprung zur nächsten Zeile. Und den bekommen wir einfach durch "advance[5] + advance[0]", denn "advance[5]" bringt uns bis zur letzten Spalte der original Matrix, und "advance[0]" bringt uns von dort weiter zur ersten zu kopierenden Spalte.

Daher die Addition:

advance[keep] += advance[0];

In "advance[keep]" steht nun also diese Distanz von der letzten zu kopierenden Spalte zur ersten zu kopierenden in der nächsten Zeile.

Jetzt steht in jedem "advance[N]" also (mit N von 1 bis "keep") die korrekte Distanz zum nächsten zu kopierenden Element. Da ich aber mit einem 0 basierten Index drauffahre rücke ich den Zeiger "advance" noch um ein Element weiter, so dass ich nun mit 0...(keep-1) drauffahren kann.

Jetzt fehlt nur noch die korrekte Startposition, und das ist auch einfach. In "advance[0]" (VOR dem weiterrücken des Zeigers!) steht ja die (1-basierte) Nummer der ersten zu kopierenden Spalte, also muss ich bloss vom Anfang der Matrix "advance[0] - 1" Elemente weitergehen um dort zu landen.

Und dann muss nur noch kopiert werden

Ich hoffe das war einigermassen verständlich. Wenn nicht sag einfach bescheid, wenns an einem bestimmten Punkt hakt kann ich dir das nochmal genauer erklären, bzw. es versuchen.

[hustbaer]

So. Hab nu selbst ein wenig Profiling gemacht (MSVC 7.1, single threaded runtime, Release, Full Opt.)...

Ich denke es wird sich auszahlen
Bitte schreib was sobald du Resultate hast... würde mich interessieren wie schnell das bei dir wirklich ist (mit "realen" Daten und so).

[Mati]

hallo hustbaer...

ich hätte noch ne frage...warum bentzt du char arrays?

ich versuche gerade noch eine zeile einzufügen die aber probleme macht:

const int col = 8; //z.B
flags[col] = 1;

kann ich so denn nicht ein char array verändern?

Ich komme einfach nicht zum austesten...aber damit ichs vergleichen kann muss ich eben die obige zeile einsetzen...

auf diese weise gehts:

char* unit; 
    char* dynamicBuffer = 0; 

     // alloc temp space 
    if(rows <= 1000) 
        unit = static_cast<char*>(alloca(rows)); 
    else 
    { 
        dynamicBuffer = new char[rows]; 
        unit = dynamicBuffer; 
    }
    unit[unit_col] = true;

    c = 0; 
    n = rows; 
    while(n--) 
    { 
        flags[c] &= unit[c]; 
        ++c; ++src; 
    } 

    delete [] dynamicBuffer;

aber als abkürzung reicht doch ein einzeiler bei dem ich lediglich eine stelle auf true setze....nur
läuft das so nicht korrekt...und am ende gibts nen sefault *grmpf

[hustbaer]

Mati, Freund, was glaubst du was folgende Stelle macht?

size_t NukeZeroColumnsAndOne(double* matrix, size_t rows, size_t columns, long andOne) 
{ 
    // ...
        MarkZeroColumns(matrix, rows, columns, flags); 
        if((andOne >= 0) && (andOne < columns)) 
            flags[andOne] = 1; 
    // ...
}

Naja, egal. Klar reicht es wenn du einfach eine Stelle in "flags" auf true setzt nachdem MarkZeroColumns gelaufen ist. Du musst natürlich sicher stellen dass der Index >= 0 und < "rows" ist.

Und ein char array verwende ich weil ein char das kleinste ist was man in C++ direkt addressieren kann (brauch ja bloss 1 bit), und weil bei bool die Chance bestehen würde dass der Compiler sich genötigt fühlt langsameren Code zu erzeugen als mit char möglich wäre.

Dass du seg-faults bekommst verstehe ich nicht ganz, bei mir läuft das ohne Probleme, auch mit 4000x4000 Matritzen...

[Mati]

ach scheiße...jetzt versteh ichs auch ...peinlich sorry -
ich mach mich endlcih ans profiling....sorry

[hustbaer]

Kein Problem

[Mati]

*lach
langsam werd ich verrückt...Ich glaube ich hab nen BUG:

versuch mal als input folgende "matrix"
0 0 0 0 0 5

und als andOne = 4 oder andOne = 3

ich bin dabei schon zu lösen aber habs nocht net ....grrrrrr
EDIT: ich heinz: sollte auch beschreiben worans liegt:
also er nimmt in keep hier nicht mehr die eine zeile auf die behalten werden soll durch das andOne...

[hustbaer]

Hihi.
Ja das liegt daran weil ich das falsch verstanden habe, und die Logik umgedreht *pfeiff*
Er behält also nicht die Zeile deren Nummer du übergibst sondern er löscht die dann immer

Ändere einfach das "flags[andOne] = 1" auf "flags[andOne] = 0". Den Funktionsnamen und den Namen "andOne" solltest du dann natürlich entsprechend anpassen.

[Mati]

jo jetzt hab ichs
geprofiled auch - respekt.

Die harte pointer-arithmetik und dein algorithmus bringen bei meinen testläufen sehr viel.
Ich habe natürlich die methode zum nullzeilenlöschen innerhalb eines anderen algorithmus.
Ursprünglich nach meiner ersten implementierung frass sie 75 % der gesamtlaufzeit. Habe dann eine optimierung (reimplemenierung der methode) gemacht und den anteil auf 55 - 60% gedrückt. Mit deiner variante bekomme ich jetzt 20 - 25 % ! Das ist enorm!

Vielen dank an dieser stelle! Es funkioniert wunderbar