Inheritance and InterfacesSingle inheritance in JavaComparable and ComparatorSetsUsing Both ArrayList and SetsData processing examplePossible solutionsDropping Glass BallsGlass balls revisited (more balls)What is big-Oh about? (preview)More on O-notation, big-OhWhich graph is “best” performance?Big-Oh calculations from codeAmortization: Expanding ArrayListsSome helpful mathematicsRunning times @ 106 instructions/secCPS 100e5.1Inheritance and InterfacesInheritance models an "is-a" relationshipA dog is a mammal, an ArrayList is a List, a square is a shape, …Write general programs to understand the abstraction, advantages?void execute(Pixmap target) { // do something}But a dog is also a quadruped, how can we deal with this?CPS 100e5.2Single inheritance in JavaA class can extend only one class in JavaAll classes extend Object --- it's the root of the inheritance hierarchy treeCan extend something else (which extends Object), why?Why do we use inheritance in designing programs/systems?Facilitate code-reuse (what does that mean?)Ability to specialize and change behavior•If I could change how method foo() works, bar() is okDesign methods to call ours, even before we implement•Hollywood principle: don't call us, …CPS 100e5.3Comparable and ComparatorBoth are interfaces, there is no default implementationContrast with .equals(), default implementation?Contrast with .toString(), default?Where do we define a Comparator?In its own .java file, nothing wrong with thatPrivate, used for implementation and not public behavior•Use a nested class, then decide on static or non-static•Non-static is part of an object, access inner fieldsHow do we use the Comparator?Sort, Sets, Maps (in the future)Does hashing (future topic) have similar problems?CPS 100e5.4SetsSet is an unordered list of itemsItems are unique! Only one copy of each item in set!We will use two different implementations of setsTreeSetA TreeSet is backed up by a tree structure (future topic)Keeps items sorted (+)Slower than HashSets ?? (-) HashSet A HashSet is backed up by a hashing scheme (future topic)Items not sorted – should seem to be in random order (-)Faster than TreeSets ?? (+)CPS 100e5.5Using Both ArrayList and SetsYou may want to use a set to get rid of duplicates, then put the items in an ArrayList and sort them!Problem:Often data comes in the form of an arrayHow do we go from array to ArrayList or TreeSet?Problem:Often we are required to return an arrayHow do we go from a Collection such as an ArrayList or TreeSet to an array?Can do it the “hard” way with loops or iterators:one item at a timeOR:CPS 100e5.6Data processing exampleScan a large (~ 107 bytes) filePrint the 20 most frequently used words together with counts of how often they occurNeed more specification?How do you do it?CPS 100e5.7Possible solutions1. Use heavy duty data structures (Knuth)Hash tries implementationRandomized placementLots o’ pointersSeveral pages2. UNIX shell script (Doug Mclroy)tr -cs “[:alpha:]” “[\n*]” < FILE | \sort | \uniq -c | \sort -n -r -k 1,1 | \head -20•Which is better?K.I.S.?CPS 100e5.8Dropping Glass BallsTower with N FloorsGiven 2 glass ballsWant to determine the lowest floor from which a ball can be dropped and will breakHow?What is the most efficient algorithm?How many drops will it take for such an algorithm (as a function of N)?CPS 100e5.9Glass balls revisited (more balls)Assume the number of floors is 100In the best case how many balls will I have to drop to determine the lowest floor where a ball will break?1. 12. 23. 104. 165. 176. 187. 208. 219. 5110. 100In the worst case, how many balls will I have to drop?1. 12. 23. 104. 165. 176. 187. 208. 219. 5110. 100If there are n floors, how many balls will you have to drop? (roughly)CPS 100e5.10What is big-Oh about? (preview)Intuition: avoid details when they don’t matter, and they don’t matter when input size (N) is big enoughFor polynomials, use only leading term, ignore coefficients y = 3x y = 6x-2 y = 15x + 44 y = x2 y = x2-6x+9 y = 3x2+4xThe first family is O(n), the second is O(n2)Intuition: family of curves, generally the same shapeMore formally: O(f(n)) is an upper-bound, when n is large enough the expression cf(n) is largerIntuition: linear function: double input, double time, quadratic function: double input, quadruple the timeCPS 100e5.11More on O-notation, big-OhBig-Oh hides/obscures some empirical analysis, but is good for general description of algorithmAllows us to compare algorithms in the limit•20N hours vs N2 microseconds: which is better?O-notation is an upper-bound, this means that N is O(N), but it is also O(N2); we try to provide tight bounds. Formally:A function g(N) is O(f(N)) if there exist constants c and n such that g(N) < cf(N) for all N > ncf(N)g(N)x = nCPS 100e5.12Which graph is “best” performance?CPS 100e5.13Big-Oh calculations from codeSearch for element in an array:What is complexity of code (using O-notation)?What if array doubles, what happens to time? for(int k=0; k < a.length; k++) { if (a[k].equals(target)) return true; }; return false;Complexity if we call N times on M-element vector?What about best case? Average case? Worst case?CPS 100e5.14Amortization: Expanding ArrayListsExpand capacity of list when add() calledCalling add N times, doubling capacity as neededWhat if we grow size by one each time?Item # Resizing costCumulative costResizing Cost per itemCapacity After add1 0 0 0 12 2 2 23-4 4 6 1.5 45-8 8 14 1.75 82m+1 - 2m+12 m+12m+2-2 around 2 2m+1CPS 100e5.15Some helpful mathematics1 + 2 + 3 + 4 + … + NN(N+1)/2, exactly = N2/2 + N/2 which is O(N2) why?N + N + N + …. + N (total of N times)N*N = N2 which is O(N2) N + N + N + …. + N + … + N + … + N (total of 3N times)3N*N = 3N2 which is O(N2)1 + 2 + 4 + … + 2N 2N+1 – 1 = 2 x 2N – 1 which is O(2N ) Impact of last statement on adding 2N+1 elements to a vector1 + 2 + … + 2N + 2N+1 = 2N+2-1 = 4x2N-1 which is O(2N) resizing + copy = total (let x = 2N)CPS 100e5.16Running times @ 106 instructions/secN O(log N) O(N) O(N log N)O(N2)100.000003 0.00001 0.000033 0.00011000.000007 0.00010 0.000664 0.10001,0000.000010 0.00100 0.010000 1.010,0000.000013 0.01000 0.132900
View Full Document
Unlocking...