WPC-Aufgabe (Programmierwettbewerb)

Jester

Die Frage mußt Du Dir selbst beantworten. Mein Cache ist dasfür jedenfalls zu klein

Mein System sieht etwa so aus:

AMD64 3500+, 1024MB RAM. Während den Tests werden keine größeren Programme im Hintergrund laufen, so dass ein Großteil des Speichers auch zur Verfügung stehen dürfte.

Super, das reicht. :xmas1:

c.rackwitz

wozu brauchst du 300 MB speicher?

Kann ich jetzt leider noch nicht so genau verraten. Es geht darum, einen Algorithmus mit linear wachsendem Speicherbedarf herzunehmen, weil er ein etwas besseres Laufzeitverhalten hat. Wenn er aber bei 500MB zum swappen anfängt ist der Spaß vorbei, deshalb behandel ich ganz große Listen ein bisschen anders. Vielleicht nimmt Jester eh keine Listen mit mehr als 20 Mio Elementen her. Vielleicht nimmt er sie jetzt auch nur extra deshalb her, weil er das liest. Mal schaun. :xmas1:

volkard

c.rackwitz schrieb:

wozu brauchst du 300 MB speicher?

bei 10 mio elemeten sind das nur 30 byte pro element.

Jester

Optimizer schrieb:

Vielleicht nimmt Jester eh keine Listen mit mehr als 20 Mio Elementen her. Vielleicht nimmt er sie jetzt auch nur extra deshalb her, weil er das liest.

Ja, jetzt krieg ich Dich da wo's weh tut.

Nein, ich schrieb oben was von "vor allem Geschwindigkeit auf Eingaben mittlerer Größe". Daran werde ich mich auch halten. Kann sein, daß auch mal 20 Mios vorkommen, viel größer wohl kaum und der Schnitt wird denke ich eher niedriger liegen.

MfG Jester

c.rackwitz

euer exzessiver speicherverbrauch zusammen mit einem profiler hat mir jetzt gewaltige optimierungsmoeglichkeiten aufgezeigt. danke!

Deutschland hat aber über 80 Mio. Einwohner.

volkard

Kennner schrieb:

Deutschland hat aber über 80 Mio. Einwohner.

aber die bösen bekommen die rute zu spüren. höchstens 100 geschenke muß der weihnachtsmann in deutschland verteilen. gut-sein ist unmodern. die anderen geschenke sind gefaked, da spielen verwandte und freunde den weihnachtsmann und bringen geschenke (, die sie vorher zu diesem zweck gekauft haben).

Michael E.

Kann mir einer nen Profiler empfehlen?

evilissimo

volkard schrieb:

Kennner schrieb:

Deutschland hat aber über 80 Mio. Einwohner.

aber die bösen bekommen die rute zu spüren. höchstens 100 geschenke muß der weihnachtsmann in deutschland verteilen. gut-sein ist unmodern. die anderen geschenke sind gefaked, da spielen verwandte und freunde den weihnachtsmann und bringen geschenke (, die sie vorher zu diesem zweck gekauft haben).

Du hast Weihnachten für mich zerstört. Ich habe immer noch an den Weihnachtsmann geglaubt *fg* :p

BR
evilissimo

evilissimo

@ Jester
Werden die Strecken Parallel zur X und Y Achse verlaufen?

Edit: Und liegen alle Punkte/Strecken im positiven Bereich oder können die auch im negativen liegen?

BR

evilissimo

Jester

Die Strecken liegen einfach irgendwie. Weder in nem festen Bereich, noch parallel zu irgendwas.

Kann das jemand bestätigen

std::vector<unsigned int> list2; 
    list2.push_back(98324); 
    list2.push_back(876); 
    list2.push_back(9999987); 
    list2.push_back(1876); 
    list2.push_back(17654); 
    list2.push_back(290); 
    list2.push_back(3872365); 
    list2.push_back(47828); 
    list2.push_back(5837); 
    list2.push_back(16276); 
    list2.push_back(782376); 
    list2.push_back(828374); 
    list2.push_back(97654); 
    list2.push_back(90); 
    list2.push_back(910); 
    list2.push_back(920); 
    list2.push_back(1920); 
    list2.push_back(555555); 
    list2.push_back(39201); 
    list2.push_back(59201); 
    list2.push_back(49301); 
    list2.push_back(11); 
    list2.push_back(222); 
    list2.push_back(33); 
    list2.push_back(1); 
    list2.push_back(1465); 
    list2.push_back(7828); 
    list2.push_back(2837); 
    list2.push_back(28376); 
    list2.push_back(82376); 
    list2.push_back(2); 
    list2.push_back(28374);

16628551

std::vector<unsigned int> list3; 
    list3.push_back(100); 
    list3.push_back(1); 
    list3.push_back(2); 
    list3.push_back(3); 
    list3.push_back(4); 
    list3.push_back(5); 
    list3.push_back(6); 
    list3.push_back(12); 
    list3.push_back(8); 
    list3.push_back(11);

160

std::vector<unsigned int> list4; 
    list4.push_back(2); 
    list4.push_back(33); 
    list4.push_back(4); 
    list4.push_back(5); 
    list4.push_back(6); 
    list4.push_back(1);

37

roger that. Würd mich auch freuen, wenn eine dritte Instanz das noch bestätigen könnte. Ich weiß nicht warum, aber ich hab ne panische Angst, dass ich es nicht richtig mache. Ich find meinen Algorithmus zwar logisch, aber für nen Korrektheitsbeweis bin ich zu blöd.

EDIT: was ist bis jetzt der geilste Frickel-Kommentar in eurem Code? Meiner:

// vielleicht passt des

Bashar

Ich kann alle drei Werte bestätigen. Mich wundert, wieso das die optimalen Werte sein sollen, ich hab eigentlich erstmal die einfachste Form meines Algorithmus' aufgeschrieben, die Verbesserung sollte noch kommen ... das scheint aus irgendeinem Grunde so schon optimal zu sein. Oder eure Ergebnisse sind es nicht

Muss nur noch -- definitiv -- an der Laufzeit feilen

Ich kann alle drei Werte bestätigen.

Dann kann's kaum noch falsch sein.

Bashar schrieb:

Muss nur noch -- definitiv -- an der Laufzeit feilen

Hast noch nichts mit O(log(log(log n))) gefunden?

Woah, kann das sein, dass std::vector::clear() ends teuer ist? Das STL-Zeugs taugt irgendwie nicht.

Bashar

Nein, erstmal die doof-Version, O(n^2). 10000 Pakete dauern ein paar Sekunden.

evilissimo

class WeightListGenerator
{
  std::vector<unsigned> weight_list;  
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());
  }  
  std::vector<unsigned> const & GetList() const { return weight_list; }
};

Anstatt ständig alles tippen zu müssen könnt ihr die obige klasse verwenden um eure vectoren zu basteln. Mit dem selben startwert ( seed ) könnt ihr dann eure werte untereinander vergleichen. ( macht eure posts etwas kürzer )

size_t anzahl_pakete = 10;
unsigned seed = 234;
WeightListGenerator gen( anzahl_pakete , seed );
u64 result = wpc_expert(gen.GetList());

BR
evilissimo

volkard

irgendwer schrieb:

Kann das jemand bestätigen
16628551

leider nicht.
ich hab 16628462.
ich hab aber auch 16628551 in meinem ersten versuch gehabt.