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.

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.

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.

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)? Ja, kann (und wird) passieren. Was ich davon habe? Damit versuche ich, den Einfluss der verschiedenen Rechnerarchitekturen auf das Ergebnis zumindest etwas zu reduzieren. 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.

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.

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

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.

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

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!

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.