WPC-Aufgabe (Programmierwettbewerb)

volkard

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

Ponto

Hab da ganz andere Werte raus. Kann aber am Generator liegen. Benutze den der glibc? Was habt ihr genommen?

Ich hab mal einen PRNG vorgeschaltet:

class Prng
{
public:
   Prng(unsigned int seed);

   void init (unsigned int seed);
   unsigned int getuint();
private:
   unsigned int a[55];
   int index;
};

Prng::Prng(unsigned int seed)
{
   init(seed);
}

void Prng::init(unsigned int seed)
{
   a[0] = seed;
   for (index = 1; index != 55; ++index) {
      a[index] = a[index-1]*31 + 1;
   }
}

unsigned int Prng::getuint() {
   index = (index + 1) % 55;
   a[index] = a[(index + 23) % 55] + a[(index + 54) % 55];
   return a[index];
}

class WeightListGenerator 
 { 
   std::vector<unsigned> weight_list;   
   Prng prng;

 public: 
   WeightListGenerator( size_t elems , unsigned seed = unsigned(time(0))) 
   : weight_list(std::vector<unsigned int>(elems,0)),
     prng(seed)
   { 
      while(elems--) 
        weight_list[elems] = prng.getuint(); 
   }   
   std::vector<unsigned> const & GetList() const { return weight_list; } 
 };

Mit den folgenden Ergebnissen:

E: 100 S: 10   228544409808
E: 300 S: 10   682663452603
E: 200 S: 12   426704698914
E: 200 S: 31   436103580650
E: 100 S: 1000 193533809787
E: 300 S: 1000 615707704331

Geht dein Algo auch mit gleichen Gewichten?
Ich hab den Code so geändert

class WeightListGenerator 
{ 
typedef std::map<unsigned int, int,std::less<unsigned int> > WMAP;
  std::vector<unsigned> weight_list;   
  WMAP wmap;
public: 
  WeightListGenerator( size_t elems , unsigned seed = unsigned(time(0))) 
  : weight_list(std::vector<unsigned int>(elems,0)) 
  { 
     std::srand(seed);                         
	 //while(elems--) {
  //     weight_list[elems] = unsigned(rand()); 
	 //}
	 while(elems>0) {
		 unsigned int value = unsigned(rand()); 
		 if(wmap.find(value) == wmap.end()) {
			 weight_list[elems] = value;
			 wmap.insert(WMAP::value_type(value,0));
			 elems--;
		 } else {
			 std::cout<<"\nEQUAL\n";
		 }
	 }

  }   
  std::vector<unsigned> const & GetList() const { return weight_list; } 
};

Und er gibt mir bei SEED=1000 ELEMS=300 zweimal EQUAL aus, bleibt auch nicht mehr hängen.

Haben wir nicht immer die gleichen Zahlen?

Jetzt wirds lang, aber ich wills wissen.

