WPC-Aufgabe (Programmierwettbewerb)

Zuviel rumgefrickelt
Mit dem neuen Algo ist das Ergebnis 6149750

Brutus

Hat jemand 'ne große Vergleichsliste für die Schnittpunktaufgabe? Ne 30er, am besten 50er oder am allerbesten ne 100er wäre ganz hilfreich, dann könnten wir auch mal vergleichen.

Hehe, ich glaub, ich hab nen Algo gefunden (meinen alten konnt ich ja jetzt in die Tonne treten ), muss ich zu Hause mal ausprobieren.

irgendwer schrieb:

Zuviel rumgefrickelt
Mit dem neuen Algo ist das Ergebnis 6149750

hm, ich komme auf 6149588

Michael E.

Hehe, Algo mit O(n) Komm aber heut nicht mehr nach Hause

evilissimo

Und hier noch etwas für WPC_Pro:

#include <limits>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <vector>

static const double max_int = std::numeric_limits<int>::max();

#include <windows.h>

#pragma once

struct Point
{
  Point(double xc, double yc) : x(xc), y(yc) {}
  double x, y;
};

class Line
{
public:
  Line(Point const& startPoint, Point const& endPoint) : start(startPoint), end(endPoint)
  {}
  Point const& getStart() const { return start; }
  Point const& getEnd()   const { return end;   }

private:
  Point start, end;
};

size_t wpc_pro(std::vector<Line> const& lines);

class WPCProHelper
{
    enum
    {
        minLength = 20,
	    maxLength = 100,
        windowWidth = 640,
    	windowHeight = 480
    };
public:
    WPCProHelper()
    {
        __int64 s = get_rdtsc();
        Sleep(1000);
        __int64 e = get_rdtsc();   
        computer_speed = (e - s) / 1000;
    }
    size_t execute( int num , unsigned seed )
    {
        std::vector<Line> vec = generateLines(num,seed);
        startMessure();
        size_t erg = wpc_pro(vec);    
        endMessure();            
        return erg;
    }
    __int64 getDuration()
    {
        return (( end_ticks - start_ticks ) / computer_speed);
    }
private:
    __int64 computer_speed;
    __int64 start_ticks;
    __int64 end_ticks;    
private:
    void startMessure()
    {
        start_ticks = get_rdtsc();
    }
    void endMessure()
    {
        end_ticks = get_rdtsc();
    }
    bool invalidPoint(Point const& p) 
    {
	    return (p.x <= 0 || p.y <= 0 || p.x >= windowWidth || p.y >= windowHeight);
    }
    __int64 get_rdtsc()
    {
       __asm rdtsc
    }
    inline std::vector<Line> generateLines( int numLines , unsigned seed = unsigned(time(0))) 
    {
        using namespace std;
        srand(seed);
        std::vector<Line> target;
	    for(int i = 0; i < numLines; ++i) {
		    Point start(0, 0), end(0, 0);
		    double length, phi;

		    start.x = random01() * windowWidth;
		    start.y = random01() * windowHeight;

		    do {
			    length = random01() * (maxLength - minLength) + minLength;
			    phi = random01() * 2 * 3.14;

			    end.x = start.x + length * cos(phi);
			    end.y = start.y + length * sin(phi);
		    } while(invalidPoint(end));

		    target.push_back(Line(start, end));
	    }
        return target;
    }
    double random01() 
    {
        return double(rand()/max_int);
    }
};

#include "WPCProHelper.h"
#include <iostream>

int main()
{
    WPCProHelper h;
    size_t erg = h.execute(10000,333);
    std::cout << erg << "\t" << h.getDuration() << std::endl;
}

Mein ergebnis für die verwendete Einstellung ( seed = 333 / linien = 10000 )

4052812 Schnittpunkte

Mein AMD Athlon XP 2600+ mit 1024 MB RAM braucht dafür ca. 2.9 Sekunden

Ich hab den Code mit dem VC8 als Release compiliert mit eingeschalteten Optimierungen.

Da mein Algorithmus noch O(n^2) ist lässt sich da bestimmt noch was drehen. Mal schauen ob mir noch ne Idee kommt

