Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Dop­pel­stun­de 3: Kon­zept „Abs­trak­te Da­ten­ty­pen“ [nur LF]

Ziel der Stun­de ist, dass die Schü­le­rin­nen und Schü­ler das grund­sätz­li­che Prin­zip von Abs­trak­ten Da­ten­ty­pen ver­ste­hen: Ein ADT ist ein Ver­bund von Ob­jek­ten, der be­stimm­te Ope­ra­tio­nen an­bie­tet. Zu die­sen Ope­ra­tio­nen müs­sen so­wohl Syn­tax als auch Se­man­tik de­fi­niert wer­den. Die Syn­tax wird be­reits durch die Me­tho­den­si­gna­tu­ren fest­ge­legt, was man z.B. durch eine abs­trak­te Ober­klas­se um­set­zen kann. Schwie­ri­ger ist, die Se­man­tik für einen ADT ein­deu­tig zu de­fi­nie­ren.

Der erste Teil des Auf­ga­ben­blatts 03_­lis­te_bench­mark.odt be­fasst sich genau damit: Was soll­te man bei einer Liste z.B. unter „vorne ein­fü­gen“ ver­ste­hen? Die Schü­le­rin­nen und Schü­ler wer­den auf­ge­for­dert, in Klein­grup­pen eine mög­lichst ein­deu­ti­ge Be­schrei­bung des Ver­hal­tens ei­ni­ger an­ge­ge­be­ner Me­tho­den zu for­mu­lie­ren. Wenn da­nach in einer Ple­nums­pha­se die Er­geb­nis­se ge­sam­melt wer­den, ist die Auf­ga­be der Lehr­kraft, die Er­geb­nis­se auf mög­li­che Lü­cken zu über­prü­fen und die Schü­le­rin­nen und Schü­ler zu einer mög­lichst voll­stän­di­gen und kor­rek­ten Be­schrei­bung zu lei­ten.

Im nächs­ten Teil wer­den dem Kurs mit dem BlueJ-Pro­jekt 03_­lis­ten­va­ri­an­ten_bench­mark ver­schie­de­ne Im­ple­men­ta­tio­nen vor­ge­legt. Es han­delt sich dabei um ein­fach ver­ket­te­te Lis­ten, ein­mal in ite­ra­ti­ver Form und ein­mal re­kur­siv. Zudem eine ein­fach ver­ket­te­te Liste mit einem Ver­weis auf das letz­te Ele­ment und eine Liste, die in­tern durch ein Array re­prä­sen­tiert wird. Eine Ei­gen­schaft von ADTs ist, dass es ver­schie­de­ne Im­ple­men­ta­tio­nen geben kann, die sich in Lauf­zeit- und Spei­cher­ef­fi­zi­enz un­ter­schei­den. Daher kann man mit der Bench­mark-Klas­se die ver­schie­de­nen Lis­ten­va­ri­an­ten in un­ter­schied­li­chen An­wen­dungs­sze­na­ri­en ver­wen­den und je­weils un­ter­su­chen, wie sich die Lauf­zeit und der Spei­cher­be­darf ent­wi­ckeln.

Auf­ga­be der Kurs­mit­glie­der ist, die Aus­ga­be der Bench­mark-Auf­ru­fe z.B. in einer Ta­bel­len­kal­ku­la­ti­on zu un­ter­su­chen (und ggf. zu vi­sua­li­sie­ren). Es ist dabei von Vor­teil, wenn man nicht nur den Ge­samt­spei­cher­be­darf bzw. die -lauf­zeit be­trach­tet, son­dern die Werte durch die An­zahl der Ele­men­te di­vi­diert. Damit zei­gen sich die Un­ter­schie­de der Grö­ßen­ord­nung deut­li­cher. Es zei­gen sich Un­ter­schie­de zwi­schen den ver­schie­de­nen Im­ple­men­ta­tio­nen, die im An­schluss durch einen Ver­gleich der Quell­codes er­klärt wer­den kön­nen.

Tech­ni­sche An­mer­kun­gen: Der Spei­cher­be­darfs-Bench­mark wird auf etwas un­kon­ven­tio­nel­le Art und Weise aus­ge­führt. Der Grund hier­für ist, dass die Java Vir­tu­al Ma­chi­ne mit der Op­ti­on „‑ja­vaa­gent“ aus­ge­führt wer­den muss, um die Si­ze­Of-Bi­blio­thek ein­zu­bin­den. Diese ver­wen­det die Java-API „In­stru­men­ta­ti­on“, die seit Java 5 ver­füg­bar ist. Um eine feh­ler­träch­ti­ge Än­de­rung der BlueJ-Kon­fi­gu­ra­ti­on zu ver­mei­den, wurde ent­schie­den, dass statt­des­sen aus dem Pro­gramm her­aus ein neuer Java-Pro­zess ge­star­tet wird, des­sen Kon­so­len­aus­ga­be ge­parst wird.

