![[ICO]](/icons/blank.gif){kind=icon}
![[PARENTDIR]](/icons/back.gif){kind=icon}
![[TXT]](/icons/text.gif){kind=icon}
![[ ]](/icons/unknown.gif){kind=icon}
Wer nichts anderes vorhat, kann die unten vorgegebene Aufgabe für dieses Semester wählen.
Natürlich können Sie, wenn Sie wollen, auch die Implementierung eines anderen Problems optimieren; allerdings hat das einige Nachteile: Sie müssen einen Teil der Zeit Ihrer Präsentation für die Erklärung des Problems und des Algorithmus aufwenden, und die Ergebnisse sind nicht direkt vergleichbar. Der Vorteil (vor allem, wenn Sie einen späteren Termin wählen) ist, dass Sie nicht das wiederholen, was andere gemacht haben, oder ein langsameres Programm präsentieren.
Bereiten Sie eine 15-18-minütige Präsentation vor (am besten machen Sie einen Probelauf, damit sich die Präsentation auch sicher in der Zeit ausgeht). Da Sie dabei nicht soviel Zeit haben wie ich in der Vorlesung, präsentieren Sie die meisten Schritte nur im Überblick (also eventuell nur, wieviel er gebracht hat), und nur ein paar besonders interessante Schritte mit mehr Details. Besonders interessant sind u.a. die Schritte, die unerwartet viel oder unerwartet wenig bringen.
An sich muss das optimierte Programm für die gleiche Eingabe die gleiche Ausgabe produzieren wie das Originalprogramm, insbesondere für die gemessenen Testfälle. Sie können Sich auch überlegen, bestimmte Eingaben nicht korrekt zu verarbeiten, müssen das dann aber dokumentieren und begründen, warum Sie meinen, dass das sinnvoll ist.
Sie dürfen auch die Programmiersprache ändern.
Ausgeschlossen sind allerdings Optimierungen zu Trivialprogrammen
(z.B. if Eingabe=Benchmarkeingabe then print
Benchmarkausgabe), da dabei zuwenig zu lernen ist.
Das vorgegebene Programm ist in Java geschrieben und von dem in Pascal geschriebene Programm von Niklaus Wirth aus seinem Algorithmen-Lehrbuch abgeleitet (daher ist der Programmierstil auch nicht idiomatisches Java). Das Programm implementiert Backtracking mittels Rekursion.
Bei einem Aufruf mit
perf stat -e cycles -e instructions -e cache-misses -e branch-misses java nqueens 16erhielt ich auf der g0.complang.tuwien.ac.at die folgende Ausgabe:
14772512
Performance counter stats for 'java nqueens 16':
523831716202 cycles # 0.000 M/sec
801011053783 instructions # 1.529 IPC
237721 cache-misses # 0.000 M/sec
7488545479 branch-misses # 0.000 M/sec
155.371804861 seconds time elapsed
Das sind die Basiswerte, mit denen Sie Ihre Lösung vergleichen sollten
(am Besten, indem Sie einen Speedup-Faktor angeben). Relevant sind
vor allem die Zyklen, die anderen Werte können aber zur Erklärung der
gemessenen Zyklen dienen.
Sie können Ihr Programm (und Doku dazu, z.B. Ihre Präsentation) im Web veröffentlichen (wird nicht beurteilt), und zwar indem Sie auf /nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-abgaben/2014w ein Verzeichnis anlegen und Ihre Dateien in diesem Verzeichnis ablegen.
Aufgaben vom [WS02/03 | WS03/04 | WS04/05 | WS05/06 | WS06/07 | WS07/08 | WS08/09 | WS09/10 | WS10/11 | WS11/12 | WS12/13 | WS13/14 ]
9.1., 16.1., 23.1.Die Terminvergabe erfolgt, über unser Web-Anmeldesystem. Und zwar müssen Sie dabei folgendermaßen vorgehen:
| Name | Last modified | Size | Description |
|---|---|---|---|---|
| Parent Directory | - | ||
| nqueens.java | 2014-11-12 17:42 | 1.7K | |
| nqueens.class | 2014-11-13 16:39 | 1.2K | |
| eightqueens.pascal | 2014-11-11 16:34 | 1.3K | |