Kleiner Programmierwettbewerb

[TomasRiker]

Hallo!

Auf meiner Seite veranstalte ich seit einiger Zeit kleine Programmierwettbewerbe (Sprache: C++). Die Aufgaben sind meistens sehr schnell und leicht zu lösen. Je nach Aufgabe geht es um Geschwindigkeit, Kürze des Codes (Token-Count) oder sonstige Kriterien.

Den aktuellen Wettbewerb (schon der 9.), der noch bis zum 12. Oktober läuft, findet ihr hier.

Über zusätzliche Teilnehmer freue ich mich immer, denn je mehr Leute mitmachen, desto spannender ist das Ganze natürlich.

[flashpixx]

Nette Sache, aber es ich würde hier die entsprechenden Beschleunigungsstrukturen aus der Computergraphik (kd-Tree, Octree, Cohen-Sutherland) verwenden. Zum dem Rechteckproblem würde man hier wohl am sinnvollsten das Clipping nach Cohen-Sutherland verwenden, um damit zu prüfen, ob man das Rechteck bearbeiten muss, oder nicht. Siehe hierzu auch den fertigen Code: Algorithmus von Cohen-Sutherland ? Wikipedia

Außerdem kann man nicht einen Algorithmus nach der Geschwindigkeit in einer bestimmten Programmiersprache messen, sondern muss die Komplexität für den Algorithmus bestimmen. Nur weil etwas "schnell" läuft, heißt es noch lange nicht, dass es gut ist.

HTH Phil

[TomasRiker]

Genau, sowas Ähnliches habe ich auch vor (Quadtree).

Natürlich sollte ein Algorithmus anhand seiner Komplexität (Zeit, Speicher) bewertet werden, aber das wäre sehr kompliziert. Dazu müsste ich mir jede Einsendung genau per Hand ansehen und "beweisen", welche Komplexität sie hat. Darum mache ich die Auswertung eben so, dass jeder Algorithmus eine Reihe von Tests durchlaufen muss, wobei dann Punkte anhand der benötigten Zeit vergeben werden.

Würde mich freuen, wenn du mitmachst!

[xk4fu]

Genau, sowas Ähnliches habe ich auch vor (Quadtree).

Natürlich sollte ein Algorithmus anhand seiner Komplexität (Zeit, Speicher) bewertet werden, aber das wäre sehr kompliziert. Dazu müsste ich mir jede Einsendung genau per Hand ansehen und "beweisen", welche Komplexität sie hat. Darum mache ich die Auswertung eben so, dass jeder Algorithmus eine Reihe von Tests durchlaufen muss, wobei dann Punkte anhand der benötigten Zeit vergeben werden.

Würde mich freuen, wenn du mitmachst!

die komplexität eines algorithmus wird ganz einfach über die O-Notation bestimmt...

[Klotzkopp]

die komplexität eines algorithmus wird ganz einfach über die O-Notation bestimmt...

Und du kannst das "ganz einfach" aus dem Code ablesen, oder woher nimmst du die Information?

[xk4fu]

ja, kann ich

ein bubblesort hat z.b. O(n²)

es gibt hier zwei for schleifen, die jeweils n bzw. n-1 mal durchlaufen werden

zuweisungen usw kann man außer acht lassen

somit ist z.b. der bubblesort nicht wirklich schnell

O(n*log(n)) Sorts sollten dem z.b. immer vorgezogen werden

[Klotzkopp]

ja, kann ich

Bei einem trivialen Algorithmus wie Bubblesort könntest du das vielleicht auf einen Blick sehen. Aber mal ehrlich, könntest du einem Quicksort ansehen, welche Komplexität er hat, oder hast du das vielleicht doch nur auswendig gelernt?

Aus einem beliebig komplexen Stück Code zu ermitteln, welche Laufzeitkomplexität er hat, ist nicht "ganz einfach". Die O-Notation fällt nicht vom Himmel.

[xk4fu]

