[PDF] 252-0027 Einführung in die Programmierung 10.0 Generische

ArrayListalsParameterpublic void name(ArrayList name) { ... }Beispiel:SchreibenSie eineMethode, die alleSubstantive (fangenmitGrossbuchstabenan) auseinerArrayListentfernt// Removes all nouns from the given listpublic void removeNouns(ArrayList list) {...}6

ArrayListalsRückgabewert§EineListekannauchalsErgebniszurückgegebenwerden:ArrayListmethodName(params)§Oder auchpublic ArrayListmethodName(params)static ArrayListmethodName(params)public static ArrayListmethodName(params)§u.s.w.8

ArrayListMethodenadd(value)appends value at end of listadd(index, value)inserts given value just before the given index, shifting subsequent values to the rightclear()removes all elements of the listindexOf(value)returns first index where given value is found in list (-1 if not found)get(index)returns the value at given indexremove(index)removes/returns value at given index, shifting subsequent values to the leftset(index, value)replaces value at given index with given valuesize()returns the number of elements in listtoString()returns a string representation of the listsuch as "[3, 42, -7, 15]"12

ArrayList numbers = new ArrayList();Scanner input;input = new Scanner(new File("numbers.txt"));while (input.hasNextInt()) {intn= input.nextInt();numbers.add(n);}System.out.println(numbers);filterEvens(numbers);// Remove even numbersSystem.out.println(numbers);14

AndereÜbungen§SchreibenSieeineMethodereversedie die Reihenfolgeder ElementeeinerArrayListfürStrings umkehrt.§SchreibenSieeineMethodecapitalizeAdverbsdie alsParameter eineArrayListvon String Objektenentgegennimmtund jedesWort einesenglischenTextes, das mit"ly" endet, mitGrossbuchstabenschreibt.25

Übersicht§10.1 Einleitung§10.2 ArrayList§ArrayList§Wrapper Typen§10.3 Vergleichenvon Objekten§10.4 Mengen§10.5 Abbildungen§10.6 Iteratoren26

10.3 Vergleichenvon Objekten27

compareTofürString§Beispiel: in derStringKlassegibtesdie Methodepublic intcompareTo(Stringother)§EinAufrufsomeS.compareTo(otherS) liefert:einenWert < 0 wennsomeS"vor" otherSin der Ordnungsrelationist,einenWert > 0 wennsomeS"nach" otherSin der Ordnungsrelationist,oder0 wennsomeSund otherSin der Ordnungsrelation"gleich" sind29

