Index of /anton/lvas/effizienz-aufgabe09

Abgabe Effiziente Programme WS09/10

Sie können ein beliebiges Beispiel wählen.

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 wenig bringen.

Vorgegebene Aufgabe: uid2name

Vergleichen Sie auf der g0 die Laufzeit (besonders "user time") der folgenden beiden Befehle:

time ls -ln /var/mail
time ls -l  /var/mail

Der Unterschied in der Laufzeit kommt daher, dass die Version mit -n nicht die Accountnamen herausfinden muss, sondern stattdessen die numerische user-id ausgibt.

Bei unserem Beispiel geht es darum, das Herausfinden des Accountnamens zu beschleunigen.

Das Ausgangsprogramm ist uid2name.c, das eine auf das für uns Essentielle reduzierte Version des Befehls ls -l darstellt: Es liest eine Reihe von user-ids ein und gibt die zugehörigen Account-Namen aus. Damit wir nicht von eventuellen Änderungen in /etc/passwd betroffen sind, sondern vergleichbare Ergebnisse bekommen, verwenden wir einen Snapshot dieser Datei.

Die Eingabe für den Vergleich ist bench-input (ein Snapshot der user-ids in /var/mail). Mit make können Sie das Ausgangsprogramm bauen und vermessen, wobei die Messwerte auch in einem Verzeichnis von Resultaten abgelegt wird. Und zwar werden pro Messung zwei Zahlen ausgegeben: Die Menge des allokierten Speichers, und die Anzahl der verbrauchten Zyklen (user+system time). Wenn Sie das Programm optimieren, behalten Sie bitte diese Ausgaben bei und messen Sie ab und zu mit make (besonders dann die Version, die Sie präsentieren). Sie können sich dann auch die "Trainingszeiten" der anderen anschauen.

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/2009w 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 ]

`Termin/Anmeldung zur Präsentation`





Die Terminvergabe erfolgt, wenn die Termine feststehen, über unser
Web-Anmeldesystem.
Und zwar müssen Sie dabei folgendermaßen vorgehen:



 Eines der Mitglieder der Gruppe klickt auf "Gruppe bilden" und
trägt die Matrikelnummer seiner Partner ein (zur Gruppengröße siehe unten).

 Wenn die Gruppe gebildet ist, sollte eines der Gruppenmitglieder
auf "Abgabegespräche anzeigen" und "Termine anzeigen" klicken, um
sich dort zum ersten Präsentationstermin anzumelden.



Im WS 2009/2010 ist im Normalfall eine Gruppengröße von fünf Personen
vorgesehen.  Wenn Sie eine andere Gruppengröße bilden wollen,
schreiben Sie ab 19.11. an
studass@complang.tuwien.ac.at.  Beachten Sie
allerdings, dass die Anzahl der Termine begrenzt ist, sodass wir nur
eine begrenzte Zahl kleinerer Gruppen akzeptieren können.


Anton Ertl

 Name                    Last modified      Size  Description
 Parent Directory                             -   
 Makefile                13-Nov-2009 13:01  230   
 bench-input             12-Nov-2009 20:12  3.4K  
 uid2name                13-Nov-2009 00:19   11K  
 uid2name.c              12-Nov-2009 23:42  1.3K