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

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

21

28.01.2008, 23:00

OK, dann ist es wohl tatsächlich O(n²).
Nur dürften solche Extremfälle in zufälligen Daten äußerst selten vorkommen.
David Scherfgens Website | Konzentrationstest Polizei

grek40

Alter Hase

Beiträge: 1 491

Wohnort: Dresden

  • Private Nachricht senden

22

28.01.2008, 23:16

Sie sollten aber fairerweise in einem Test auch berücksichtigt werden, sonst werden die Teilnehmer zu sehr bevorzugt, die ihren Algo auf 'nette' Daten aufbauen :)

Florianx

Frischling

Beiträge: 49

  • Private Nachricht senden

23

28.01.2008, 23:45

So ich hab nun auch endlich einen funktionierenden Code :)

Allerding eine simple Näherungslösung, wobei ich große Probleme mit der Genauigkeit hab, wenn der Code in angemessener Geschwindigkeit laufen soll. Damit könnte ich höchstens bei der Anzahl der Token gewinnen :/

Aber ich hab mich jetzt auch mal an eine exakte Lösung rangehockt, wobei das schon an die Grenzen meiner Mathekenntnisse geht, und das dann auch noch in Code umzusetzten ist gar net so einfach. Aber ich glaub, ich könnte es schaffen, ohne ein Einziges Integral wirklich zu lösen :)

otze

Frischling

Beiträge: 62

  • Private Nachricht senden

24

04.02.2008, 11:58

Ich hab mich mal an die Analytische Lösung rangetraut, und irgendwie ist das ganze sehr ekelhaft...nen schönheitswettbewerb wird mein Code sicher nicht gewinnen ;)

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

25

04.02.2008, 12:33

Funktioniert sie denn?
Morgen schreibe ich meine vorerst letzte Klausur. Dann werde ich mich auch mal an die Arbeit machen.
David Scherfgens Website | Konzentrationstest Polizei

rklaffehn

Treue Seele

Beiträge: 267

Wohnort: Braunschweig

  • Private Nachricht senden

26

04.02.2008, 18:18

Hier mal die drei großen Testfälle, mit denen ich so rumexperimentiere:

C-/C++-Quelltext

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

  TestCase tc_concentric_shrink;
  for (int c = 0; c < 10000; ++c)
    tc_concentric_shrink.circles.push_back (Circle (0.0, 0.0, MAX_RADIUS - double (c) * MAX_RADIUS / 10000.0));
  tc_concentric_shrink.correct_result = PI * 1.0e-4;

  test_cases.push_back (tc_concentric_shrink);

  TestCase tc_concentric_grow;
  for (int c = 1; c <= 10000; ++c)
    tc_concentric_grow.circles.push_back (Circle (0.0, 0.0, double (c) * MAX_RADIUS / 10000.0));
  tc_concentric_grow.correct_result = PI * 1.0e-4;

  test_cases.push_back (tc_concentric_grow);

  TestCase all_intersect;
  for (int c = 0; c < 10000; ++c)
    all_intersect.circles.push_back (Circle (-50.0 * std::cos (double (c) * 2.0 * PI / 10000.0),
                                              50.0 * std::sin (double (c) * 2.0 * PI / 10000.0), 100.0));
  all_intersect.correct_result = PI * 2500.0;

  test_cases.push_back (all_intersect);


Das Ergebnis für den dritten Fall ist allerdings nur eine Schätzung, wenn auch eine recht Gute. :) Die tatsächliche Fläche müsste minimal größer sein.

Zeiten sage ich im Sinne der Spannung mal nicht, nur soviel: mein Algorithmus rechnet am dritten Fall sehr deutlich länger als an den ersten beiden, weil mich da O(n²) voll erwischt.
God is real... unless declared integer.
http://www.boincstats.com/signature/user_967277_banner.gif

S.Seegel

2x Contest-Sieger

Beiträge: 95

  • Private Nachricht senden

27

04.02.2008, 19:06

Meine analytische - also zumindest theoretisch exakte - Lösung liefert mir für den dritten Testfall genau deinen Schätzwert. Das "etwas" - um das die tatsächliche Lösung größer sein sollte - liegt also jenseits der Genauigkeit von double ;)

Quellcode

 
1
2
3

Ergebnis: 0.000314159    Korrekter Wert: 0.000314159    OK!
Ergebnis: 0.000314159    Korrekter Wert: 0.000314159    OK!
Ergebnis: 7853.98        Korrekter Wert: 7853.98        OK!


Die ersten beiden Testfälle fallen bei meiner Lösung unter O(n), beim dritten schlägt dann ebenfalls O(n²) voll zu.

PS: wenn jemand zu weiteren Testfällen die - meiner Lösung nach (!) - exakten Schnittflächen wissen möchte, immer her damit. Natürlich ohne Gewähr ;)

rootnode

Frischling

Beiträge: 92

Wohnort: Aachen, Pontstraße

Beruf: Student

  • Private Nachricht senden

28

04.02.2008, 21:20

Ok, um die Spannung mal etwas anzureiben.

Habe mal die Testcases von Klaffehn hinzugefügt:


Quellcode

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