mit "ganz einfach" habe ich eigentlich gemeint, dass man - entsprechendes know how vorausgesetzt - den code zeile für zeile durchgeht und die komplexität anhand der O-Notation bestimmt;

TomasRiker stellt sich das mit seinem Beweis und seiner Bewertung glaube ich komlizierter vor als es ist

[TomasRiker]

mit "ganz einfach" habe ich eigentlich gemeint, dass man - entsprechendes know how vorausgesetzt - den code zeile für zeile durchgeht und die komplexität anhand der O-Notation bestimmt;

TomasRiker stellt sich das mit seinem Beweis und seiner Bewertung glaube ich komlizierter vor als es ist

Und ich glaube, du stellst es dir zu einfach vor.

Die Laufzeit der Rechteck-Algorithmen hängt grundsätzlich schonmal von zwei Variablen ab: der Bildgröße und der Anzahl der Rechtecke. Und das sind nicht einfach nur ein paar Schleifen, wo du direkt siehst, wie oft sie durchlaufen. Da wird mit Bäumen gearbeitet, und je nach dem, welche Rechtecke bereits gezeichnet wurden, werden nachfolgende Rechtecke komplett übersprungen etc..

Die Worst Case-Laufzeit könnte man vielleicht noch ermitteln, aber was sagt die schon? Interessanter ist die Average Case-Laufzeit. Dazu müsstest du die Zufallsverteilung der Rechtecke berücksichtigen.

Ich wage mal zu behaupten, dass das nahezu unschaffbar ist. Und das dann noch für jede einzelne Einsendung machen und dokumentieren, so dass es nachvollziehbar ist? Nur um dann eine theoretische Aussage zu haben, die in der Praxis möglicherweise bedeutungslos ist? Und dann gewinnt am Ende ein O(n * log(n))-Algorithmus vor einem O(n²), obwohl er erst für astronomisch große Zahlen von n (die nie erreicht werden) schneller läuft? Nein danke ...

[TomasRiker]

Ach, und noch ein Problem.

Nehmen wir an, die Komplexität hängt von N und M ab (Anzahl der Rechtecke und Bildgröße).

Welcher Algorithmus von den Folgenden ist nun nach deinem System der "beste"?

O(N² * M)

O(N * M²)

O(log N + M³)

...

Aber wenn du für all dies eine Lösung hast und per göttlicher Einsicht mit einem Blick die Komplexität jedes Codestücks bestimmen kannst, darfst du die Auswertung gerne übernehmen.

[xk4fu]

bei der o notation gibt es kein n, m, usw...

es gibt nur eine konstante n

z.b. mal wieder der bubblesort

man hat ja zwei schleifen mit unterschiedlichen variablen

die erste schleife wird n mal durchlaufen

die zweite n * n, da die zweite selbst n mal durchlaufen wird und das n mal (durch die erste)

ich weis nicht auf was du diese aussage beziehst:

O(N² * M) <----- M?????

O(N * M²) <----- M²????

O(log N + M³) <-- M³????

auf unwissenheit oder ignoranz?

von göttlicher eingebung kann hier auf jedenfall nicht gesprochen werden

klar kann man die o notation nicht immer verwenden, aber bevor man sie nicht kennt, sollte man nicht ein unqualifiziertes urteil darüber geben!

[flashpixx]

Als Beispiel: Bei einem kd-Tree kannst Du nicht vorausberechnen, wie viele Schnitte er tatsächlich benötigt. Dies wird heuristisch abgeschätzt. Ich kann natürlich mein Beispiel so wählen, dass eine gute / schlechte Lösung heraus kommt. Durchaus kann man für ein gegebenes Problem durch einen anderen Algorithmus z.b. BVH eine bessere Lösung erreichen, analog dazu um 3 Elemente zu sortieren, ist es sinnvollere die mit If-The-Else zu prüfen, als einen Quicksort der durch den rekursiven Aufruf Heap usw verbraucht.

