euklidischer Abstand



  • Hallo

    Es ist ja möglich mit dem euklidischen Abstand die Distanz zwischen 2 Vektoren zu bestimmen was auch als "Ähnlichkeit" interpretiert werden kann. Die Formel kennt ja sicher jeder. Ich habe das jetzt so "naiv" programmtechnisch umgesetzt. Jedoch dauert die Berechnung des Abstandes ziemlich lange, da ich das mehrere tausendmale durchführe, die Dimensionen der Vektoren sind nicht festgelegt. Ich habe schon optional was eingebaut um die Wurzel wegzulassen da ich den e.A. nur als Ähnlichkeitsmaß benötige.
    Gibt es eine "schnelle" Implementation dieser Berechnungsvorschrift?
    Und wie sieht es mit anderen Distanzmaßen aus die auch auf den reellen Zahlen definiert sind? Gibts "schnellere" Alternativen? Wie schon gesagt ich benötige es nur als Ähnlichkeitsmaß. 🙂

    bye

    tt



  • Dieser Thread wurde von Moderator/in Marc++us aus dem Forum Rund um die Programmierung in das Forum Mathematik verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.



  • 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?



  • 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.



  • 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



  • 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); 
    }
    


  • 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.



  • 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.



  • 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



  • 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)={1,xy0,x=yd(x, y)= \left\{ \begin{array}{ll} 1,\; x \ne y \\ 0,\; x = y \\ \end{array} \right.

    verwenden würdest 😉



  • 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



  • 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



  • Wie wärs mit der Maximums-Norm?


Log in to reply