effizient programmieren - suche tips...

hallo,

bin grad an einer programmiersache, die sehr viele array-durchläufe benötigt und bei größeren daten enorm zeit frisst.
es geht z.b. darum, dass ich grauwertdaten eines volumina hab (also z.b. grauwerte für jedes voxel innerhalb der dimensionen 64*256*512 z.b.)).
will ich die grauwerte nun vom orginalgrauwertbereich runterschrauben auf vielleicht 32 grauwerte, muss ich je jeden grauwert ersetzen mit dem neuen wert...
kann man das irgendwie vereinfachen?
im moment hab ich da 3 ineinandergeschachtelte for-schleifen und da wird dann für jeden grauwert geschaut, welcher neue wert an dessen stelle muss. aber das dauert...
na ja, und solche schleifen tauchen in meinem projekt immer wieder auf (in verschiedener anwendung.
bringt es was die daten beispielsweise in ein 1-dimensionales array zu konvertieren (im moment isses ja ein 3d-array)?
vielleicht kennt ja auch jemand eine nette seite, die sich mit solchen zeitfresser-problemen beschäftigt?

würde mich über tips freuen...

vg, july

Marc++us

Das nach 1 Dimension umzusetzen ändert nichts an Deinem Problem - die Datenmenge bleibt gleich, und bei einem 3D-Array erledigt der Compiler die Umrechnung der Indizes, bei einem 1D-Array mußt Du es manuell machen.

Gewinn: 0

Sag lieber mal was über den Wertebereich der Daten: aus welchem Werteintervall sind Deine Grauwerte? 0..255?

es sind integer-werte. muss aber nicht 0-255 sein, sondern kann z.b. auch 0-480 sein oder so. in dem konkreten einen fall will ich halt anhand bestimmter grauwertbins (die ich vorher ermittle) die werte auf 0-32 (z.b) bekommen.

wie machen das eigentlich grafikprogramme, wenn sie filter etc. anwenden? so zeitintensiv kommt mir das da nicht vor...

Cpp_Junky

Hmm Voxel ?
Geht es um dreidimensionale Darstellung also Voxel-Grafik (3d) ?
Und was meinst du genau mit Grauwerten ? Willst du sowas wie schattierungen machen ?
/me ist verwirrt :p

ja, ich meine mit voxel schon 3d-punkte.
es ist so, dass ich bildreihen habe (als einen stapel 2d-bilder).
die dritte dimension ist quasi die zeit.
jedes pixel in jedem bild hat also einen grauwert (wie ein ganz normales graues bild eben ). damit die weiteren berechnungen nicht so aufwendig werden, will ich statt der z.b. 400 verschiedenen grauwerte nur noch 32 verwenden. also teil ich meinen grauwertbereich in 32 teile und je nach dem in welchen bereich ein grauwert fällt, wird ihm der neue grauwert zugeordnet.
jetzt etwas klarer?

Bashar

Warum soll man das Arraydurchlaufen nicht vereinfachen können?

Typ array[64][256][512];
const int ende = 64 * 256 * 512;
for (int i = 0; i < ende; ++i) {
  machwas(((Typ*)array)[i]);
}

Ich seh da keine manuelle Indexberechnung. Obs was bringt ist die andere Frage, und obs überhaupt geht die nächste -- wenn das Array nicht komplett vererbeitet werden soll wird das schon schwieriger.

TheTester

die dritte dimension ist quasi die zeit.

heisst das die Anzahl der Bilder ist die Tiefe deiner 3d Datenstruktur?

wie machen das eigentlich grafikprogramme,
wenn sie filter etc. anwenden? so zeitintensiv
kommt mir das da nicht vor...

Die nehmen meist ein Pixel und seine umliegenden Nachbarn, daraus kannst du eine große Matrix bauen und die multiplizierst du dann meist nur noch mit einem Vektor.

Und ich glaub was du da versuchst nennt sich "Vektor Quantisierung". Musst mal schaun aber ich denk schon das es dafür halbwegs schnelle Algorithmen gibt.

bye

tt

Cpp_Junky

Ne!
Also ganz langsam (damit sogar ich das kapier ) ...
Was sind das für Bilder und was willst du damit anstellen ?

heisst das die Anzahl der Bilder ist die Tiefe deiner 3d Datenstruktur?

genau

da muss ich direkt mal unter dem begriff "Vektor Quantisierung" schauen, vielleicht werd ich ja fündig...

Was sind das für Bilder und was willst du damit anstellen ?

Also folgendes:

die Bilder sind medizinische Aufnahmen (MRT). sie haben beispielsweise dimensionen von 256x512. die verschiedenen aufnahmen sind entweder zu verschiedenen zeiten aufgenommen worden, oder aber sie stellen die schichten des untersuchten organs oder was auch immer dar.
die pixel sind grauwerte, haben also irgendwelche integer-werte (der einfachheit halber nehmen wir mal an im bereich 0 bis 255)
da ich in der weiteren verabreitung ziemlich viel mit den grauwerten arbeiten muss, wird es weniger rechenintensiv, wenn es weniger verschiedene grauwerte sind. also teil ich meinen bereich (0-255) z.b. in 32 teilbereiche auf (in diesem fall würden die bereiche dann jeweils 8 grauwerte beinhalten, d.h. die originalwerte von 0 bis 7 bekämen jetzt den neuen wert 0, die originalwerte von 8 bis 15 bekämen eine 1 usw).
na ja, und dazu muss ich ja jeden originalgrauwert abklappern, schauen, in welchen bereich er gehört und den neuen wert zuordnen. daher die vielen schleifen...

Obs was bringt ist die andere Frage, und obs überhaupt geht die nächste

hab's vorhin mal probiert, aber scheint nicht wirklich schneller zu sein

Marc++us

July schrieb:

na ja, und dazu muss ich ja jeden originalgrauwert abklappern, schauen, in welchen bereich er gehört und den neuen wert zuordnen. daher die vielen schleifen...

Nicht zwangsläufig.

Angenommen Du kannst die Anzahl der Grauwerte so wählen, daß es immer um eine Potenz von 2 geht - dann kannst Du die Originalwerte z.B. unverändert lassen, aber bei einem Zugriff machst Du sowas:

(z.B. 0..255 als Originalwerte und Du willst Werte im Bereich 0..31 haben)

return wuerfel[x][y][z] >> 3;

Aber das macht nur Sinn, wenn jedes Element nur selten gelesen wird. Mir ist noch nicht klar, warum die ganze Operation bei Dir so lange dauern soll. Falls Du irgendwelche Algorithmen optimierst, die bei weniger Grauwerten schneller arbeiten, so klingen die in meinen Ohren wesentlich aufwendiger als eine Umskalierung von Grauwerten.

Wie skalierst Du denn die Grauwertpalette um? Vielleicht sollte man da mal ansetzen.

hab's vorhin mal probiert, aber scheint nicht wirklich schneller zu sein

Welch Wunder.

musicman

Ich denke mal, dass du da nicht drumrum kommen wirst, da du einfach jeden Pixel verarbeiter musst. Also ergibt sich halt einfach der folgende Code:

for (int i = 0; i < ende; ++i)
{
newVal[i] = (oldVal[i] * newMaximumValue) / oldMaxOccuringValue;
}

Mir fällt da sonst keine mögliche Optimierung ein.

jetzt steh ich auf'm schlauch *verwirrt ist*

Falls Du irgendwelche Algorithmen optimierst, die bei weniger Grauwerten schneller arbeiten, so klingen die in meinen Ohren wesentlich aufwendiger als eine Umskalierung von Grauwerten.
Wie skalierst Du denn die Grauwertpalette um?

was verstehst du unter "umskalierung von grauwerten"? das ist doch das, was ich machen will und was ich die ganze zeit zu erklären versuche, oder nicht???

musicman

July schrieb:

was verstehst du unter "umskalierung von grauwerten"? das ist doch das, was ich machen will und was ich die ganze zeit zu erklären versuche, oder nicht???

Genau, und das macht der Algo den ich grad gepostet habe.

na des mach ich doch auch...
nur das es nicht ganz so einfach ist, da ich die dunklen werte gesondert behandeln muss. das histogram hat ne ziemlich charakteristische kurve, bei der erst ein haufen schwarze werte auftauchen, dann geht das histogram zurück und hat dann erst wieder bei den relevanten grauwerten größere werte.
mit dem geglätteten histogram such ich dann nach dem minimum. alle werte darunter bekommen den neuen wert 0, den rest teil ich gleichmäßig von 1-31 auf.
sinn des ganzen? schwarzabstufungen sind in der weiterverabreitung störend, da sie zum inhalt des bildes nix beitragen.
tja, dadurch ist die zuordnung nich ganz so einfach. ich merk mir dann halt in einem array die grenzen und such dann unter welcher grenze der jeweilig grauwert liegt.
alles in allem brauch mein rechi wohl so an die 4 minuten um 1 (!) bild umzurechnen und das mal 64... gute nacht...

vielleicht würde es ja (etwas zumindest) bringen, wenn ich mir vorher ein array anlege, dass auf den indizees (0-255) den passenden grauwert speichert. da müsste ich nicht jedesmal umständlich ermitteln, mit welchem wert ich ersetzen muss...
wird aber schon wieder komplizierter, wenn es auch negative grauwerte gibt...

Winn

Servus,

da ich derzeit eine ähnliche Problemstellung hatte, erstmal meine Skalierungsfunktion

void BuildLinearScale(const double ValMin, const double ValMax, const int iDisc, double *dDisc)
	{
		double Bandwidth;
		double Delta;
		int i;

		Bandwidth=0.;
		Bandwidth+=fabs(ValMax);
		Bandwidth-=fabs(ValMin);
		Delta=Bandwidth/iDisc;

		for(i=0;i<iDisc;i++) dDisc[i]=ValMin+i*Delta;		
	}

Die Anzahl der Diskretisierungen "iDisc" ist freiwählbar. Mit dieser Funktion untersuche ich mein 4D Array (!), 3 für den Raum und eine für die Zeit nach Werten in dieser Skala.

for(i=0;i<iXCells;i++)
	for(j=0;j<iYCells;j++)
		for(k=0;k<iZCells;k++)
			{
				for(n=0;n<iNDumps;n++)
					{
						for(l=0;l<iDisc-11;l+=10)
							{
								if ((TFx(n,i,j,k)<=dDisc[l+1]) && (dDisc[l]>=TFx(n,i,j,k))) TP(l,i,j,k)+=1.;
								if ((TFy(n,i,j,k)<=dDisc[l+1]) && (dDisc[l]>=TFy(n,i,j,k))) TP(l,i,j,k)+=1.;
								if ((TFz(n,i,j,k)<=dDisc[l+1]) && (dDisc[l]>=TFz(n,i,j,k))) TP(l,i,j,k)+=1.;

								if ((TFx(n,i,j,k)<=dDisc[l+2]) && (dDisc[l+1]>=TFx(n,i,j,k))) TP(l+1,i,j,k)+=1.;
								if ((TFy(n,i,j,k)<=dDisc[l+2]) && (dDisc[l+1]>=TFy(n,i,j,k))) TP(l+1,i,j,k)+=1.;
								if ((TFz(n,i,j,k)<=dDisc[l+2]) && (dDisc[l+1]>=TFz(n,i,j,k))) TP(l+1,i,j,k)+=1.;

								if ((TFx(n,i,j,k)<=dDisc[l+3]) && (dDisc[l+2]>=TFx(n,i,j,k))) TP(l+2,i,j,k)+=1.;
								if ((TFy(n,i,j,k)<=dDisc[l+3]) && (dDisc[l+2]>=TFy(n,i,j,k))) TP(l+2,i,j,k)+=1.;
								if ((TFz(n,i,j,k)<=dDisc[l+3]) && (dDisc[l+2]>=TFz(n,i,j,k))) TP(l+2,i,j,k)+=1.;

								if ((TFx(n,i,j,k)<=dDisc[l+4]) && (dDisc[l+3]>=TFx(n,i,j,k))) TP(l+3,i,j,k)+=1.;
								if ((TFy(n,i,j,k)<=dDisc[l+4]) && (dDisc[l+3]>=TFy(n,i,j,k))) TP(l+3,i,j,k)+=1.;
								if ((TFz(n,i,j,k)<=dDisc[l+4]) && (dDisc[l+3]>=TFz(n,i,j,k))) TP(l+3,i,j,k)+=1.;

								if ((TFx(n,i,j,k)<=dDisc[l+5]) && (dDisc[l+4]>=TFx(n,i,j,k))) TP(l+4,i,j,k)+=1.;
								if ((TFy(n,i,j,k)<=dDisc[l+5]) && (dDisc[l+4]>=TFy(n,i,j,k))) TP(l+4,i,j,k)+=1.;
								if ((TFz(n,i,j,k)<=dDisc[l+5]) && (dDisc[l+4]>=TFz(n,i,j,k))) TP(l+4,i,j,k)+=1.;

								if ((TFx(n,i,j,k)<=dDisc[l+6]) && (dDisc[l+5]>=TFx(n,i,j,k))) TP(l+5,i,j,k)+=1.;
								if ((TFy(n,i,j,k)<=dDisc[l+6]) && (dDisc[l+5]>=TFy(n,i,j,k))) TP(l+5,i,j,k)+=1.;
								if ((TFz(n,i,j,k)<=dDisc[l+6]) && (dDisc[l+5]>=TFz(n,i,j,k))) TP(l+5,i,j,k)+=1.;

								if ((TFx(n,i,j,k)<=dDisc[l+7]) && (dDisc[l+6]>=TFx(n,i,j,k))) TP(l+6,i,j,k)+=1.;
								if ((TFy(n,i,j,k)<=dDisc[l+7]) && (dDisc[l+6]>=TFy(n,i,j,k))) TP(l+6,i,j,k)+=1.;
								if ((TFz(n,i,j,k)<=dDisc[l+7]) && (dDisc[l+6]>=TFz(n,i,j,k))) TP(l+6,i,j,k)+=1.;

								if ((TFx(n,i,j,k)<=dDisc[l+8]) && (dDisc[l+7]>=TFx(n,i,j,k))) TP(l+7,i,j,k)+=1.;
								if ((TFy(n,i,j,k)<=dDisc[l+8]) && (dDisc[l+7]>=TFy(n,i,j,k))) TP(l+7,i,j,k)+=1.;
								if ((TFz(n,i,j,k)<=dDisc[l+8]) && (dDisc[l+7]>=TFz(n,i,j,k))) TP(l+7,i,j,k)+=1.;

								if ((TFx(n,i,j,k)<=dDisc[l+9]) && (dDisc[l+8]>=TFx(n,i,j,k))) TP(l+8,i,j,k)+=1.;
								if ((TFy(n,i,j,k)<=dDisc[l+9]) && (dDisc[l+8]>=TFy(n,i,j,k))) TP(l+8,i,j,k)+=1.;
								if ((TFz(n,i,j,k)<=dDisc[l+9]) && (dDisc[l+8]>=TFz(n,i,j,k))) TP(l+8,i,j,k)+=1.;

								if ((TFx(n,i,j,k)<=dDisc[l+10]) && (dDisc[l+9]>=TFx(n,i,j,k))) TP(l+9,i,j,k)+=1.;
								if ((TFy(n,i,j,k)<=dDisc[l+10]) && (dDisc[l+9]>=TFy(n,i,j,k))) TP(l+9,i,j,k)+=1.;
								if ((TFz(n,i,j,k)<=dDisc[l+10]) && (dDisc[l+9]>=TFz(n,i,j,k))) TP(l+9,i,j,k)+=1.;
							}

						qty=(n+1)*iXCells*iYCells*iZCells;
						for(l=0;l<iDisc-1;l++) TP(l,i,j,k)/=qty;
						for(l=0;l<iDisc-1;l++) TE(n,i,j,k)+=CalcSingleEntropy(TP(l,i,j,k));
						for(l=0;l<iDisc-1;l++) TP(l,i,j,k)*=qty;
					}
				PrintProgress(now,end);	
				now+=1.;
			}

n=Zeitschritt
i,j,k=x,y,z Koordinate
TFX,TFy,TFz mein 4D Array

Dieser Schreibaufwand in der letzten For-Schleife hat für deutlichen Schub gesorgt, der Prozessor kann dadurch ungestörter seine eigentliche Arbeit leisten, anstatt die Zählvariablen zu inkrementieren und nach größer kleiner zu prüfen.

Winn

musicman schrieb:

July schrieb:

was verstehst du unter "umskalierung von grauwerten"? das ist doch das, was ich machen will und was ich die ganze zeit zu erklären versuche, oder nicht???

Genau, und das macht der Algo den ich grad gepostet habe.

Glaube ich nicht. Ich glaube, dass der Code, den du da gepostet hast, nur Unsinn macht.

@Winn:

das heißt, du testet deine grenzen in 10er-schritten ab, wenn ich das richtig verstehe. hmm, schon möglich, dass es effizienter ist, als alle grenzen einzeln durchlaufen zu lassen...
allerdings, was wäre im vergleich zu der idee mir halt vorher schon ein array anzulegen, welches über den index (=alter grauwert) zum neuen grauwert führt?
so bräuchte ich gar keine tests wegen der grenzen mehr machen, sondern würde einfach den wert jedes voxels (v-alt) mit dem wert des arrays an der stelle v-alt ersetzen...
oder lahmt das ebenfalls?

Winn

July schrieb:

@Winn:

das heißt, du testet deine grenzen in 10er-schritten ab, wenn ich das richtig verstehe. hmm, schon möglich, dass es effizienter ist, als alle grenzen einzeln durchlaufen zu lassen...
allerdings, was wäre im vergleich zu der idee mir halt vorher schon ein array anzulegen, welches über den index (=alter grauwert) zum neuen grauwert führt?
so bräuchte ich gar keine tests wegen der grenzen mehr machen, sondern würde einfach den wert jedes voxels (v-alt) mit dem wert des arrays an der stelle v-alt ersetzen...oder lahmt das ebenfalls?

Also ich denke, daß es vom Prinzip meinem Beispiel gleicht. Das Array "ALT" wird durch ein Array "NEU" neu kategorisiert. Das entspricht einer linearen Skalierung oder Quantisierung (Abstände $$\Delta_i=\Delta_{i+1}$$). Bei der Überprüfung oder beim Schreiben der "NEUEN" Werte in die "ALTEN" Werte wirst Du wahrscheinlich ähnliche Prüfungsroutinen (Setze NEU Werte, wenn ALT Wert in einem Interval [a,b] liegt) haben, die wenn Du sie in einem 10er Block zusammenführst, schneller sind. Hab ich das richtig verstanden ?