Zu Deiner Aussage, dass es abhängig von Anzahl der Rechecke / Bildgröße ist, das ist irrelevant, denn es sind konstante Faktoren. Es geht bei der Bestimmung der Komplexität um eine Schranke (O, Theta, Omega) ab einem gewissen n0. Es kann sein, dass der eine oder andere Algorithmus für einen wert < n0 bessere Ergebnisse liefert. Aber Du möchtest eine Aussage über die Güte treffen, damit ist dieser Bereich (< n0) nicht relevant. Außerdem betrachtet man die einzelnen Kosten des Codes mit einem Maß z.B. eine Varibablenzuweisung ist immer mit +1 zu sehen usw.

Du möchtest die Average-Zeit haben und diese bestimmst Du anhand des gegebenen Beispiels. Die Aussage, die Du gewinnst hat überhaupt kein Maß, denn nehme ich ein anderes Beispiel, sieht das Ergebnis auch anders aus. Im Grunde kann ich die Lösung "hart" codieren und damit erschlage ich jeden Algorithmus, da ich sie ein einziges mal voraus berechne.

Wenn Du eine Aussage über die Güte des Algorithmus treffen willst, dann musst Du sehr viele verschiedene Beispiel nehmen und die Ergebnisse im Mittel betrachten (im Grunde einen Grenzwertprozess) und dies wäre dann eine Komplexitätsanalyse

Phil

[TomasRiker]

bei der o notation gibt es kein n, m, usw...

es gibt nur eine konstante n

So ein Unfug.

Erstens ist n keine Konstante, dann wäre es ja witzlos. n ist eine Variable.

Zweitens ist die O-Notation nicht auf eine einzige Variable beschränkt. Zum Beispiel ein Algorithmus zum Suchen eines Strings in einem anderen String: Boyer-Moore-Algorithmus

Seine Komplexität ist O(n+m), wobei das eine die Länge des gesuchten Strings und das andere die Länge des durchsuchten Strings ist.

klar kann man die o notation nicht immer verwenden, aber bevor man sie nicht kennt, sollte man nicht ein unqualifiziertes urteil darüber geben!

Ich kenne die O-Notation sehr wohl, schließlich lernt man sie schon in den ersten Semestern jedes Informatikstudiums. Du hingegen scheinst sie nicht verstanden zu haben, wenn man sich deine Aussagen oben durchliest.

Bearbeitet 15. September 2008 von TomasRiker

[TomasRiker]

Zu Deiner Aussage, dass es abhängig von Anzahl der Rechecke / Bildgröße ist, das ist irrelevant, denn es sind konstante Faktoren.

Da hast du mich wohl falsch verstanden.

Angenommen man schafft es tatsächlich, die mittlere Laufzeit eines Algorithmus zu bestimmen. Sagen wir mal, der eine Algorithmus liegt in O(n * m²), wobei n die Anzahl der Rechtecke und m die Bildgröße ist. Ein anderer Algorithmus liegt nun in O(n² * m), weil er komplett anders vorgeht (ist nur ein Beispiel!). Wie willst du nun entscheiden, welcher davon besser ist? Hängt es nur von einer Variablen ab, dann ist es klar, denn O(n) ist z.B. "besser" als O(n²). Aber bei mehreren Variablen?

Mal abgesehen davon ist die Frage einfach nur: wer schafft es mit seinem Algorithmus, eine Reihe zufälliger Tests am schnellsten abzuarbeiten? Dass das nicht unbedingt die perfekte Art der Bewertung ist (sie lässt Komplexität und Speicherverbrauch außer Acht), ist mir klar. Ich veranstalte diesen Wettbewerb in der Freizeit und habe keine Lust, wochenlang Algorithmen auseinanderzunehmen und theoretisch zu ermitteln, wie lange sie im Durchschnitt brauchen.

Vergleichen wir es mal mit einem Fußballspiel: am Ende gewinnt die Mannschaft, die mehr Tore geschossen hat. Das ist mein Ansatz. Du hingegen würdest jeden Spieler analysieren und seine Technik, Ausdauer usw. bewerten (aber wie?) und dann bestimmen, wer theoretisch gewinnen müsste.

