Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

#03: "Kreisschnitt", Geschwindigkeit, 17.02.2008

Werbeanzeige

S.Seegel

2x Contest-Sieger

Beiträge: 95

  • Private Nachricht senden

31

05.02.2008, 17:53

Zitat von »"CodingCat"«

Wie genau das Referenzergebnis ist, kann ich allerdings nicht sagen, sollte aber recht gut hinkommen - könnte ja vielleicht mal jemand mit nem analytischen Ansatz checken.

Aber gerne :

Quellcode

 
1
2

Ergebnis: 0.000100008    Korrekter Wert: 0.000100008    OK!
Ergebnis: 0.000157076    Korrekter Wert: 0.000157076    OK!

Wie es scheint stimme ich 100%ig mit dir überein :)
Hast du deine Referenzlösungen mit Papier und Bleistift bestimmt oder ist das deine Näherung ?

CodingCat

1x Contest-Sieger

Beiträge: 420

Beruf: Student (KIT)

  • Private Nachricht senden

32

05.02.2008, 17:56

Das sind Näherungen, allerdings mit einer ziemlich hohen Auflösung (auf dem Heap - der Stack hat nicht mehr gereicht ;-)). Hab noch 2 Testszenarien hinzugefügt, ich denke die Lösungen sollten recht gut hinkommen, wenn die ersten beiden gestimmt haben. :-)

S.Seegel

2x Contest-Sieger

Beiträge: 95

  • Private Nachricht senden

33

05.02.2008, 18:07

Auch deine weiteren beiden Testfälle kann ich so bestätigen.

Für analytische Ansätze sehe ich in der alles entscheidenden Kategorie Performance keine Chance. Hab meine Lösung zwar mangels Zeit noch keinen Strich optimiert, aber mehrere Größenordnungen an Geschwindigkeit werde ich kaum raus holen können :?

Florianx

Frischling

Beiträge: 49

  • Private Nachricht senden

34

05.02.2008, 20:39

So siehst bei mir im mom aus:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Ergebnis: 0                     Korrekter Wert: 0                    Zeit: 0    OK!
Ergebnis: 0.785398         Korrekter Wert: 0.785398         Zeit: 0    OK!
Ergebnis: 0                     Korrekter Wert: 0                    Zeit: 0    OK!
Ergebnis: 0.19635           Korrekter Wert: 0.19635           Zeit: 0    OK!
Ergebnis: 1.22837           Korrekter Wert: 1.22837           Zeit: 0    OK!
Ergebnis: -77.5012          Korrekter Wert: 0.19635           Zeit: 0    Fehler!
Ergebnis: 39.9583           Korrekter Wert: 31.5147           Zeit: 0    Fehler!
Ergebnis: 0.000314159    Korrekter Wert: 0.000314159    Zeit: 0    OK!
Ergebnis: 31415.9           Korrekter Wert: 31415.9           Zeit: 0    OK!
Ergebnis: 0                     Korrekter Wert: 0                     Zeit: 0    OK!
Ergebnis: 0.000100008    Korrekter Wert: 0.000100008    Zeit: 0    OK!
Ergebnis: 0.000157076    Korrekter Wert: 0.000157076    Zeit: 0    OK!
Ergebnis: 0.000252739    Korrekter Wert: 0.000252739    Zeit: 0    OK!
Ergebnis: 0.000106667    Korrekter Wert: 0.000106667    Zeit: 0    OK!
Gesamt-Zeit: 0


So bestimm ich die Zeit:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

double total_seconds = time();

for(std::vector<TestCase>::const_iterator it = test_cases.begin();
    it != test_cases.end();
    ++it)
{
    double seconds = time();
    const double result = my_intersection(it->circles);
    seconds = time() - seconds;
    const bool ok = is_ok(result, it->correct_result);

    std::cout << "Ergebnis: " << std::setw(15) << result;
    std::cout << "Korrekter Wert: " << std::setw(15) << it->correct_result;
    std::cout << "Zeit: " << std::setw(5) << seconds;
    std::cout << (ok ? "OK!" : "Fehler!") << std::endl;
}

total_seconds = time() - total_seconds;
std::cout << "Gesamt-Zeit: " << std::setw(5) << total_seconds;


