WPC-Aufgabe (Programmierwettbewerb)

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.

c.rackwitz

volkard schrieb:

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

postest du im neuen jahr die zwischenschritte fuer dieses ergebnis? ich waer interessiert.

Michael E.

Ich auch, kireg nämlich auch 16628551 raus. Dabei war ich mir doch sicher, dass mein Algorithmus richtig ist

BTW: Ich wär mal froh, wenn ich die Komplexität von meinem Algo rauskriegen würd Müsst aber einklich O(n) sein.

Bashar

volkard schrieb:

ich hab 16628462.

Gut.

Ponto

Michael E. schrieb:

Ich auch, kireg nämlich auch 16628551 raus. Dabei war ich mir doch sicher, dass mein Algorithmus richtig ist

BTW: Ich wär mal froh, wenn ich die Komplexität von meinem Algo rauskriegen würd Müsst aber einklich O(n) sein.

O(n)? Da muss ich noch rauskriegen, wie man es ohne Sortieren macht.

TomasRiker

volkard, Bashar:
Ihr wollt uns doch nur Angst machen!
... oder?