Ergänzung zu Yalus Tests

[Stefan (Gast)]

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.

ls -lt a.out convex_hull
15320 Nov 13 21:14 a.out (g++ -O3)
84936 Nov 13 21:12 convex_hull (nim c -d:release)

Hier der C++ und Nim-Code:

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
typedef double coord_t;
typedef double coord2_t;
 
struct Point {
  coord_t x, y;
  bool operator <(const Point &p) const {
    return x < p.x || (x == p.x && y < p.y);
  }
};
 
coord2_t cross(const Point &O, const Point &A, const Point &B)
{
  return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
 
vector<Point> convex_hull(vector<Point> P)
{
  int n = P.size(), k = 0;
  vector<Point> H(2*n);
  sort(P.begin(), P.end());
  for (int i = 0; i < n; ++i) {
    while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
    H[k++] = P[i];
  }
  for (int i = n-2, t = k+1; i >= 0; i--) {
    while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
    H[k++] = P[i];
  }
  H.resize(k);
  return H;
}

#define Max 1000
#define NumPoints (Max * Max)

using namespace std;
int main()
{
  vector<Point> v(NumPoints);
  int i;
  for (i = 0; i < NumPoints; i++)
  {
    v[i].x =  i / Max; 
    v[i].y =  i % Max;
    //cout << v[i].x <<v[i].y << endl;
  }
  cout << endl;
  
  vector<Point> h = convex_hull(v);
  int s = h.size();
  for (i = 0; i < s; i++)
  {
    cout << "(" << h[i].x << "," << h[i].y << ") ";
  }
  cout << endl;
}

import algorithm, sequtils
const
  Max = 1000
  NumPoints = Max * Max

type Point = tuple[x, y: float]

proc cmpPoint(a, b: Point): int =
  result = cmp(a.x, b.x)
  if result == 0:
    result = cmp(a.y, b.y)

template cross[T](o, a, b: T): expr =
  (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)

proc slower_convex_hull[T](points: var seq[T], cmp: proc(x, y: T): int {.closure.}) : seq[T] =
  points.sort(cmp)
  var lower: seq[T] = @[]
  for p in points:
    while len(lower) > 1 and cross(lower[len(lower) - 2], lower[len(lower) - 1], p) <= 0:
      discard lower.pop
    lower.add(p)
  var upper: seq[T] = @[]
  for i in countdown(high(points), low(points)):
    let p = points[i]
    while len(upper) > 1 and cross(upper[len(upper) - 2], upper[len(upper) - 1], p) <= 0:
      discard upper.pop
    upper.add(p)
  result = concat(lower[0 .. -2], upper[0 .. -2])

proc convex_hull[T](points: var seq[T], cmp: proc(x, y: T): int {.closure.}) : seq[T] =
  points.sort(cmp)
  let n = points.len
  var k = 0
  result = newSeq[T](2 * n)
  for p in points:
    while k > 1 and cross(result[k-2], result[k-1], p) <= 0:
      dec(k)
    result[k] = p
    inc(k)
  var
    i = n - 2
    t = k + 1
  while i >= 0:
    while k >= t and cross(result[k-2], result[k-1], points[i]) <= 0:
      dec(k)
    result[k] = points[i]
    inc(k)
    dec(i)
  result.setLen(k-1)

#var v = map(toSeq(0..<MaxPoints), proc(x: int): Point = (float(x div Max), float(x mod Max)))

var
  v = newSeq[Point](NumPoints)
  i = 0

while i < NumPoints:
  v[i].x =  (float) (i div Max) 
  v[i].y =  (float) (i mod Max)
  inc(i)
  
#echo slower_convex_hull[Point](v, cmpPoint)
echo convex_hull[Point](v, cmpPoint)

#assert(convex_hull[Point](s, cmpPoint) == @[(0.0, 0.0), (999.0, 0.0), (999.0, 999.0), (0.0, 999.0)])

Übrigens frage ich mich, wieso mit

   vector<Point> H(2*n);

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?