3. WPC-Aufgabe (Programmierwettbewerb)

WPC-Aufgabe (Programmierwettbewerb)

  • M

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

    0
  • E

    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 )

    0
  • P

    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.

    0
  • E

    du meinst wohl eher 2 * n

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

    BR
    evilissimo

    0
  • J

    schau Dir mal ein kariertes Blatt Papier an. 😉

    0
  • V

    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.

    0
  • E

    Jester schrieb:

    schau Dir mal ein kariertes Blatt Papier an. 😉

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

    0
  • B

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

    0
  • P

    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.

    0
  • N

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

    0
  • B

    Was will er uns nur sagen? 😕

    0
  • V

    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.

    0
  • J

    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

    0
  • M

    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?

    0
  • V

    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.

    0
  • M

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

    0
  • ?

    Wer hat abgegeben?

    0
  • P

    Hier ist meine Abgabe für die Sortieraufgabe. Bin mir aber über die Korrektheit nicht klar geworden, kann also falsch sein.

    http://www.pontohonk.de/wpc/wpc-sorting.C

    0
  • V

    hier meine:

    #include <vector>
#include <algorithm>
//#include <iostream>
using namespace std;

struct Geschenk{
	unsigned int gewicht;
	size_t platz;
	friend bool operator<(Geschenk const& a,Geschenk const& b){
		return a.gewicht<b.gewicht;
	}
};

typedef unsigned long long u64; 
u64 wpc_expert(std::vector<unsigned int> const& weights){
	u64 result=0;
	//geschenke kopieren in meine kleine liste, die sich die 
	//ursprüngliche platznummer zu jedem geschenk merkt. 
	size_t size=weights.size();
	vector<Geschenk> geschenk(size);
	for(size_t i=0;i!=size;++i){
		geschenk[i].gewicht=weights[i];
		geschenk[i].platz=i;
	}
	//sortieren
	sort(geschenk.begin(),geschenk.end());
	//kleinstes gewicht überhaupt merken
	u64 globalMin=geschenk[0].gewicht;
	//jetzt kann ich anhand der platznummern die zyklen erkennen
	for(size_t start=0;start!=size;++start){
		if(geschenk[start].platz!=start){
//			cout<<geschenk[start].gewicht<<' ';
			unsigned int min=geschenk[start].gewicht;
			size_t len=1;
			u64 sum=min;
			size_t ende=geschenk[start].platz;
			geschenk[start].platz=start;
			while(ende!=start){
//				cout<<geschenk[ende].gewicht<<' ';
				if(geschenk[ende].gewicht<min)
					min=geschenk[ende].gewicht;
				sum+=geschenk[ende].gewicht;
				size_t neuEnde=geschenk[ende].platz;
				++len;
				geschenk[ende].platz=ende;
				ende=neuEnde;
			}while(ende!=start);
//			cout<<"    "<<len<<' '<<min<<' '<<sum<<'\n';
			//so, jetzt habe ich vom zyklus die laenge, die summe das minimum. 
			//nun kommt die überlegung. 

			//der weihnachtsmann arbeitet immer zyklus nach zyklus ab. 
			//dabei macht er einen polygontausch. pfiffigerweise beginnt er dabei 
			//mit dem leichtesten geschenk im zyklus. dadurch hebt er immer das 
			//leichteste und das, was auf seinen zielplatz kommt. 
			//er macht also len-1 vertauschungen, jeweils das leichteste und 
			//ein anderes. 
			u64 arbeitOhneTrick=sum+(len-2)*u64(min);
			//machmal kommt es vor, daß es ein trick es noch leichter macht. 
			//beispiel: 1 32 33 34 31
			//hier hat er nur den zyklus 32 33 34 31 zu vertauschen, aber das 
			//kostet so zu viel. wenn er zuerst die 31 mit der 1 vertauscht, 
			//kann er dann 34, 33, 32 und 31 mit 1, hat er so viel arbeit gespart, 
			//daß es sich gelohnt hat, das leichte paket zu benutzen und mehr als 
			//die minimale anzahl an vertauschungen durchzuführen. 
			u64 arbeitMitTrick=sum+min+(len+1)*globalMin;
			if(arbeitOhneTrick<arbeitMitTrick)
				result+=arbeitOhneTrick;
			else
				result+=arbeitMitTrick;
		}
	}
	return result;
}

    wir haben das gleiche verfahren.

    habe mich übrigens gegen

    for (SizeType i = 0; i != size; ++i) pos[i] = i;
   std::sort(pos.begin(), pos.end(), Sorter(weights));

    entschieden, weil da die zugriffe während des sortierens zu durcheinander sind. ich befürchte, das macht der cache nicht mit.

    total_weight += weights[i];

    in der innersten schleife wollte ich das ergebnis nicht anfassen, da es bestimmt nicht gut in ein register gesteckt werden kann. hab deswegen den zyklus noch auf ne lokale variable sum aufsummiert. eigentlich unangebracht und dein code ist hübscher.

    u64 s1 = (amount - 2) * min;
      u64 s2 = (amount + 1) * M + min;

    das ist bitter. bei nem großen zyklus kriegste einen überlauf, weil amount und min nur 32-bitter sind.

    std::swap(cur, pos[cur]);

    lol. ich hab

    size_t neuEnde=geschenk[ende].platz;
				geschenk[ende].platz=ende;
				ende=neuEnde;

    geschrieben und nicht bemerkt, daß die folge von zuweisungen einfach nur die beiden vertauscht.

    0
  • E

    Meine WPC Pro ( die Linien ) Lösung ist folgende ( falls es überhaupt jemanden interessiert *g* )

    http://www.evilissimo-softdev.de/wpc/wpc_pro.html

    BR

    evilissimo

    0
Anmelden zum Antworten