//begin
	list.push_back(365);
	list.push_back(1216);
	list.push_back(5415);
	list.push_back(16704);
	list.push_back(24504);
	list.push_back(11254);
	list.push_back(24698);
	list.push_back(1702);
	list.push_back(23209);
	list.push_back(5629);
	list.push_back(23830);
	list.push_back(32505);
	list.push_back(19574);
	list.push_back(16513);
	list.push_back(11529);
	list.push_back(13026);
	list.push_back(3768);
	list.push_back(1031);
	list.push_back(22229);
	list.push_back(7851);
	list.push_back(15646);
	list.push_back(7121);
	list.push_back(15810);
	list.push_back(6470);
	list.push_back(4195);
	list.push_back(25857);
	list.push_back(29816);
	list.push_back(11409);
	list.push_back(25981);
	list.push_back(6401);
	list.push_back(7628);
	list.push_back(17112);
	list.push_back(17688);
	list.push_back(1825);
	list.push_back(20443);
	list.push_back(19867);
	list.push_back(32578);
	list.push_back(4482);
	list.push_back(11605);
	list.push_back(18834);
	list.push_back(12136);
	list.push_back(28980);
	list.push_back(10524);
	list.push_back(17391);
	list.push_back(15489);
	list.push_back(1435);
	list.push_back(10254);
	list.push_back(17635);
	list.push_back(10633);
	list.push_back(13079);
	list.push_back(29982);
	list.push_back(17251);
	list.push_back(18993);
	list.push_back(5347);
	list.push_back(15274);
	list.push_back(1580);
	list.push_back(12245);
	list.push_back(1598);
	list.push_back(31753);
	list.push_back(5637);
	list.push_back(25262);
	list.push_back(18121);
	list.push_back(11875);
	list.push_back(9540);
	list.push_back(15177);
	list.push_back(15921);
	list.push_back(1989);
	list.push_back(4243);
	list.push_back(28727);
	list.push_back(8973);
	list.push_back(5492);
	list.push_back(23796);
	list.push_back(11271);
	list.push_back(2314);
	list.push_back(8834);
	list.push_back(22275);
	list.push_back(16241);
	list.push_back(6725);
	list.push_back(7072);
	list.push_back(14203);
	list.push_back(17364);
	list.push_back(32760);
	list.push_back(25907);
	list.push_back(28924);
	list.push_back(16867);
	list.push_back(15961);
	list.push_back(22442);
	list.push_back(2828);
	list.push_back(12442);
	list.push_back(1983);
	list.push_back(22030);
	list.push_back(11867);
	list.push_back(24696);
	list.push_back(19207);
	list.push_back(13018);
	list.push_back(17995);
	list.push_back(9960);
	list.push_back(310);
	list.push_back(22286);
	list.push_back(23471);
	list.push_back(24064);
	list.push_back(32351);
	list.push_back(24447);
	list.push_back(3283);
	list.push_back(3181);
	list.push_back(18888);
	list.push_back(9329);
	list.push_back(18110);
	list.push_back(18862);
	list.push_back(16712);
	list.push_back(24423);
	list.push_back(9139);
	list.push_back(12929);
	list.push_back(3059);
	list.push_back(25402);
	list.push_back(4862);
	list.push_back(411);
	list.push_back(8186);
	list.push_back(6761);
	list.push_back(11757);
	list.push_back(8348);
	list.push_back(24524);
	list.push_back(16304);
	list.push_back(24092);
	list.push_back(17730);
	list.push_back(4737);
	list.push_back(1244);
	list.push_back(14581);
	list.push_back(28381);
	list.push_back(15225);
	list.push_back(7133);
	list.push_back(13432);
	list.push_back(22531);
	list.push_back(5440);
	list.push_back(22045);
	list.push_back(6456);
	list.push_back(12420);
	list.push_back(13237);
	list.push_back(19984);
	list.push_back(21926);
	list.push_back(13216);
	list.push_back(4460);
	list.push_back(20237);
	list.push_back(5778);
	list.push_back(28280);
	list.push_back(3152);
	list.push_back(28508);
	list.push_back(18671);
	list.push_back(19139);
	list.push_back(5517);
	list.push_back(4240);
	list.push_back(26839);
	list.push_back(12738);
	list.push_back(6317);
	list.push_back(14870);
	list.push_back(16847);
	list.push_back(23414);
	list.push_back(527);
	list.push_back(1099);
	list.push_back(7696);
	list.push_back(27714);
	list.push_back(30811);
	list.push_back(21621);
	list.push_back(20905);
	list.push_back(11640);
	list.push_back(18422);
	list.push_back(13866);
	list.push_back(7219);
	list.push_back(23323);
	list.push_back(648);
	list.push_back(31301);
	list.push_back(14768);
	list.push_back(30072);
	list.push_back(18999);
	list.push_back(4385);
	list.push_back(5282);
	list.push_back(19031);
	list.push_back(19904);
	list.push_back(26201);
	list.push_back(17090);
	list.push_back(20187);
	list.push_back(19142);
	list.push_back(10706);
	list.push_back(14836);
	list.push_back(20649);
	list.push_back(2666);
	list.push_back(10748);
	list.push_back(20859);
	list.push_back(16972);
	list.push_back(3099);
	list.push_back(9044);
	list.push_back(25449);
	list.push_back(9945);
	list.push_back(21167);
	list.push_back(10542);
	list.push_back(8794);
	list.push_back(24782);
	list.push_back(1971);
	list.push_back(2993);
	list.push_back(30562);
	list.push_back(26688);
	list.push_back(26880);
	list.push_back(24355);
	list.push_back(31812);
	list.push_back(11318);
	list.push_back(13455);
	list.push_back(2151);
	list.push_back(26085);
	list.push_back(9040);
	list.push_back(1679);
	list.push_back(29379);
	list.push_back(29440);
	list.push_back(20396);
	list.push_back(23988);
	list.push_back(21223);
	list.push_back(13082);
	list.push_back(14857);
	list.push_back(14801);
	list.push_back(6955);
	list.push_back(14777);
	list.push_back(10285);
	list.push_back(2217);
	list.push_back(1305);
	list.push_back(4561);
	list.push_back(4741);
	list.push_back(21763);
	list.push_back(21547);
	list.push_back(1407);
	list.push_back(7436);
	list.push_back(27644);
	list.push_back(13781);
	list.push_back(3577);
	list.push_back(5997);
	list.push_back(27809);
	list.push_back(25286);
	list.push_back(32710);
	list.push_back(18540);
	list.push_back(30141);
	list.push_back(25964);
	list.push_back(18218);
	list.push_back(2178);
	list.push_back(26096);
	list.push_back(10678);
	list.push_back(18661);
	list.push_back(28615);
	list.push_back(25089);
	list.push_back(14877);
	list.push_back(15133);
	list.push_back(6934);
	list.push_back(5493);
	list.push_back(19941);
	list.push_back(2712);
	list.push_back(19563);
	list.push_back(24929);
	list.push_back(3232);
	list.push_back(8238);
	list.push_back(27279);
	list.push_back(28028);
	list.push_back(10997);
	list.push_back(6782);
	list.push_back(9208);
	list.push_back(20344);
	list.push_back(17567);
	list.push_back(20449);
	list.push_back(14570);
	list.push_back(15507);
	list.push_back(6072);
	list.push_back(11420);
	list.push_back(12515);
	list.push_back(31081);
	list.push_back(1336);
	list.push_back(16730);
	list.push_back(32566);
	list.push_back(31756);
	list.push_back(31417);
	list.push_back(5593);
	list.push_back(23286);
	list.push_back(29782);
	list.push_back(10621);
	list.push_back(5091);
	list.push_back(19989);
	list.push_back(11902);
	list.push_back(11953);
	list.push_back(7808);
	list.push_back(16333);
	list.push_back(1002);
	list.push_back(4339);
	list.push_back(10602);
	list.push_back(32319);
	list.push_back(20036);
	list.push_back(14099);
	list.push_back(25793);
	list.push_back(2907);
	list.push_back(4304);
	list.push_back(15382);
	list.push_back(20736);
	list.push_back(12543);
	list.push_back(19453);
	list.push_back(17537);
	list.push_back(20272);
	list.push_back(8291);
	list.push_back(12090);
	list.push_back(14548);
	list.push_back(347);
	list.push_back(8372);
	list.push_back(7434);
	list.push_back(2388);
	list.push_back(3908);
	list.push_back(4351);
	list.push_back(13659);
	list.push_back(24333);
	list.push_back(9045);
	list.push_back(16721);
	list.push_back(23060);
	list.push_back(24088);
	list.push_back(13273);
	list.push_back(26397);
	list.push_back(25069);
	list.push_back(23834);
	list.push_back(27755);
	list.push_back(12509);
	list.push_back(28035);
	list.push_back(13837);
	list.push_back(19374);
	list.push_back(15612);
	list.push_back(4780);
	list.push_back(5187);
	list.push_back(18751);
	list.push_back(30708);
	list.push_back(20999);
	list.push_back(25511);
	list.push_back(6120);
	list.push_back(9652);
	list.push_back(2776);
	list.push_back(17735);
	list.push_back(22551);
	list.push_back(6724);
	list.push_back(24851);
	list.push_back(11535);
	list.push_back(20110);
	list.push_back(26027);
	list.push_back(18871);
	list.push_back(3287);
	list.push_back(29531);
	list.push_back(30481);
	list.push_back(12637);
	list.push_back(12449);
	list.push_back(27915);
	list.push_back(31521);
	list.push_back(28945);
	list.push_back(12315);
	list.push_back(19483);
	list.push_back(31153);
	list.push_back(1376);
	list.push_back(6508);
	list.push_back(6831);
	list.push_back(30373);
	list.push_back(15282);
	list.push_back(14636);
	list.push_back(5254);
	list.push_back(6672);
	list.push_back(18907);
	list.push_back(9140);
	list.push_back(6958);
	list.push_back(9117);
	list.push_back(1004);
	list.push_back(25497);
	list.push_back(14964);
	list.push_back(11566);
	list.push_back(9295);
	list.push_back(29043);
	list.push_back(20767);
	list.push_back(194);
	list.push_back(23059);
	list.push_back(22755);
	list.push_back(12766);
	list.push_back(1436);
	list.push_back(4484);
	list.push_back(11988);
	list.push_back(20606);
	list.push_back(2210);
	list.push_back(11007);
	list.push_back(15616);
	list.push_back(20320);
	list.push_back(25603);
	list.push_back(5124);
	list.push_back(1718);
	list.push_back(299);
	list.push_back(18972);
	list.push_back(30349);
	list.push_back(2779);
	list.push_back(12990);
	list.push_back(14237);
	list.push_back(29342);
	list.push_back(26416);
	list.push_back(20841);
	list.push_back(20711);
	list.push_back(5662);
	list.push_back(16594);
	list.push_back(16732);
	//end

Ergebnis: 6213835

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.