Gebrauchvon compareTo§compareTokannimTest einerifAnweisunggebrauchtwerden.String a = "alice";String b= "bob";if (a.compareTo(b) < 0) { // true...}31

32Gebrauchvon compareToPrimitive TypeObjectsif (a < b) { ...if (a.compareTo(b) < 0) { ...if (a <= b) { ...if (a.compareTo(b) <= 0) { ...if (a == b) { ...if (a.compareTo(b) == 0) { ...if (a != b) { ...if (a.compareTo(b) != 0) { ...if (a >= b) { ...if (a.compareTo(b) >= 0) { ...if (a > b) { ...if (a.compareTo(b) > 0) { ...

34This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort. Implementa;on note: This implementa;on is a stable, adap;ve, itera;ve mergesortthat requires far fewer than n lg(n) comparisons when the input array is par;ally sorted, while offering the performance of a tradi;onal mergesortwhen the input array is randomly ordered. If the input array is nearly sorted, the implementa;on requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

§Fall 1: Die Elementeder ArrayListstellencompareToautomatischzurVerfügungArrayList list = new ArrayList();String = {"my", "dog", "has", "fleas"};for (inti= 0; i< s.length; i++) list.add(new String(s[i]));Collections.sort(list);System.out.println(list1);§Output: [dog, fleas, has, my]36

Siehtgut aus, aberwirdnichtübersetzt//javacExample7aa.java Example7aa.java:15: cannot find symbolsymbol: method sort(java.util.ArrayList)location: class java.util.CollectionsCollections.sort(list1);^1 error41

Comparablepublic interface Comparable {public intcompareTo(Eother);}§EineKlassekanndas Interface Comparableimplementierenund so einenatürlicheOrdnungfürihreExemplaredefinieren. §NatürlicheOrdnung: esgibtnureineOrdnungsrelation§WennwirmehrereRelationenzulassenwollendannwirdeskomplizierter43

Comparable§EinAufrufsomeE.compareTo(otherE) liefert:einenWert < 0 wennsomeE"vor" otherEin der Ordnungsrelationist,einenWert > 0 wennsomeE"nach" otherEin der Ordnungsrelationist,oder0 wennsomeEund otherEin der Ordnungsrelation"gleich" sind45

ComparableMusterpublic class nameimplements Comparable {...public intcompareTo(nameother) {...}}46

ComparableBeispielclass Word implementsComparable {String item;intposition;intcount;... //constructor(s)public intcompareTo(Wordotherword) {String compareItem= otherword.item;return (item.compareTo(compareItem));}}48

compareTound Collec*ons§AuchandereCollections nutzendieseMethode.§Java's TreeSet/Mapbrauchtintern compareToum eineOrdnungzudefinierenSet set = new TreeSet();for (String s: a) {set.add(s);}System.out.println(s);// [al, bob, cari, dan, mike]51

Aufgabe§Sieerinnernsichan die KlassePoint52

KlassePointpublic class Point {private intx;private inty;// Constructs a Point at the given x/ylocation.public Point(intinitialX, intinitialY) {x= initialX;y= initialY;}// Methods...}53

Aufgabe§Sieerinnernsichan die KlassePoint§Wirwollendie Point Exemplaresortieren§point1 "vor" point2 wenn§point1.x < point2.x oder§point1.x == point2.x und point1.y < point2.y§point1 "nach" point2 wenn§point1.x > point2.x oder§point1.x == point2.x und point1.y > point2.y§sonstpoint1 "gleich" point255

compareTofürPoint§EinAufrufA.compareTo(B) liefert:einenWert < 0wennA "vor" B in derOrdnungsrela 0wennA "nach" B in derOrdnungsrela ComparableBeispielpublic class Point implements Comparable {private intx;private inty;}57

ComparableBeispielpublic class Point implements Comparable{private intx;private inty;// unchanged // must implement compareTo(Point other)}58

ComparablefürPoint// sort by x and break ties by ypublic intcompareTo(Point other) {if (x < other.x) {return -1;} else if (x > other.x) {return 1;} else if (y < other.y) {return -1; // same x, smaller y} else if (y > other.y) {return 1; // same x, larger y} else {return 0; // same x and same y}}59

compareToDiskussion§Subtraktion-Manchmalkannman durchSubtraktionentsprechenderWerteden fürcompareTogewünschtenRückgabewerterhalten:// sort by x and break ties by ypublic intcompareTo(Point other) {if (x != other.x) {return x -other.x; // different x} else {return y -other.y; // same x; compare y}}60

compareToDiskussion§Subtraktion-Manchmalkannman durchSubtraktionentsprechenderWerteden fürcompareTogewünschtenRückgabewerterhalten:§Die Idee:§if x > other.x,then x -other.x> 0§if x < other.x,then x -other.x< 0§if x == other.x,then x -other.x== 0§Achtung: DieserWegfunktioniertnichtfürreelleZahlen(doubles) abersieheMath.signum(double)61

Übersicht§10.4 Mengen§10.5 Abbildungen63

10.4 Mengen64

Beispiel§SchreibenSie einProgrammdas "einegrosseAnzahl" von Werteneinliestund dannin der umgekehrtenReihenfolgeausgibt§Grosse Anzahl: 100'000, 1'000'000, ....§KeineweiterenOperationen(fürdieses Beispiel)§WirwolleneineKlasseder Collection Frameworks benutzen§WollenoffenhaltenwelcheKlasseverwendetwerdensoll65

Beispiel--Fortsetzung§Nehmenwiran wirhabenesmitIntegerWertenzutunpublic static void process(ArrayList c) {// get input// output in reverse order}§DieseMethodekannfürArrayList Examplareverwendetwerden§Aber istArrayListder besteTypfürdieseAufgabe§Was gibtesdennnoch?67

Java Collections Framework68<Collection<List<SetLinkedListArrayListTreeSet<SortedSetHashSet<MapTreeMap<SortedMapHashMap

List70

LinkedListMethodenadd(value)appends value at end of listadd(index, value)inserts given value just before the given index, shifting subsequent values to the rightclear()removes all elements of the listindexOf(value)returns first index where given value is found in list (-1 if not found)get(index)returns the value at given indexremove(index)removes/returns value at given index, shifting subsequent values to the leftset(index, value)replaces value at given index with given valuesize()returns the number of elements in listtoString()returns a string representation of the listsuch as "[3, 42, -7, 15]"72

KommtunsdieseListebekanntvor?73

ArrayListMethodenadd(value)appends value at end of listadd(index, value)inserts given value just before the given index, shifting subsequent values to the rightclear()removes all elements of the listindexOf(value)returns first index where given value is found in list (-1 if not found)get(index)returns the value at given indexremove(index)removes/returns value at given index, shifting subsequent values to the leftset(index, value)replaces value at given index with given valuesize()returns the number of elements in listtoString()returns a string representation of the listsuch as "[3, 42, -7, 15]"75

Beispiel--Fortsetzung§Nehmenwiran wirhabenesmitIntegerWertenzutunpublic static void process(List c) {// get input// print in reverse order}§DieseMethodekannfürArrayListund LinkedListExamplareverwendetwerden§WelcheKlasseistbesser?76

Das Kleingedruckte§LinkedList: get(index) brauchtO(n) Zeit§ArrayList: get(index) brauchtO(1) Zeit77All of the operations perform as could be expected for a doubly-linked list.Opera;ons that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.The size, isEmpty, get, [and] set [..] operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

PraktischeAnalyse§Müssendas LaufzeitverhaltenfürrealistischenInput messen§Was ist"realistischer" Input?§Zeitmessungennichteinfach§Java System hat vieleKomponenten(einigehabenwirnochgarnichtkennengelernt) und verschiedeneCompiler§EinfacheMessunggibtuns"end-to-end" Übersicht§System.currentTimeMillis()oderSystem.nanoTime()§Eingebaut78

System.currentTimeMillis()§Gibtdie Zeit(in ms) seit00:00 , 1. Januar1970.§Typdes Rückgabewertesistlong§EinandererBasistyp§WieintnurmiteinerDarstellungdie mehrBits (64) erfordert§Kannwiederholtaufgerufenwerdenum die Ausführungszeiteiner(genügendlangelaufenden) Methodezumessen79

System.nanoTime()The java.lang.System.nanoTime() method returns the current value of the most precise available system timer, in nanoseconds. The value returned represents nanoseconds since some fixed but arbitrary time (perhaps in the future, so values may be negative) and provides nanosecond precision, but not necessarily nanosecond accuracy. §Typdes Rückgabewertesistlong§Kannwiederholtaufgerufenwerdenum die Ausführungszeiteiner(genügendlangelaufenden) Methodezumessen80

ArrayList arrayList= new ArrayList();long startTime= System.nanoTime();for (inti= 0; i< 100000; i++) {arrayList.add(Integer.valueOf(i));}long endTime= System.nanoTime();long duration = endTime-startTime;System.out.println("ArrayListadd:" + duration);81

Beispiel--Fortsetzungpublic static void process(List c) {// get input// print in reverse order}§DieseMethodekannfürArrayListund LinkedListExamplareverwendetwerden§WelcheKlasseistbesser?82

Beispiel-Messungen§100'000 Integer Wertehinzufügenlist.add(Integer.valueOf(i))§Messungen§Durchschnittvon 4 Ausführungen(

Vorsicht!! )§Intel(R) Xeon(R) CPU E5-4640 0 @ 2.40GHz, OpenJDK (1.8.0_161-b14)83KlasseZeit (ns)LinkedList9'312'254ArrayList11'972'638

§ErnsthafteEvaluationenmüssenvieleAspekteberücksichtigen§MehrfacheAusführungdes selbenProgramms§Durchschnitt(arithmetisch, harmonisch, geometrisch)§k-out-of-N§Prozessorensindkomplex§SpeicherHierarchie§EchteClock Rate §Java Umgebungistkomplex85

Messungen§ArrayList(ms):86Time (ns)12'881'02711'416'02911'446'88112'146'617Time (ns)8'711'75510'547'6429'001'8888'987'733§LinkedList(ms): Einfügen/Entfernenam Anfanggehtsehrschnellin einerLinkedList -beivielenanderenOperationengewinntdie ArrayListhaushoch

Beispiel§Input: Thomas Mann, Die Buddenbrooks, 1'602'177 Bytes§Quelle: ProjektGuttenberg§Lesender Datei, Einfügenin Collection§Intel(R) Xeon(R) CPU E5-4640 0 @ 2.40GHz, OpenJDK (1.8.0_161-b14)88KlasseZeit(ms)LinkedList662ArrayList615

Java Collections Framework93<Collection<List<SetLinkedListArrayListTreeSet<SortedSetHashSet<MapTreeMap<SortedMapHashMap

SetObjekteList list = new ArrayList();...Set set1 = new TreeSet(); // emptySet set2 = new HashSet(list);§Es gibtden Defaultkonstruktor(liefertdie leereMenge) und einenKonstrukor, der eineMengebasierendauf eineranderenCollection erstellt. 102

Set Methoden105add(value)adds the given value to the setcontains(value)returns trueif the given value is found in this setremove(value)removes the given value from the setclear()removes all elements of the setisEmpty()returns trueif the set's size is 0toString()returns a string such as "[3, 42, -7, 15]"

ArbeitenmitSetExemplarenList list = new ArrayList();...Set set1 = new TreeSet(list); Set set2 = new HashSet(list);§Oft wissenwirnichtwelcheArt Set am bestenist§Daher wollenwirunsereProgrammeflexibellassen§Verwendendes Interfaces alsTypfürParameter und Attribute/Variablebooleanmethod(Set s)108