Bearbeitet 15. September 2008 von TomasRiker

[flashpixx]

Angenommen man schafft es tatsächlich, die mittlere Laufzeit eines Algorithmus zu bestimmen. Sagen wir mal, der eine Algorithmus liegt in O(n * m²), wobei n die Anzahl der Rechtecke und m die Bildgröße ist. Ein anderer Algorithmus liegt nun in O(n² * m), weil er komplett anders vorgeht. Wie willst du nun entscheiden, welcher davon besser ist? Hängt es nur von einer Variablen ab, dann ist es klar, denn O(n) ist z.B. "besser" als O(n²). Aber bei mehreren Variablen?

Du hast hier gedanklich konkrete Werte für n und m angenommen. Die Komplexitätsklassen sind nicht wie Du annimmst eine Schranke, sondern eine obere Schranke: siehe hierzu Erk & Priese - Theoretische Informatik - Kapitel 15.1

"Das O-Kalkül wird in der Informatik benutzt, um abzuschätzen, wieviel Zeit ein Algorithmus schlimmstenfalls braucht. Man gibt diese Zeit an in Abhängigkeit von der Größe des Eingabewertes des Algorithmus. Einfach die Laufzeit auf einem bestimmten Rechner zu messen, ist nicht sehr aufschlussreich: Ein anderer Rechner kann viel länger oder kürzer brauchen. Um eine rechnerunabhängige Meßzahl zu haben, betrachtet man die Anzahl der Schritte, die ein Algorithmus ausführt..."

Du sagst, dass Du die Laufzeit auf 2 Testsystemen ermittelst. Dir kann es passieren, dass Du widersprüchliche Ergebnisse bekommst, damit hast Du keine Aussage bezüglich des Programms.

Mal abgesehen davon ist die Frage einfach nur: wer schafft es mit seinem Algorithmus, eine Reihe zufälliger Tests am schnellsten abzuarbeiten?

Du hast Dir zufällige Test ausgedacht, ich hoffe, dass die Eingaben iid sind.

Dass das nicht unbedingt die perfekte Art der Bewertung ist (sie lässt Komplexität und Speicherverbrauch außer Acht), ist mir klar.

Eben, N/D TIME/SPACE und dass gilt NSPACE(s(n)) Teilmenge von DTIME(2^s(n)) (Satz von Savitch) mit s(n) >= n (s totale Fkt von N => N)

Ich veranstalte diesen Wettbewerb in der Freizeit und habe keine Lust, wochenlang Algorithmen auseinanderzunehmen und theoretisch zu ermitteln, wie lange sie im Durchschnitt brauchen.

Unter den Umständen ist die Aussage, die als Ergebnis des "Wettbewerbes" heraus kommt, überhaupt nicht verwertbar, denn sie sagt nichts über die Güte des Algorithmus aus

Phil

P.S.: trotzdem gute Diskussion

[TomasRiker]

Du hast hier gedanklich konkrete Werte für n und m angenommen. (...)

Nein, mir ist schon klar, dass wir einen Grenzwert betrachten.

Du wirst mir doch zustimmen, dass die Laufzeit eines Algorithmus hier von der Anzahl der Rechtecke und von der Bildgröße abhängt, also von zwei Eingabegrößen. Damit hätten wir sowas wie O(n*m²) und O(n²*m), sind wie gesagt nur Beispiele.

Nun kannst du nicht sagen, was davon besser ist, oder?

Die Laufzeit des einen Algorithmus wächst quadratisch mit der Anzahl der Rechtecke und linear mit der Bildgröße, der andere linear mit der Anzahl der Rechtecke und quadratisch mit der Bildgröße.

Das ist vergleichbar mit Raytracing und Rasterizing. Was davon ist "besser" (also was davon sollte einen Contest gewinnen)?

Du sagst, dass Du die Laufzeit auf 2 Testsystemen ermittelst. Dir kann es passieren, dass Du widersprüchliche Ergebnisse bekommst, damit hast Du keine Aussage bezüglich des Programms.

