WPC-Aufgabe (Programmierwettbewerb)

Jester

Klar, Standard-Lib ist erlaubt! Ja, die getter/setter müssen natürlich const sein.
Ich änder's gleich noch in der Aufgabenstellung.

Die Geschenke haben natürlich alle ein Gewicht echt größer 0.

MfG Jester

Michael E.

Jester schrieb:

Klar, Standard-Lib ist erlaubt!

hash_map ist doch aber nur ne standard extension, oder etwa nicht?

Jester

Ist auch wieder wahr. Aber wenn ne Hashmap hilft, dann soll's mir recht sein.

Was ist die Referenz, ob das Programm standardkonform genug ist? Ich kann beim VC++ 8 size_t benutzen ohne std:: ist das normal?

TomasRiker

Also ich denke mal nicht, dass Du mit einer Strafe rechnen musst, wenn noch ein "std::" irgendwo vor muss

Jester

Wenn da sowas wie ein std:: fehlt, dann ist das kein Problem. Ich prüfe sicher nicht jedes Detail nach.

Nur, wenn ich das nicht mit geringem Aufwand kompiliert krieg (weil grobe Syntaxfehler drin sind), dann werde ich's halt rausschmeißen.

Jester

@Korrektheit: Mit der Formulierung wollte ich aussagen, daß die Lösung natürlich korrekt arbeiten muß und andernfalls ausgeschlossen wird.

TomasRiker

Mein Algorithmus läuft mit Visual C++ (STLPort) mehr als doppelt so schnell als mit GCC... liegt das eher an der STL-Implementierung oder an was anderem?

TomasRiker schrieb:

Mein Algorithmus läuft mit Visual C++ (STLPort) mehr als doppelt so schnell als mit GCC... liegt das eher an der STL-Implementierung oder an was anderem?

Profiler.

User--

hash_map ist nen bischen ungeschickt, da viele Standard-Libs die zwar anbieten, aber oft nen anderes Interface haben.
Wäre es daher nicht klüger zu sagen, alle sollen STLPort verwenden?

Ne, darauf hab ich keine Lust. Im Zweifelsfall würde ich halt sagen, er muss die nötigen Header für hash_map mitliefern.

Können wir davon ausgehen, dass gewicht1 + gewicht2 € { Wertebereich von unsigned int } ?
Wenn nicht, wär's auch nicht so schlimm, nur wissen würde ich es gerne. :xmas1:

TomasRiker

Eigentlich wäre es schon gut, wenn alle STLPort nehmen würden. Dann hätte man einen Unsicherheitsfaktor, nämlich die STL-Implementierung, weniger im Spiel.
Leider kriege ich es absolut nicht hin, STLPort unter Dev-C++ zum laufen zu kriegen. Hat es jemand von Euch schonmal probiert?
Das Builden mit make klappt nicht und das direkte Verwenden der Header (ohne IO-Streams, was laut INSTALL-Datei eigentlich funktionieren sollte) geht auch nicht.

Siehste, kriegst es nichtmal hin. :xmas1:
Und ich werde es auch nicht hinkriegen. Ich code einmal im Jahr in C++, mir fehlt da die Routine mit include-path, lib-path setzen, usw.

Aber mal Ernst, welchen Unsicherheitsfaktor meinst du? Wenn du etwas nehmen willst, was nicht aus der STL ist, spricht doch nichts dagegen, du kannst ja den Header mitgeben. Dein Programm ist sicher nicht standardkonform, wenn du eine erweiterte STL voraussetzt.

Michael E. schrieb:

// 'ne Menge Code
Kompiliert mit VC++ 2003 Toolkit auf Speed optimiert komm ich auf folgende Ausgabe:

5 174 824
722 308 723

Wie siehts bei euch aus?

Ich krieg

initialized
518186
116811652
Drücken Sie eine beliebige Taste . . .

Ich kann aber noch nicht mit Sicherheit sagen, dass ich alles hundertprozentig richtig mache. Zumindest krieg ich aber die 290 raus.

EDIT: Ich vermute random_shuffle ist nicht gleich. Ich biete nochmal ne feste Folge an:

vector<unsigned int> list;
	list.push_back(98324);
	list.push_back(876);
	list.push_back(7654);
	list.push_back(90);
	list.push_back(872365);
	list.push_back(7828);
	list.push_back(2837);
	list.push_back(28376);
	list.push_back(82376);
	list.push_back(28374);

Ergebnis: 1136412

Jester

Optimizer schrieb:

Können wir davon ausgehen, dass gewicht1 + gewicht2 € { Wertebereich von unsigned int } ?
Wenn nicht, wär's auch nicht so schlimm, nur wissen würde ich es gerne. :xmas1:

Ja, da könnte ihr von ausgehen.

Michael E.

Optimizer schrieb:

Ich biete nochmal ne feste Folge an:

vector<unsigned int> list;
	list.push_back(98324);
	list.push_back(876);
	list.push_back(7654);
	list.push_back(90);
	list.push_back(872365);
	list.push_back(7828);
	list.push_back(2837);
	list.push_back(28376);
	list.push_back(82376);
	list.push_back(28374);

Ergebnis: 1136412

Krieg ich auch raus.

TomasRiker

Mit Visual C++ schaffe ich:
444535
125194854

Mit Dev-C++ leider nicht...
es scheint an der STL-Implementierung zu liegen.
STLPort ist da fast doppelt so schnell (darum will ich's ja auch benutzen)!

Ist es ok, wenn mein Programm 300 MB Speicher bei 10 Millionen Elementen braucht?

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.