Folgende - nicht so seltene Problem - wurde in dclc im Nov 2001 aufgeworfen. Nach einer kurzen Diskussion hat Hans Eder die beiden Hauptvarianten implementiert und mir den Code und seine Benchmark-Ergebnisse zugeschickt und die Verwendung hier zugelassen. -- HelmutLeitner

Der OP hat TrueColorBilder und möchte auf Grund der RGB-Werte eine ja-nein Entscheidung möglichst effizient durchführen. Die konkrete Aufgabenstellung wurde noch nicht genannt, aber die gleiche Situation wäre bei einer Umwandlung TrueColorBilder -> MonoChromBilder? gegeben (ähnliche Aufgabenstellungen ergeben sich auch bei der Umwandlung in Bilder mit Farbpaletten).

Der auf der Hand liegende Lösungsansatz besteht darin, die Berechnung nicht für jedes einzelne Pixel durchzuführen, sondern TabellenStattBerechnungen zu verwenden. Offen sind die Fragen nach der optimalen Repräsentation dieser Tabellen und der bestmöglichen Performance. Siehe auch SpeicherplatzFürPerformance.

Variante 1: Bit-Array simulieren

Es gibt genug leicht verfügbaren Code um einen Bit-Array der Dimension 2^24 zu simulieren (z.B. www.snippets.org). Natürlich kostet die Positionsberechnung und der Zugriff auf das Einzelbit ein wenig Rechenzeit.

Vorteile:

• Keine Kompromisse in der Exaktheit der Transformation.
• ...

• Der Speicherbedarf ist immer noch ziemlich hoch (2 MB)
• Die Vorbereitung der Tabelle erfordert die Vorberechnung von 16 Mio Einzelwerten, was vermutlich wieder eigene Optimierungsüberlegungen (Effiziente Berechnung? Tabelle in einem File speichern? Lohnt sich das z.B. für ein Einzelbild) nach sich zieht.
• Die Performance ist etwas schlechter als in Variante 2
• ...

Variante 2: Char-Array und Reduktion der Auflösung

Man kann meist auf einen Teil der Präzision in der Einzelfarbe (1-3 Bit) verzichten (z.B. durch r>>=2; g>>=2; b>>=2) und dann mit einem normalen komfortablen Array:

char ColorDecisionArray[64][64][64];

arbeiten.

Vorteile:

• Performance ist besser
• Speicherbedarf ist geringer (im Beispiel 256 KB) und varierbar.
• Es müssen auch wesentlich weniger Funktionswerte vorberechnet werden.
• Die Optimierung ist auch für mehr als Ja-Nein-Entscheidungen anwendbar (es sind 7 Bit Reserve vorhanden).
• ...

• Man verzichtet auf Präzision.

Auf meinem Rechner (Pentium 166, C++Builder 3.0) ist die Variante 2 rund doppelt so schnell wie die Variante 1 (3100 gegen 1500 Durchläufe in 2 Sekunden). Ich habe versucht eine möglichst wirklichkeitsnahe und faire Testumgebung für dieses Problem zu erstellen. Hier mein Testprogramm: #include <time.h> #include <stdlib.h> #include <stdio.h> #define TESTLEN 1024 #define LOOPTIME 2.0 typedef unsigned long ul; unsigned char ColorDecisionArray [64][64][64]; /* 256 kByte*/ unsigned char ColorDecisionBitArray [32L*32*32*8*8*8/8]; /* 2 Mbyte */ unsigned char col[TESTLEN]; #define COLOR_DECISION_GET(R, G, B, V) { unsigned long pos = ((ul)(G&248)<<13) | ((ul)(R&248)<<8) | ((B&248)<<3) | ((G&7)<<3) | (R&7); V = (unsigned char)((ColorDecisionBitArray [pos] >> (B&7) )&1); } #define COLOR_DECISION_SET(R, G, B, V) { unsigned long pos = ((ul)(G&248)<<13) | ((ul)(R&248)<<8) | ((B&248)<<3) | ((G&7)<<3) | (R&7); if ( V == 0 ) ColorDecisionBitArray [pos] &= (unsigned char)(~(1 <<(B&7))); else ColorDecisionBitArray [pos] |= (unsigned char)( (1 <<(B&7))); } int main(void) { int n, i; clock_t start; unsigned char red[TESTLEN], green[TESTLEN], blue[TESTLEN]; unsigned char *r,*g,*b,*c; for (i=0; i<TESTLEN; i++) { red[i] = (unsigned char)rand(); green[i]= (unsigned char)rand(); blue[i] = (unsigned char)rand(); } for (n=0, start=clock(); ((clock()-start)/CLK_TCK)<LOOPTIME; n++) { for (c=col,r=red,g=green,b=blue,i=0; i<TESTLEN; i++,r++,g++,b++,c++) ColorDecisionArray[*r>>2][*g>>2][*b>>2] = *c; for (c=col,r=red,g=green,b=blue,i=0; i<TESTLEN; i++,r++,g++,b++,c++) *c = ColorDecisionArray[*r>>2][*g>>2][*b>>2]; } printf("Highscore Leitner : %d Loops\n",n); for (n=0, start=clock(); ((clock()-start)/CLK_TCK)<LOOPTIME; n++) { for (c=col,r=red,g=green,b=blue,i=0; i<TESTLEN; i++,r++,g++,b++,c++) COLOR_DECISION_SET(*r, *g, *b, *c); for (c=col,r=red,g=green,b=blue,i=0; i<TESTLEN; i++,r++,g++,b++,c++) COLOR_DECISION_GET(*r, *g, *b, *c); } printf("Highscore Klemm : %d Loops\n",n); return 0; } mfg hans eder

Anmerkung 1: Die Schleifendurchläufe sind nur als qualitatives Maß für die Geschwindigkeit zu sehen, weil oben der - allerdings nicht sehr große - Schleifenoverhead mitgemessen wurden.

Anmerkung 2: Das Mischen der Bits in der Variante 2 ergibt eine geringfügige Verbesserung der Performance, vermutlich auf Grund der von Frank Klemm ins Spiel gebrachten besseren "Lokalität" der Zugriffe!? Eine vereinfachte Variante mit konventioneller Bitanordnung ist interessanterweise um einige Prozent langsamer.

Anmerkung 3: Die Ergebnisse könne teilweise stark vom Prozessor abhängig sein. Auf einem 750 MHz Athlon / Win98 / Borland C 5.0x war das Verhältnis ca. 18000:12000 Schleifendurchläufe in den gleichen 2 Sekunden.