Ja, kann (und wird) passieren. Was ich davon habe? Damit versuche ich, den Einfluss der verschiedenen Rechnerarchitekturen auf das Ergebnis zumindest etwas zu reduzieren.

Unter den Umständen ist die Aussage, die als Ergebnis des "Wettbewerbes" heraus kommt, überhaupt nicht verwertbar, denn sie sagt nichts über die Güte des Algorithmus aus

Wie du sicher schon gesehen hast, sind wir Spieleentwickler. Von daher hat der Contest auch eine Art "dirty hacking"-Charakter. In Computerspielen muss man die Hardware voll ausreizen, Performance ist sehr wichtig. Was zählt ist, wie schnell das Spiel läuft. Den Spieler interessiert es nicht, welche Komplexität der verwendete Algorithmus hat, sondern dass er das Spiel flüssig spielen kann.

Die von dir zitierte Aussage kann man durchaus auch umdrehen: die Komplexität eines Algorithmus sagt nichts darüber aus, wie lange er tatsächlich braucht (und das ist es, was mich interessiert). In der O-Betrachtung gehen wir von Grenzwerten aus (n geht gegen unendlich). Hier haben wir es aber mit realen Daten zu tun, und da geht nichts gegen unendlich.

Bearbeitet 15. September 2008 von TomasRiker

[flashpixx]

In Computerspielen muss man die Hardware voll ausreizen, Performance ist sehr wichtig.

Ich gebe Dir durchaus recht, dass man, wenn ich eine konkrete Software entwickel, durchaus der Code anders aussehen kann (!), wie in einem theoretischen Modell.

Die von dir zitierte Aussage kann man durchaus auch umdrehen: die Komplexität eines Algorithmus sagt nichts darüber aus, wie lange er tatsächlich braucht (und das ist es, was mich interessiert).

Nein, jeder Rechner wird als Turing-Maschine betrachtet und darauf wird die Komplexitätsanalyse gemacht. Du gehst hier von einem konkreten Rechner, einer festen Architektur und sogar eine konkreten Sprache aus

Nun kannst du nicht sagen, was davon besser ist, oder?

Du möchtest innerhalb des Contest eine Aussage über die "Güte eines Algorithmus", sprich wie gute sein Laufzeitverhalten ist. Du kannst nicht einfach hingehen und ein Szenario definieren und sagen "wenn das Programm darauf schnell läuft, ist der Algorithmus besser als ein anderer".

Dein Contest soll die Güte bestimmen, d.h. Dein Bewertungsmaßstab muss richtig gewählt sein und das wäre hier eine Komplexitätsanalyse. Ich bestreite nicht, dass man eine Quick & Dirty Lösung erzeugen kann, die absolut schnell läuft (bzw. das konkrete Problem schnell löst). Ich kritisiere, dass Du eben auf dieser Art des "Meßverfahrens" keine gültige Aussage über die Güte treffen kannst bzw darfst. Wenn Du wirklich eine objektive Lösung möchtest, dann mache Komplexitätsanalyse, andernfalls hat, meiner Ansicht nach, die Interpretation des Endergebnis keine bestand.

Phil

[TomasRiker]

Kritik akzeptiert.

Einer perfekten fairen Bewertung anhand einer Komplexitätsanalyse stehen jedoch zu viele Hindernisse im Weg:

- Aufwand

- Nachvollziehbarkeit für jeden (auch den 12-jährigen Hobbyentwickler, der gerade seine ersten Schritte mit C++ gemacht hat)

- Teilnehmer, deren Algorithmus in allen für die Praxis relevanten Tests immer am schnellsten ist, die dann aber trotzdem nicht gewinnen. Die würden sich zurecht aufregen ...

Nun könnte man natürlich sagen: "Wenn eine solche Bewertung nicht möglich ist, dann hat der Contest keine Daseinsberechtigung."

Dem halte ich aber entgegen:

- Es macht Spaß, ein kleines Programm bis auf's Letzte zu optimieren.

