[quote=Spacerat]Mittelpunktes der BB[/quote] klingt nett auch wenn ich nicht allzu genau verstehe was ihr beide da plant
(oder nur du und @AmunRa eher bei meiner Idee ),
auch nicht zu genau zu verstehen versucht , lieber selber ein kleines Testprogramm, dauert auch so schon lange genug
ich habe deinen Code zum Vergleich zum Teil übernommen und eher noch vereinfacht (kein ==-Vergleich bei bei mir) statt zu optimieren,
ich teste hier auch mit völligen Zufallszahlen = Farben, keine Häufigkeiten-Sortierung usw., das muss dann zu deinem Programm keine Aussage haben
Idee: Palette von 1000 Farben, Aufspaltung des Raums in Würfel mit 16 Pixel Seitenlänge (Variable r),
für jeden der im Moment 161616 = 4092 Würfel von Mittelpunkt aus mit der ‚normalen Suche‘ durch alle Palettenfarben Kandidaten bestimmen,
die naheste Farbe sowie alle bis maximal Variable ‚radius‘ höheren Abstand,
diesen radius zu wählen ist für mich etwas kompliziert, problematisch bei dünn besetzten Paletten,
ferne Punkte haben hohe Differenzunterschiede nach der aktuellen Rechnung, da muss der radius eigentlich höher gewählt werden,
bei 1000 Farben wird es aber wohl nicht so viel Abstand geben, jedenfalls keine sichere Sache, alles provisorisch,
exakte normalisierte Abstandsberechnung wäre hilfreich, mit Tradeoff höhere Berechnungskosten, Wurzel…
im geposteten Beispiel sind 30-200 Farben in jedem der 4092 Würfel, ziemlich breit gefächert, aber leistet schon einiges,
bei der Suche wird wie schon mal vorgeschlagen zu jeder Suchfarbe erst der Würfel bestimmt, dann nur mit den Farben dort verglichen
Ergebnis akutell:
1000 Palette, 500.000 Zufallsfarben suchen,
Initialisierung: 0.2-0.3 sec
normale Suche mit Durchlauf über alle 1000 Palettenfarben: 3.3 sec
Suche mit Würfeln: 0.5 sec
Streichung des Faktors 5 beim Radius führt auch noch zur korrekten Checksumme, nur noch um die 20 Farben in jedem Würfel,
Suche mit Würfeln sinkt dann auf unter 0.1 sec bei mir
public class Test
{
static Random rand = new Random(42);
static final int nSearch = 500000;
static Col[] search = new Col[nSearch];
static int nPalette = 1000;
static Col[] palette;
static final int r = 16;
static final int r2 = 256 / r;
static final int radius = (int)(5 * 3 * r2 * 1.5 * r2 * 1.5);
static final Col[][][][] room = new Col[r][r][r][];
public static void main(String[] args)
{
debug("Start main");
Set<Col> setP = new HashSet<Col>();
do
{
setP.add(nextCol());
}
while (setP.size() < nPalette);
palette = setP.toArray(new Col[nPalette]);
Arrays.sort(palette); // Sortierung hier und in den Würfeln wichtig damit bei gleichen Abständen immer dieselbe Farbe gewählt wird
for (int i = 0; i < r; i++)
for (int j = 0; j < r; j++)
for (int k = 0; k < r; k++)
{
Set<Col> cand = new HashSet<Col>();
addCandidates((i + 0.5) * r2, (j + 0.5) * r2, (k + 0.5) * r2, cand, palette);
Col[] candA = cand.toArray(new Col[cand.size()]);
Arrays.sort(candA);
room**[j][k] = candA;
}
rand = new Random(44);
for (int i = 0; i < nSearch; i++)
search** = nextCol();
searchAll();
search3D();
}
static void searchAll()
{
debug("start All");
long check = 0;
for (Col cs : search)
{
check += nearestColor(cs, palette).hashCode();
}
debug("check: " + check);
}
static void search3D()
{
debug("start 3D");
long check = 0;
for (Col cs : search)
{
check += nearestColor(cs, room[cs.ri][cs.gi][cs.bi]).hashCode();
}
debug("check: " + check);
}
static void debug(String st)
{
System.out.println(System.currentTimeMillis() + " - " + st);
}
static Col nextCol()
{
return new Col(rand.nextInt(255), rand.nextInt(255), rand.nextInt(255));
}
static void addCandidates(double r, double g, double b, Set<Col> cand, Col[] pal)
{
Col mid = new Col((int)r, (int)g, (int)b);
int smallestError = Integer.MAX_VALUE;
int maxError = Integer.MAX_VALUE;
for (Col color2 : pal)
{
int currentError = distanceSquared(mid, color2);
if (smallestError > currentError)
{
smallestError = currentError;
maxError = smallestError + radius;
}
if (currentError < maxError)
{
cand.add(color2);
}
}
Iterator<Col> iter = cand.iterator(); // woher viele eingesammelt, nun wieder streichen was zuviel ist
while (iter.hasNext())
{
Col next = iter.next();
int currentError = distanceSquared(mid, next);
if (currentError > maxError)
{
iter.remove();
}
}
}
static Col nearestColor(Col color1, Col[] pal)
{
int smallestError = Integer.MAX_VALUE;
Col rc = null;
for (Col color2 : pal)
{
int currentError = distanceSquared(color1, color2);
if (smallestError > currentError)
{
smallestError = currentError;
rc = color2;
}
}
return rc;
}
static int distanceSquared(Col rgb1, Col rgb2)
{
int rd = rgb1.r - rgb2.r;
int gd = rgb1.g - rgb2.g;
int bd = rgb1.b - rgb2.b;
return rd * rd + gd * gd + bd * bd;
}
static class Col
implements Comparable<Col>
{
final int r;
final int g;
final int b;
final int ri;
final int gi;
final int bi;
final int hash;
public Col(int r, int g, int b)
{
this.r = r;
this.g = g;
this.b = b;
ri = r / r2;
gi = g / r2;
bi = b / r2;
final int prime = 31;
int result = 1;
result = prime * result + b;
result = prime * result + g;
result = prime * result + r;
hash = result;
}
/**
* @inheritDoc
*/
@Override
public String toString()
{
return "Col [r=" + r + ", g=" + g + ", b=" + b + "] - [ri=" + ri + ", gi=" + gi + ", bi=" + bi + "]";
}
/**
* @inheritDoc
*/
@Override
public int hashCode()
{
return hash;
}
/**
* @inheritDoc
*/
@Override
public boolean equals(Object obj)
{
if (this == obj) return true;
if (obj == null) return false;
if (getClass() != obj.getClass()) return false;
Col other = (Col)obj;
if (b != other.b) return false;
if (g != other.g) return false;
if (r != other.r) return false;
return true;
}
/**
* @inheritDoc
*/
public int compareTo(Col o)
{
int c = r - o.r;
if (c != 0) return c;
c = g - o.g;
if (c != 0) return c;
return b - o.b;
}
}
}