euklidischer Abstand

b7f7

fubar schrieb:

Ich habe zwar nicht so ganz verstanden, worum es geht, aber könntest du vielleicht inner_product und accumulate gebrauchen? Ansonsten zeig mal Code!

Oder vielleicht anstatt der euklidischen die Taxicab-/Manhattan Norm verwenden?

ich denk mal das problem ist, das sein algo O(n^2) ist. da ist dann nur die Frage ob es wirklich alle Abstände sein sollen oder ob nicht die suche nach dem kleinsten reicht.

TheTester

fubar
****

dif ist mittlerweile ein globales Array von der größe dim und es ist halt die ganz normale Berechnung.

double eucl_dist(double *x, double *mi, int dim)
{
	double dif[dim];

	int i;
	double sum=0;

	for(i=0; i<dim; ++i)
	{
		dif[i]=x[i]-mi[i];
		dif[i]*=dif[i];
		sum += dif[i];
	}

return (sqrt(sum));
}

b7f7
****

sicher suche ich den kleinsten Abstand aber dafür muss ich ja erstmal alle anderen berechnen oder? Da die Abstände nicht fix sind und sich auch mit der Zeit ändern.

bye

tt

fubar

Ich denke, so wäre es schon mal ein wenig schneller:

double eucl_dist2(double* x, double* mi, int dim) 
{
    double sum=0; 

    for(int i=0; i<dim; ++i) 
    { 
        sum += (x[i]-mi[i])*(x[i]-mi[i]); 
    } 
	return sqrt(sum); 
}

b7f7

dann braucht man aber nicht mehr den Abstand zu berechnen für Punkte deren Delta x,y oder z grösser als der bis dato berechnete minimale abstand ist.
wenn alle Punkte von pro Berechnungschritt nach zB x sortiert sind kann man immer erst testen ob der Delta x Abstand nicht grösser als minDist ist und Abbrechen. es kommt zwar der sortieraufwand dazu aber der vorteil durch das zeitige Abbrechen is doch gross.
klingt irgendwie nach Gravitationsberechnung.

volkard

TheTester schrieb:

dif ist mittlerweile ein globales Array von der größe dim und es ist halt die ganz normale Berechnung.
double eucl_dist(double *x, double *mi, int dim)
{
	double dif[dim];

	int i;
	double sum=0;

	for(i=0; i<dim; ++i)
	{
		dif[i]=x[i]-mi[i];
		dif[i]*=dif[i];
		sum += dif[i];
	}

return (sqrt(sum));
}

ohne fehler geht:

double square_of_eucl_dist(double *x, double *mi, int dim)
{
	double dif[dim];

	int i;
	double sum=0;

	for(i=0; i<dim; ++i)
	{
		dif[i]=x[i]-mi[i];
		dif[i]*=dif[i];
		sum += dif[i];
	}

return (sum);
}

als einsparen von sqrt. viele algos haben kein bauchweh, wenn sie auf den abstandsquadraten statt den abständen arbeiten (zum beispiel suche nach dem kleinsten abstand).

double square_of_eucl_dist(double *x, double *mi, int dim)
{
	double sum=0;
	for(int i=0; i<dim; ++i)
	{
		dif=x[i]-mi[i];
		dif*=dif;
		sum += dif;
	}

return (sum);
}

und dif muß gar kein array sein.

die vielen multiplikationen tun natürlich noch weh. heftige einspareungen kann man erreichen, wenn man sich erlauben kann, ein anderes abstandsmaß zu verwenden, also nicht den euglidischen abstand.

TheTester

Jupp denke schon das ich ein anderes Abstandsmaß verwenden kann, da ich wie gesagt nur die "Ähnlichkeit" benötige nichts anderes. Mal sehn welches sich anbietet.

bye

tt

fubar

Wie oben schon erwähnt dürfte die Taxicab-/Manhattan Norm etwas schneller sein

double dist(double *x, double *mi, int dim) 
{ 
	double sum=0; 

    for(int i=0; i<dim; ++i) 
    { 
        sum += fabs(x[i]-mi[i]); 
    } 
	return sum; 
}

Man könnte noch den fabs-Aufruf "wegoptimieren".

Noch schneller wäre es, wenn du die diskrete Metrik

$d(x, y)= \left\{ \begin{array}{ll} 1,\; x \ne y \\ 0,\; x = y \\ \end{array} \right.$

verwenden würdest

Jester

Wobei man beachten sollte, daß die Topologie sich damit auch rasch ändert. Wären der Übergang auf die Manhatten-Norm nur die Distanzen verzerrt, aber noch nicht die Topologie ändert greift die diskrete Norm hier gehörig zu und verändert nicht nur Längen, sondern auch Lage- und Gebietsverhältnisse.

MfG Jester

TheTester

fubar
*****

Jo die "manhatten metrik" hab ich schon so implementiert. Hab auch mal geschaut wie fabs() in Asm aussieht. Der Standard fabs() braucht 3 Operationen. Also wegoptimieren brauch man da sicher nix. Ausserdem wüsste ich jetzt nicht wie man das optimieren sollte.

Und die diskrete Metrik kann ich wirklich nicht gebrauchen ;).

bye

tt

Abbadon

Wie wärs mit der Maximums-Norm?