Compsci 100e 5.1 Data and Information How and why do we organize data? Differences between data and information? What about knowledge? Compsci 100e 5.2 Organizing Data: ideas and issues ! Often there is a time/space tradeoff ! If we use more space (memory) we can solve a data/information problem in less time: time efficient ! If we use more more time, we can solve a data/information problem with less space: space efficient ! Search v Store: repeating the same thing again … ! We’re not “smart” enough to avoid the repetition • Learn new data structures or algorithms! ! The problem is small enough or done infrequently enough that being efficient doesn’t matter ! Markov illustrates this (next assignment) Compsci 100e 5.3 Map: store pairs of (key,value) ! Search engine: web pages for “clandestine” ! Key: word or phrase, value: list of web pages ! This is a map: search query->web pages ! DNS: domain name duke.edu ! IP: 152.3.25.24 ! Key: domain name, value: IP address ! This is a map: domain name->IP address ! Map (aka table, hash) associates keys with values ! Insert (key,value) into map, iterate over keys or pairs ! Retrieve value associated with a key, remove pair Compsci 100e 5.4 Maps, another point of view ! An array is a map, consider array arr ! The key is an index, say i, the value is arr[i] ! Values stored sequentially/consecutively, not so good if the keys/indexes are 1, 100, and 1000, great if 0,1,2,3,4,5 ! Time/space trade-offs in map implementations, we’ll see more of this later ! TreeMap: most operations take time log(N) for N-elements ! HashMap: most operations are constant time on average • Time for insert, get, … doesn’t depend on N (wow!) ! But! Elements in TreeMap are in order and TreeMap uses less memory than HashMapCompsci 100e 5.5 Map (foreshadowing or preview) ! Any kind of Object can be inserted as a key in a HashMap ! But, performance might be terrible if hashValue isn’t calculated well ! Every object has a different number associated with it, we don’t want every object to be associated with 37, we want things spread out ! Only Comparable object can be key in TreeMap ! Basically compare for less than, equal, or greater ! Some objects are naturally comparable: String, Integer ! Sometimes we want to change how objects are compared ! Sometimes we want to invent Comparable things Compsci 100e 5.6 Traceroute: where’s the map here? traceroute www.cs.dartmouth.edu traceroute to katahdin.cs.dartmouth.edu (129.170.213.101), 64 hops max, 1 lou (152.3.136.61) 2.566 ms 2 152.3.219.69 (152.3.219.69) 0.258 ms 3 tel1sp-roti.netcom.duke.edu (152.3.219.54) 0.336 ms 4 rlgh7600-gw-to-duke7600-gw.ncren.net (128.109.70.17) 184.752 ms 5 rlgh1-gw-to-rlgh7600-gw.ncren.net (128.109.70.37) 1.379 ms 6 rtp11-gw-to-rpop-oc48.ncren.net (128.109.52.1) 1.840 ms 7 rtp7600-gw-to-rtp11-gw-sec.ncren.net (128.109.70.122) 1.647 ms 8 dep7600-gw2-to-rtp7600-gw.ncren.net (128.109.70.138) 2.273 ms 9 internet2-to-dep7600-gw2.ncren.net (198.86.17.66) 10.494 ms 10 ge-0-1-0.10.nycmng.abilene.ucaid.edu (64.57.28.7) 24.058 ms 11 so-0-0-0.0.rtr.newy.net.internet2.edu (64.57.28.10) 45.609 ms 12 nox300gw1-vl-110-nox-internet2.nox.org (192.5.89.221) 33.839 ms 13 … 14 … 15 border.ropeferry1-crt.dartmouth.edu (129.170.2.193) 50.991 ms 16 katahdin.cs.dartmouth.edu (129.170.213.101) 50.480 ms Compsci 100e 5.7 John von Neumann “Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.” “There's no sense in being precise when you don't even know what you're talking about. “ “There are two kinds of people in the world: Johnny von Neumann and the rest of us.” Eugene Wigner, Noble Physicist Compsci 100e 5.8 Interface at work: Frequencies.java ! From recitation: key is a string, value is # occurrences ! Code below is slightly modified version of recitation code ! What clues for prototype of map.get and map.put? ! What if a key is not in map, what value returned? ! What kind of objects can be put in a map? ! Kinds of maps? for(String s : words) {! s = s.toLowerCase();! Integer count = map.get(s);! if (count == null){! map.put(s,1);! }! else{! map.put(s,count+1);! }! }Compsci 100e 5.9 Coding Interlude: FrequenciesSorted ! Nested classes in FrequenciesSorted ! WordPair: combine word and count together, why? • ! WPFreq: allows WordPair objects to be compared by freq • ! How are WordPair objects created? ! In doFreqsA is the comparable-ness leveraged? ! What about in sorting? ! Alternative in doFreqsB ! Use TreeMap, then ArrayList then sort, why? ! Is comparable-ness leveraged? Sorting? Compsci 100e 5.10 What can an Object do (to itself)? ! http://www.cs.duke.edu/csed/java/jdk1.6/api/index.html ! Look at java.lang.Object ! What is this class? What is its purpose? ! toString() ! Used to print (System.out.println) an object ! overriding toString() useful in new classes ! String concatenation: String s = "value "+ x; ! Default is basically a pointer-value Compsci 100e 5.11 What else can you do to an Object? ! equals(Object o) ! Determines if guts of two objects are the same, must override, e.g., for using a.indexOf(o) in ArrayList a ! Default is ==, pointer equality ! hashCode() ! Hashes object (guts) to value for efficient lookup ! If you're implementing a new class, to play nice with others you must ! Override equals and hashCode ! Ensure that equal objects return same hashCode value Compsci 100e 5.12 Objects and values ! Primitive variables are boxes ! think memory location with value ! Object variables are labels that are put on boxes String s = new String("genome"); String t = new String("genome"); if (s == t) {they label the same box} if (s.equals(t)) {contents of boxes the same} s t What's in the boxes? "genome" is in the boxesCompsci 100e 5.13 Objects, values, classes ! For primitive types: int, char, double, boolean ! Variables have names and are themselves boxes (metaphorically) ! Two int variables assigned 17 are equal with == ! For object types: String, ArrayList, others ! Variables have names and are labels for boxes ! If no box assigned, created, then label applied to null ! Can assign
View Full Document