Ich hatte mir eben dann doch noch mal den C++ und Haskell Code etwas
genauer angesehen und einige Tests gemacht. Die Geschwindigkeit von
Haskell ist schon recht beeindruckend dafür, dass der Code doch recht
abstrakt, also nicht sonderlich optimiert ist. Der C++ Code verzichtet
ja nun auf push() und pop()-Operationen und ebenfalls auf
Kopieroperationen, indem gleich zu Anfang ein großer Vector angelegt
wird. Das habe ich mal in Nim nachgebildet. Und: Nim ist bei mir damit
sogar etwas schneller als C++. Selbst die Variante slow_convex_hull()
mit push() und pop() ist etwa gleich schnell wie die C++ Version: C++
und Nim slow_convex_hull etwa 0.28s und Nim convex_hull etwa 0.25s.
Jeweils compiliert mit gcc/g++ 4.8.3 mit -O3. Etwas langsamer wird alles
mit der Initialisierung durch "v = map(...". aber das ist ja irrelevant.
Fazit: Ich hätte doch gedacht, dass pop() und push() etwas mehr Zeit
frisst. Und dass Nim in diesem Beispiel gleichauf mit C++ liegt ist doch
etwas mehr, als ich erwartet hatte. Bei den Dateigrößen sieht es für Nim
nicht ganz so gut aus, da ist wohl doch stets einges vom Laufzeitsystem
enthalten, insbesondere der GC.
in dem Wikibook C++ Code ein Vektor doppelt so groß wie der
Ursprüngliche angelegt wird? Die Hülle kann doch eigentlich nie mehr
Punkte als die ursprüngliche Punkmenge haben? Na gut, der erste und
letzte Punkt werden ja zunächt doppelt gespeichert, aber da sollte ja
irgendwas wie +1 reichen?