BR
evilissimo

PS: Ich bitte um eine Anpassung des obigen Codes für vergleichbare tests, muss aber dazu sagen das die Generierung der Linien mit Prng mir persönlich viel zu lange dauert. *g* Vielleicht kann das ja jemand mal anpassen ( Vorallem eine evtl portablere Version beitragen )

Ponto

evilissimo schrieb:

Da mein Algorithmus noch O(n^2) ist lässt sich da bestimmt noch was drehen. Mal schauen ob mir noch ne Idee kommt

Viel besser kann es nicht gehen, da im Worst Case O(n^2) Schnittpunkte exisitieren.

evilissimo

du meinst wohl eher 2 * n

gib mir mal ein beispiel für n^2 falls du eins hast, wäre interessant.

BR
evilissimo

Jester

schau Dir mal ein kariertes Blatt Papier an.

volkard

Ponto schrieb:

Viel besser kann es nicht gehen, da im Worst Case O(n^2) Schnittpunkte exisitieren.

das stimmt.
aber jester hat extra angeküdigt, daß viele kurze srecken dabei sind. da könnte doch was unterquadratisches gehen.

evilissimo

Jester schrieb:

schau Dir mal ein kariertes Blatt Papier an.

naja ein Kariertes Blatt hat glaub ich dann n * ( n / 4 ) Schnittpunkte.

borg

womit bewiesen wäre das es nicht schneller als O(n^2) geht

Ponto

borg schrieb:

womit bewiesen wäre das es nicht schneller als O(n^2) geht

Deshalb unterteilt man die Laufzeit solcher Algorithmen gerne:

O(nlogn + Ergebnis) ist dann besser als O(n^2 + Ergebnis) obwohl beide zu O(n^2) werden, wenn das Ergebnis wie hier gezeigt O(n^2) ist.

ness

Um Gottes willen! Ihr macht hier komplexitätsanalysen und riesige tests und ich hab mir mal eben in nen paar stunden was gebastelt???
Naja, hab glaub ich O(n^2), bin mir aber nicht sicher (manchmal kann ich schneller ausschließen, dass sich 2 Strecken net schneiden (parallel), dafür berechne ich aber auf kosten der übersichtlichkeit was doppelt)...

Brutus

Was will er uns nur sagen?

volkard

Brutus schrieb:

Was will er uns nur sagen?

er will, daß alle denken, er würde was voll lahmes abgeben, damit sie noch schnell zur streckenaufgabe wechseln, und er dann alle plattmacht.

Jester

Zumindest hat er die erste Abgabe überhaupt gemacht gemacht.

Achja, er hatte die feine Idee, die Point- und Line- Klasse in wpc_pro.h zu verpacken. Vielleicht können sich da alle dran halten. Wäre praktisch, ist aber natürlich, da ich's so spät erst sage, kein Teilnahmekriterium.

MfG Jester

Michael E.

volkard schrieb:

SEED=10 ELEMS=100 : 1509278
ich hab 1509218

SEED=10 ELEMS=300 : 5041260
ich hab 5041108

SEED=12 ELEMS=200 : 3132883
ich hab auch 3132883

SEED=31 ELEMS=200 : 3200808
ich hab auch 3200808

SEED=1000 ELEMS=100 : 1628503
ich hab 1624809

SEED=1000 ELEMS=300 : bleibt hängen (ich hoffe mal auf gleiche Gewichte)
ich hab 4776964

Hast du das mit dem schnellen Algo oder mit dem sicheren Algo gemacht?

volkard

Michael E. schrieb:

Hast du das mit dem schnellen Algo oder mit dem sicheren Algo gemacht?

ich habe nur einen implementiert. einen recht schnellen. aber hab nicht irgendwie bewiesen, daß er korrekt ist. hab auch keine programmiertechnischen optimierungem. hab nur so runtergeschrieben, wie ich per hand festtstellen würde, wieviel der weihnachstmann heben muss.

Michael E.

Ich glaub, dann brauch ich gar nicht erst mit Optimieren anzufangen. Naja, hab auch noch anderes zu tun.