Data and InformationOrganizing Data: ideas and issuesMap: store pairs of (key,value)Maps, another point of viewMap (foreshadowing or preview)Traceroute: where’s the map here?John von NeumannInterface at work: Frequencies.javaCoding Interlude: FrequenciesSortedWhat can an Object do (to itself)?What else can you do to an Object?Objects and valuesObjects, values, classesAnatomy of a classDavid ParnasParnas on re-inventionDavid Parnas (entry in Wikipedia)Tomato and Tomato, how to codeCompsci 100e5.1Data and InformationHow and why do we organize data? Differences between data and information?What about knowledge?Compsci 100e5.2Organizing Data: ideas and issuesOften there is a time/space tradeofIf we use more space (memory) we can solve a data/information problem in less time: time efficientIf we use more more time, we can solve a data/information problem with less space: space efficientSearch 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 100e5.3Map: store pairs of (key,value)Search engine: web pages for “clandestine”Key: word or phrase, value: list of web pagesThis is a map: search query->web pagesDNS: domain name duke.edu IP: 152.3.25.24Key: domain name, value: IP addressThis is a map: domain name->IP addressMap (aka table, hash) associates keys with valuesInsert (key,value) into map, iterate over keys or pairsRetrieve value associated with a key, remove pairCompsci 100e5.4Maps, another point of viewAn array is a map, consider array arrThe 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,5Time/space trade-ofs in map implementations, we’ll see more of this laterTreeMap: most operations take time log(N) for N-elementsHashMap: 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 100e5.5Map (foreshadowing or preview)Any kind of Object can be inserted as a key in a HashMapBut, performance might be terrible if hashValue isn’t calculated wellEvery object has a diferent number associated with it, we don’t want every object to be associated with 37, we want things spread outOnly Comparable object can be key in TreeMapBasically compare for less than, equal, or greaterSome objects are naturally comparable: String, IntegerSometimes we want to change how objects are comparedSometimes we want to invent Comparable thingsCompsci 100e5.6Traceroute: where’s the map here?traceroute www.cs.dartmouth.edutraceroute 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 ms11 so-0-0-0.0.rtr.newy.net.internet2.edu (64.57.28.10) 45.609 ms12 nox300gw1-vl-110-nox-internet2.nox.org (192.5.89.221) 33.839 ms13 …14 …15 border.ropeferry1-crt.dartmouth.edu (129.170.2.193) 50.991 ms16 katahdin.cs.dartmouth.edu (129.170.213.101) 50.480 msCompsci 100e5.7John 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 PhysicistCompsci 100e5.8Interface at work: Frequencies.javaFrom 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 100e5.9Coding Interlude: FrequenciesSortedNested classes in FrequenciesSortedWordPair: 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 doFreqsBUse TreeMap, then ArrayList then sort, why?Is comparable-ness leveraged? Sorting?Compsci 100e5.10What can an Object do (to itself)?http://www.cs.duke.edu/csed/java/jdk1.6/api/index.htmlLook at java.lang.ObjectWhat is this class? What is its purpose?toString()Used to print (System.out.println) an objectoverriding toString() useful in new classes String concatenation: String s = "value "+ x;Default is basically a pointer-valueCompsci 100e5.11What 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 aDefault is ==, pointer equalityhashCode()Hashes object (guts) to value for efficient lookupIf you're implementing a new class, to play nice with others you mustOverride equals and hashCodeEnsure that equal objects return same hashCode valueCompsci 100e5.12Objects and valuesPrimitive variables are boxes think memory location with valueObject variables are labels that are put on boxesString 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}stWhat's in the boxes? "genome" is in the boxesCompsci 100e5.13Objects, values, classesFor primitive types: int, char, double, booleanVariables have names and are themselves boxes (metaphorically)Two int variables assigned 17 are equal with ==For object types: String,
View Full Document
Unlocking...