- Der Wettbewerb mit den Anderen ist spannend und motivierend.

- Man lernt eine Menge dabei, z.B. wenn man einen Profiler benutzt und sieht, wie der Compiler den Code in Maschinensprache übersetzt, oder wie ein Prozessor eigentlich funktioniert.

Bearbeitet 15. September 2008 von TomasRiker

[flashpixx]

War eine gute Diskussion, fand ich jedenfalls

Einer perfekten fairen Bewertung anhand einer Komplexitätsanalyse stehen jedoch zu viele Hindernisse im Weg:

- Aufwand

- Nachvollziehbarkeit für jeden (auch den 12-jährigen Hobbyentwickler, der gerade seine ersten Schritte mit C++ gemacht hat)

- Teilnehmer, deren Algorithmus in allen für die Praxis relevanten Tests immer am schnellsten ist, die dann aber trotzdem nicht gewinnen. Die würden sich zurecht aufregen ...

Sicher, es ist der "praktische Ansatz". Sicher auch für einen Anfänger verständlich, der lieber nen Quicksort als einen Bubblesort implementiert. Nur würde ich immer dazu sagen, dass dies eben kein "generell gültiger Test" ist und sich die Ergebnisse widersprechen können. Denn gerade Anfänger (und hier sei der Hinweis auf die vielen Schüler im Forum gegeben) sind gerne mal eher dazu verleitet, schnell was Quick & Dirty zu codieren, was schnell läuft, aber einer passenden Analyse nicht standhält.

Nun könnte man natürlich sagen: "Wenn eine solche Bewertung nicht möglich ist, dann hat der Contest keine Daseinsberechtigung."

Nein Nein, er hat schon eine Daseinsberechtigung, nur eben mit dem Hinweis, dass man ihn nicht als generell betrachtet. Man würde ja auch im realen Umfeld etwas anders vorgehen, vor allem würde da auch nicht einzelne Personen sitzen.

Ein Wettbewerb "just for fun" ist durchaus okay, aber bei den Anfänger wirklich darauf hinweisen, dass diese Testverfahren nicht haltbar sind.

LG Phil

[xk4fu]

also, nicht, dass ich das falsch verstanden habe:

du hast ein programm, welches zwei variablen bekommt:

Bildgröße und der Anzahl der Rechtecke

d.h. jedem algorithmus werden diese zwei variablen übergeben;

was der algorithmus intern verbricht, ist doch erstmal vollkommen irrelevant, d.h. es kann über die o notation "ganz einfach" jeder algorithmus mit dem anderen verglichen werden, da:

1. jeder algorithmus die gleichen startvariablen braucht

wären es nicht die gleichen startvariablen, wäre es ein anderes problem, und somit wäre es schwachsinn, die beiden algorithmen zu vergleichen;

2. kann man die laufzeit des algorithmus auf die startvariablen abbilden, egal, was der algorithmus intern rumwurtschtelt!

3. kann somit jeder algorithmus, der das gleiche problem lösen muss, anhand dieser variablen eben "ganz einfach" miteinander verglichen werden;

[TomasRiker]

Ach so meinst du das. Dass ich quasi eine Art Zähler überall reinbaue. Ich dachte, du meinst das sollte allgemein, für beliebige Eingabeparameter gemacht werden. Wäre möglich!

Nur was man damit schwer abdecken kann, sind z.B. Fälle, wo jemand std::map oder so benutzt. Wenn dann jemand schreibt "map[key] = wert;", sieht das aus wie eine Zuweisung, aber dahinter steckt noch viel mehr.

[TomasRiker]

Der nächste Wettbewerb ist da.

Vielleicht möchte ja jemand mitmachen:

spieleprogrammierer.de :: Thema anzeigen - #11: "Rechnen einmal anders", K.d.C., 18.01.2009

Es geht darum, die vier Grundrechenarten zu implementieren, ohne dabei die eingebauten Operatoren (+, -, *, /, +=, -=, ...) zu verwenden - und das möglichst kurz.