Foren » 33. BwInf

Aufgabe 3 Zeit zur Bearbeitung + C++11

    • 16 Beiträge
    24. Januar 2015 16:43:15 CET
    Hallo!

    Ich wollte zunächst einmal fragen, ob man C++11 sowie 64-Bit-Unterstützung, voraussetzen kann/darf - C++11 bietet einige interessante Features, die ich gerne nutzen würde und die Bearbeitung von bspw. 100000 Zeichen mit nur ca. 2GB RAM (32-Bit) ist effektiv nahezu unmöglich...
    Auch würde mich interessieren, wie ich mir die Abarbeitung von einer 100000-Zeichen-Kette vorstellen soll bzw. welche Hardware man hier voraussetzen kann - bei mancher Hardware würde es Jahre dauern, bei mancher weniger lange...
    Die Bearbeitung ist zudem mit wenig RAM-Nutzung zwar möglich, jedoch ausgesprochen ineffektiv und es würde ewig dauern, bis man zu einem Ergebnis käme.. (Ich spreche hier stets vom Worst-Case, bei dem sämtliche Möglichkeiten, bei 100000 Zeichen also um die 5.000.000.000, bearbeitet werden müssen)

    Lange Rede, kurzer Sinn: Wie soll ich mir "Kann Längen bis X verarbeiten" vorstellen und was kann ich voraussetzen?

    Viele Grüße
    Dieser Beitrag wurde am 24. Januar 2015 16:46:30 CET von David Schmidt bearbeitet
    • 38 Beiträge
    24. Januar 2015 17:35:19 CET
    In der Aufgabenstellung steht 10000 ;). Ich denke, deine Lösung sollte auch mit durchschnittlicher Hardware in akzetabler Zeit funktionieren.

    Gruß Felix
    Dieser Beitrag wurde am 24. Januar 2015 17:36:07 CET von Felix Roth bearbeitet
    • 16 Beiträge
    24. Januar 2015 17:53:32 CET
    Das stimmt, für 10000 ist das kein Problem - bloß ist das ja nur die Mindestanforderung und ein Beispiel von bwinf.de hat die Länge 100000 - dieses könnte mein Programm theoretisch verarbeiten, jedoch würde es sehr lange dauern, daher meine Frage, was als "Kann es verarbeiten" gilt... Wenn man die Ergebnisse der Beispiele in der Doku angeben soll wäre jemand (ich übertreibe mal etwas), der sich bspw. ein Rechenzentrum mietet hier im Vorteil, da er schreiben könnte, mein Programm kann Zeichenketten bis 100000 zeichen verarbeiten, was sonst nur mit sehr langen Wartezeiten möglich wäre...


    Dieser Beitrag wurde am 24. Januar 2015 17:54:33 CET von David Schmidt bearbeitet
  • 25. Januar 2015 22:05:09 CET
    Das Thema Programmiersprachen gab es in diesem Forum schon. An C++11 müsste nichts auszusetzen sein. Über RAM-Größe/64-Bit-Unterstützung sowie Zeit kann ich zwar natürlich keine offizielle Aussage treffen aber ich nehme mal stark an dass die Lösung auch mit normaler Hardware gut laufen muss. Natürlich ist eine Länge von 100000 Zeichen nicht grade klein aber wenn es schon extra als Material auf bwinf.de angeboten wird, wäre es glaub ich schon besser wenn dein Programm das behandeln könnte.
    • 2 Beiträge
    31. Januar 2015 09:31:52 CET
    Hallo alle zusammen Ich hab's einfach mal ausprobiert und ein Programm in Java geschrieben dieses braucht 800 Sek zur Bearbeitung des 100000 Zeichen String bei der Konfiguration k=2, l=2 die für mich die langwierigste sinnlogische darstellt. Ich arbeite außerdem nicht! In einem Rechenzentrum.
    • 16 Beiträge
    8. Februar 2015 23:35:13 CET
    Was eine Reihe wirklich kleiner Denkfehler doch alles auslösen kann... :D So im Nachhinein ein echter Lacher ;) Aber ich will mal nicht zu viel verraten!
  • 24. März 2015 23:58:41 CET
    [blockquote]Jan-David Fischbach said:
    Hallo alle zusammen Ich hab's einfach mal ausprobiert und ein Programm in Java geschrieben dieses braucht 800 Sek zur Bearbeitung des 100000 Zeichen String bei der Konfiguration k=2, l=2 die für mich die langwierigste sinnlogische darstellt. Ich arbeite außerdem nicht! In einem Rechenzentrum.[/blockquote]

    Tja verdammt mein C# programm braucht ungefähr 6mal solange...
    • Moderator
    • 391 Beiträge
    26. März 2015 12:59:31 CET
    [blockquote]Hannes K said:
    Tja verdammt mein C# programm braucht ungefähr 6mal solange...[/blockquote]

    Wenn der Faktor 6 für alle (größeren) Eingaben konstant ist, ist es nicht so tragisch. Und eine Lösung mit wirklich schwacher Laufzeit würde vermutlich noch länger laufen.
  • 7. April 2015 17:00:13 CEST
    [blockquote]Wolfgang Pohl said:
    [blockquote]Hannes K said:
    Tja verdammt mein C# programm braucht ungefähr 6mal solange...[/blockquote]

    Wenn der Faktor 6 für alle (größeren) Eingaben konstant ist, ist es nicht so tragisch. Und eine Lösung mit wirklich schwacher Laufzeit würde vermutlich noch länger laufen.[/blockquote]

    Da stimme ich definitiv zu, habe aber noch einen optimierbaren Teil gefunden und konnte meine Rechenzeit deutlich verkürzen.