Hallo und Willkommen im Forum.
ist zwar lange her das thema, aber ich hätte auch ne gute idee, die eventuel etwas schneller wär. vor allen da er weniger multiplikatoren (6), und keine divisionen benötigt.
Ich habe mal beide Algorithmen gegeneinander verglichen.
Hier mein Code:
Code: Alles auswählen
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
int main()
{
int points[4][2];
int hvector[3][2]; //hilfsvectoren (normalen)
int pvector[3][2]; //Punktvectoren
int scalar[3];
float vectors[3][2];
float r, s;
int notInT = 0;
srand(time(NULL));
clock_t start, end, alg1, alg2;
for(int i = 0; i < 1000; i++)
{
for(int a = 0; a < 4; a++) //Some random data
{
points[a][0] = rand() % 1000;
points[a][1] = rand() % 1000;
}
hvector[0][0] = -(points[1][1] - points[0][1]);
hvector[0][1] = points[1][0] - points[0][0];
hvector[1][0] = -(points[2][1] - points[1][1]);
hvector[1][1] = points[2][0] - points[1][0];
hvector[2][0] = -(points[0][1] - points[2][1]);
hvector[2][1] = points[0][0] - points[2][0];
for(int a = 0; a < 3; a++)
{
pvector[a][0] = points[3][0] - points[a][0];
pvector[a][1] = points[3][1] - points[a][1];
}
for(int a = 0; a < 3; a++)
{
scalar[a] = hvector[a][0] * pvector[a][0] + hvector[a][1] * pvector[a][1];
}
vectors[0][1] = points[1][1] - points[0][1];
vectors[0][0] = points[1][0] - points[0][0];
vectors[1][1] = points[2][1] - points[0][1];
vectors[1][0] = points[2][0] - points[0][0];
vectors[2][0] = points[3][0] - points[0][0];
vectors[2][1] = points[3][1] - points[0][1];
r = ((vectors[2][0] * vectors[1][1]) - (vectors[2][1] * vectors[1][0])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
s = ((vectors[2][1] * vectors[0][0]) - (vectors[2][0] * vectors[0][1])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
if (((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1) && ((r + s) <= 1)) != ((scalar[0]>0 && scalar[1]>0 && (scalar[2]>0)) || (scalar[0]<0 && scalar[1]<0 && scalar[2] < 0)))
{
cout << "Someone is wrong!" << endl << "Points: ";
for(int a = 0; a < 4; a++)
{
cout << a << ". X: " << points[a][0] << "Y: " << points[a][1] << "|";
}
cout << endl << "hvectors: ";
for(int a = 0; a < 3; a++)
{
cout << a << ". X: " << hvector[a][0] << "Y: " << hvector[a][1] << "|";
}
cout << endl << "pvectors: ";
for(int a = 0; a < 3; a++)
{
cout << a << ". X: " << pvector[a][0] << "Y: " << pvector[a][1] << "|";
}
cout << endl << "scalars: ";
for(int a = 0; a < 3; a++)
{
cout << a << " " << scalar[a] << "|";
}
cout << endl << "vectors: ";
for(int a = 0; a < 3; a++)
{
cout << a << ". X: " << vectors[a][0] << "Y: " << vectors[a][1] << "|";
}
cout << endl << "r: " << r << " s: " << s << endl;
}
}
start = clock();
for(int i = 0; i < 100000000; i++)
{
for(int a = 0; a < 4; a++) //Some random data
{
points[a][0] = rand() % 1000;
points[a][1] = rand() % 1000;
}
hvector[0][0] = -(points[1][1] - points[0][1]);
hvector[0][1] = points[1][0] - points[0][0];
hvector[1][0] = -(points[2][1] - points[1][1]);
hvector[1][1] = points[2][0] - points[1][0];
hvector[2][0] = -(points[0][1] - points[2][1]);
hvector[2][1] = points[0][0] - points[2][0];
for(int a = 0; a < 3; a++)
{
pvector[a][0] = points[3][0] - points[a][0];
pvector[a][1] = points[3][1] - points[a][1];
}
for(int a = 0; a < 3; a++)
{
scalar[a] = hvector[a][0] * pvector[a][0] + hvector[a][1] * pvector[a][1];
}
if((scalar[0]>0 && scalar[1]>0 && (scalar[2]>0)) || (scalar[0]<0 && scalar[1]<0 && scalar[2] < 0))
notInT++;
}
end = clock();
cout << end << " from " << start << "(" << end - start << ") with " << notInT << " Points" << endl;
alg1 = end - start;
notInT = 0;
start = clock();
for(int i = 0; i < 100000000; i++)
{
for(int a = 0; a < 4; a++) //Some random data
{
points[a][0] = rand() % 1000;
points[a][1] = rand() % 1000;
}
vectors[0][1] = points[1][1] - points[0][1];
vectors[0][0] = points[1][0] - points[0][0];
vectors[1][1] = points[2][1] - points[0][1];
vectors[1][0] = points[2][0] - points[0][0];
vectors[2][0] = points[3][0] - points[0][0];
vectors[2][1] = points[3][1] - points[0][1];
r = ((vectors[2][0] * vectors[1][1]) - (vectors[2][1] * vectors[1][0])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
s = ((vectors[2][1] * vectors[0][0]) - (vectors[2][0] * vectors[0][1])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
if ((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1) && ((r + s) <= 1))
notInT++;
}
end = clock();
cout << end << " from " << start << "(" << end - start << ") with " << notInT << " Points" << endl;
alg2 = end - start;
cout << "Alg1: " << alg1 << " to Alg2:" << alg2 << " with " << (float)((alg2 - alg1) / (float)(alg1)) * 100.0f << "% diff";
return 0;
}
Bei 100.000.000 Durchläufen mit Zufälligen Daten mit den Standardeinstellungen vom Qt Designer komme ich auf folgende Ergebnisse:
Code: Alles auswählen
16800000 from 0(16800000) with 7641610 Points
34260000 from 16800000(17460000) with 7641423 Points
Alg1: 16800000 to Alg2:17460000 with 3.92857% diff
Mit g++ direkt und O3 auf:
Code: Alles auswählen
15550000 from 0(15550000) with 7639944 Points
33030000 from 15550000(17480000) with 7641594 Points
Alg1: 15550000 to Alg2:17480000 with 12.4116% diff
Dein Code ist also um 3,92% schneller in einer realen Anwendung, 12,4% mit Optimierungen, benötigst aber deutlich mehr Variablen und es muss noch bewiesen werden, damit auch garantiert ist, das für alle Kombinationen dieser Algorithmus richtig ist. Nicht schlecht.
insgesamt bruach man
-9 additionen oder subtraktionen(1 takt)
-3 negationen(1takt)
-6 multiplikatoren(glaube bis 32 takte bei 32 bit zahlen)
-keine division(die soweit ich weis länger braucht als eine multiplikation)
-keine sin cos oder tan funtionen
-3 oder 6 prüfungen
Hier stößt du an das Problem, das Code und Programm keinen 1:1 Zusammenhang haben. Dein Compiler Optimiert deinen Code und passt ihn auf Architekturen an, bzw man kann es auch direkt für bestimmte Prozessoren optimieren und Performance aus speziellen Prozessoroperaionen ziehen.
Aber das kannst du nicht anhand von Code bewerten.
Das merkt man sehr deutlich, wenn man viele unterschiedliche Implementierungen vergleicht:
http://www.proggen.org/doku.php?id=project:wordcount
http://www.proggen.org/forum/viewtopic.php?f=49&t=4872
Edit: Die Werte waren ja noch mit Zufallszahlen. Ohne wird das ganze mit 03 alles Wegoptimiert und von Qt erhält man das:
Code: Alles auswählen
5270000 from 0(5270000) with 0 Points
7650000 from 5270000(2380000) with 0 Points
Alg1: 5270000 to Alg2:2380000 with -54.8387% diff
Wobei hier wieder die Frage ist, wie der Compiler hier Optimiert.
Man merkt, es ist nicht so einfach eine Qualitative Analyse von Quellcode zu erstellen.