Bei der gesamt Zeit sind die 4 worst-case Szenarien auch dabei.

Ich versuch mich übrigens in einer exakten Lösung.
Wenn ich die letzten Bugs jetzt noch finde würde wäre alles super ;)
Optimiert hab ich auch noch nix.

CodingCat

1x Contest-Sieger

Beiträge: 420

Beruf: Student (KIT)

  • Private Nachricht senden

35

05.02.2008, 21:30

Meine 4 Worst Case Szenarien waren auch zur Überprüfung der Korrektheit gedacht, von der Geschwindigkeit her sind sie nicht besonders fordernd. Ansonsten sind deine Zeiten natürlich traumhaft - allerdings solltest du auch mal die 3 Fälle von rklaffehn à 10.000 Kreisen testen, denn innerhalb von 0,000 s die exakte Lösung von so vielen Kreisen zu bestimmen, ist schwer vorstellbar. ;-)

Florianx

Frischling

Beiträge: 49

  • Private Nachricht senden

36

05.02.2008, 22:09

ups, die hab ich ganz übersehn.
die ersten beiden Schaff ich in 0.01, wobei in den Fällen sogar noch optimieren könnte.
Beim letzten siehts dann net mehr ganz so gut aus, denn da bekomm ich gar kein Ergebnis (NAN). Sind halt noch einige Bugs in meinem Frickelwerk :D
Dauern tut das ganze im mom ein paar sec, aber ka, ob mein Prog überhaupt ansatzweise das richtige rechnet.
Hab z.B. grad erst wieder beim Debuggen ein Fall gefunden, den ich gar net behandelt hab und der auch gar so simpel ist.
Naja, mal schaun ob es überhaupt mal fehlerfrei läuft.:?

otze

Frischling

Beiträge: 62

  • Private Nachricht senden

37

06.02.2008, 10:18

Zitat von »"David Scherfgen"«

Funktioniert sie denn?
Morgen schreibe ich meine vorerst letzte Klausur. Dann werde ich mich auch mal an die Arbeit machen.

Nun, zumindest der letzte Schritt, die berechnung der eigentlichen Fläche funktioniert jetzt ;). Die ganzen vorberechnungen muss ich noch schreiben, hab im moment leider auch nicht soviel zeit :(


//edit was ist eigentlich mit dem Fall, dass sich 2 Kreise nur berühren? müssen wir den auch abfangen? in den testcases ist der Fall nicht vorhanden.

S.Seegel

2x Contest-Sieger

Beiträge: 95

  • Private Nachricht senden

38

06.02.2008, 12:20

Zitat von »"otze"«

was ist eigentlich mit dem Fall, dass sich 2 Kreise nur berühren? müssen wir den auch abfangen? in den testcases ist der Fall nicht vorhanden.

Zwei Kreise, die sich lediglich berühren, haben keine Schnittfläche, da ein Punkt per Definition keine räumliche Ausdehnung hat. Damit fällt eine Berührung in die Kategorie "kein Schnitt", das korrekte Ergebnis ist folglich 0.

Deviloper

Community-Fossil

Beiträge: 2 872

  • Private Nachricht senden

39

06.02.2008, 14:12

Nja werd meins auch mal optimieren ;) Hab imo beliebige Genauigkeit, weil ich nen Rechteck um den kleinsten Kreis gespannt hab und dann von links nach Rechts in (per Parameter übergebenen) Schritten durchgehe ... extrem lahm :D Naja was solls ;) Muss mir mal was anderes einfallen lassen ;)
Devil Entertainment :: Your education is our inspiration
Der Spieleprogrammierer :: Community Magazin
Merlin - A Legend awakes :: You are a dedicated C++ (DirectX) programmer and you have ability to work in a team? Contact us!
Siedler II.5 RttR :: The old settlers-style is comming back!

Also known as (D)Evil

Helmut

5x Contest-Sieger

Beiträge: 692

Wohnort: Bielefeld

  • Private Nachricht senden

40

06.02.2008, 21:40

Wobei wir vielleicht noch nicht darüber diskutieren sollten, wie ein möglicher Algo aussehen könnte ;)
Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

Werbeanzeige