Ergebnis: 0              Korrekter Wert: 0              OK!
Ergebnis: 0.785023       Korrekter Wert: 0.785398       OK!
Ergebnis: 0              Korrekter Wert: 0              OK!
Ergebnis: 0.196256       Korrekter Wert: 0.19635        OK!
Ergebnis: 1.2284         Korrekter Wert: 1.22837        OK!
Ergebnis: 0.196256       Korrekter Wert: 0.19635        OK!
Ergebnis: 31.5154        Korrekter Wert: 31.5147        OK!
Ergebnis: 0.000314009    Korrekter Wert: 0.000314159    OK!
Ergebnis: 31400.9        Korrekter Wert: 31415.9        OK!
Ergebnis: 0              Korrekter Wert: 0              OK!
Ergebnis: 0.000314009    Korrekter Wert: 0.000314159    OK!
Ergebnis: 0.000314009    Korrekter Wert: 0.000314159    OK!
Ergebnis: 7850.23        Korrekter Wert: 7853.98        OK!

real    0m0.148s
user    0m0.140s
sys 0m0.008s
http://www.ohloh.net/p/mosa-project/widgets/project_partner_badge.gif

CodingCat

1x Contest-Sieger

Beiträge: 420

Beruf: Student (KIT)

  • Private Nachricht senden

29

05.02.2008, 11:06

Hm, auch ich habe O(n), allerdings lässt sich mein konstanter Faktor (ca. 3000) nicht mehr allzu weit reduzieren - muss ich mir wohl nochmal Gedanken zum Ansatz machen:

Quellcode

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

Ergebnis: 0              Korrekter Wert: 0              Zeit: 0      OK!
Ergebnis: 0.785112       Korrekter Wert: 0.785398       Zeit: 0      OK!
Ergebnis: 0              Korrekter Wert: 0              Zeit: 0      OK!
Ergebnis: 0.196278       Korrekter Wert: 0.19635        Zeit: 0      OK!
Ergebnis: 1.22808        Korrekter Wert: 1.22837        Zeit: 0      OK!
Ergebnis: 0.196278       Korrekter Wert: 0.19635        Zeit: 0.001  OK!
Ergebnis: 31.4994        Korrekter Wert: 31.5147        Zeit: 0      OK!
Ergebnis: 0.000314045    Korrekter Wert: 0.000314159    Zeit: 0      OK!
Ergebnis: 31404.5        Korrekter Wert: 31415.9        Zeit: 0      OK!
Ergebnis: 0              Korrekter Wert: 0              Zeit: 0      OK!
Ergebnis: 0.000314045    Korrekter Wert: 0.000314159    Zeit: 0.251  OK!
Ergebnis: 0.000314045    Korrekter Wert: 0.000314159    Zeit: 0.251  OK!
Ergebnis: 7851.12        Korrekter Wert: 7853.98        Zeit: 0.358  OK!
Ergebnis: 4611.79        Korrekter Wert: 4613.8         Zeit: 0.25   OK!

CodingCat

1x Contest-Sieger

Beiträge: 420

Beruf: Student (KIT)

  • Private Nachricht senden

30

05.02.2008, 13:15

So, ich konnte meinen konstanten Faktor nun doch um ein Vielfaches reduzieren, dann will ich das ganze auch nochmal spannend machen (die letzten drei sind ebenfalls rklaffehns Testcases). ;-)

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.22847        Korrekter Wert: 1.22837        Zeit: 0      OK!
Ergebnis: 0.19635        Korrekter Wert: 0.19635        Zeit: 0      OK!
Ergebnis: 31.5285        Korrekter Wert: 31.5147        Zeit: 0      OK!
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.000314159    Korrekter Wert: 0.000314159    Zeit: 0.006  OK!
Ergebnis: 0.000314159    Korrekter Wert: 0.000314159    Zeit: 0.007  OK!
Ergebnis: 7853.98        Korrekter Wert: 7853.98        Zeit: 0.009  OK!

Gesamtzeit: 0.059


Noch vier nette Worst Case Szenarien, die bei mir nicht auf Anhieb funktionierten:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// zwei Kreise, die sich mandelförmig schneiden (Worst Case)

TestCase tc12; 
tc12.circles.push_back(Circle(0.0, 0.0, 1.0)); 
tc12.circles.push_back(Circle(1.9982213, 0.0, 1.0)); 
tc12.correct_result = 0.000100008;
test_cases.push_back(tc12);

// zwei sehr unterschiedlich große Kreise, die sich mandelförmig schneiden (Worst Case)

TestCase tc13; 
tc13.circles.push_back(Circle(-100.0, 0.0, 100.0)); 
tc13.circles.push_back(Circle(0.0, 0.0, 0.01)); 
tc13.correct_result = 0.000157076;
test_cases.push_back(tc13);

// zwei sehr sehr unterschiedlich große Kreise, die sich mandelförmig schneiden (Worst Case)

TestCase tc14; 
tc14.circles.push_back(Circle(-100.0, 0.0, 100.0)); 
tc14.circles.push_back(Circle(-0.005, 0.0, 0.01)); 
tc14.correct_result = 0.000252739;
test_cases.push_back(tc14); 

// zwei sehr sehr große Kreise, die sich mandelförmig schneiden (Worst Case)

TestCase tc15; 
tc15.circles.push_back(Circle(-99.999799999, 0.0, 100.0)); 
tc15.circles.push_back(Circle(99.999799999, 0.0, 100.0)); 
tc15.correct_result = 0.000106667;
test_cases.push_back(tc15);


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.

Werbeanzeige