Das Pro­jekt 04_­set ent­hält kom­pi­lier­te .class-Da­tei­en, damit der Quell­code der Set-Va­ri­an­ten ver­bor­gen bleibt. Unter be­stimm­ten Um­stän­den kann es sein, dass die Java-Ver­si­on an Ihrer Schu­le nicht mit den kom­pi­lier­ten Da­tei­en kom­pa­ti­bel ist. In die­sem Fall soll­ten Sie das Pro­jekt 04_­set (mit Source­code) selbst noch ein­mal auf den Schul­rech­nern kom­pi­lie­ren und die dabei ent­ste­hen­den .class- und .ctxt-Da­tei­en an die Schü­le­rin­nen und Schü­ler aus­tei­len.

Als Er­wei­te­rung der Stun­de wird der ADT Set be­spro­chen. In der Prä­sen­ta­ti­on 04_­set.odp
wer­den drei un­ter­schied­li­che Im­ple­men­ta­ti­ons­an­sät­ze er­läu­tert und ihre Vor- und Nach­tei­le be­schrie­ben. Im An­schluss er­hal­ten die Schü­le­rin­nen und Schü­ler ein Pro­jekt mit drei kom­pi­lier­ten Im­ple­men­ta­tio­nen der Set. Sie sind nur als Set­Va­ri­an­teA, Set­Va­ri­an­teB und Set­Va­ri­an­teC be­nannt und der Quell­code ist nicht ein­seh­bar, so dass man daran nicht er­ken­nen kann, wel­che Klas­se wel­che Va­ri­an­te dar­stellt3 . Die Auf­ga­be für die Schü­le­rin­nen und Schü­ler ist nun, mit ihrem Wis­sen über die Un­ter­schie­de zwi­schen den vor­ge­stell­ten Va­ri­an­ten Bench­marks zu ent­wer­fen, mit denen man her­aus­fin­den kann, wel­che Klas­se für wel­che Va­ri­an­te steht. Bei der Im­ple­men­ta­ti­on des Bench­marks kann man sich an der Me­tho­de „mein­Test“ ori­en­tie­ren. Vor dem Auf­ruf der Me­tho­de ist die Set immer leer.

Als mög­li­che In­di­ka­to­ren kann man die fol­gen­den Bench­marks ver­wen­den:

  • Man fügt erst ein paar Zah­len von 1 bis 10 ein und dann die Zahl 1.000.000 – hier soll­te der Spei­cher­be­darf der Bit­vek­tor-Set sprung­haft an­stei­gen, wo­durch man diese iden­ti­fi­ziert hat.
    • Al­ter­na­tiv: Man fügt zu­erst die große Zahl ein und dann be­lie­big viele klei­ne­re Zah­len. Der Spei­cher­be­darf wächst jetzt nicht mehr.
  • Man fügt z.B. die Zah­len von 1 bis 100.000 ein und misst die Lauf­zeit. Der Zeit­be­darf der Set, die ein­fach eine Ar­ray­List ver­wen­det, steigt für jedes wei­te­re Ele­ment li­ne­ar an. In der Summe er­gibt sich hier eine qua­dra­ti­sche Lauf­zeit, wo­durch man diese iden­ti­fi­ziert hat.
  • Die ver­blie­be­ne Set-Im­ple­men­ta­ti­on muss dem­nach die Hash­ta­ble-Im­ple­men­ta­ti­on sein. Hier soll­te man fest­stel­len, dass der Spei­cher­be­darf etwa li­ne­ar mit der An­zahl der Ele­men­te wächst und die Lauf­zeit – mit Aus­nah­men beim Re­ha­shing – kon­stant ist.

 

3 Lei­der kann man in BlueJ wei­ter­hin Ob­jek­te der Klas­se auf die Ob­jekt­leis­te zie­hen und mit der „In­spi­zie­ren“-Funk­ti­on die pri­va­ten At­tri­bu­te ein­se­hen. Dies ist aber nicht Sinn der Auf­ga­be und soll­te un­ter­bun­den wer­den.

 

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][187 KB]

 

Wei­ter zu DS 4: ADT Stack