UAF CS 311 - Tables in Various Languages External Data

Unformatted text preview:

Tables in Various LanguagesExternal DataCS 311 Data Structures and AlgorithmsLecture SlidesFriday, December 4, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappellcontinued4 Dec 2009 CS 311 Fall 2009 2ReviewWhere Are We? — The Big ProblemOur problem for much of the rest of the semester: Store: a collection of data items, all of the same type. Operations: Access items [one item: retrieve/find, all items: traverse]. Add new item [insert]. Eliminate existing item [delete]. All this needs to be efficient in both time and space.A solution to this problem is a container.Generic containers: those in which client code can specify the type of data stored.4 Dec 2009 CS 311 Fall 2009 3Unit OverviewTables & Priority QueuesMajor Topics Introduction to Tables Priority Queues Binary Heap algorithms Heaps & Priority Queues in the C++ STL 2-3 Trees Other balanced search trees Hash Tables Prefix Trees Tables in various languagesIdea #1: Restricted TableIdea #2: Keep a Tree BalancedIdea #3: “Magic Functions”Lots of lousy implementations(part)4 Dec 2009 CS 311 Fall 2009 4ReviewTables in Various Languages — OverviewWe now take a brief look at Table usage in various languages, beginning with C++. C++ STL Sets: std::set. Maps: std::map. Other Tables. Set algorithms. Other Languages Python. Perl. Lisp.4 Dec 2009 CS 311 Fall 2009 5ReviewTables in Various Languages — C++ STL: std::setstd::set<valuetype> s; Table implementation. Key type & value type are the same. Duplicate keys not allowed. Implementation: balanced search tree. Iterators are bidirectional, not mutable (no “*iter = v;”). Iterators & references valid until item is erased.Operations Insert: member insert, takes item. Returns std::pair<iterator, bool>. Does nothing if key already present. Delete: Member erase, takes key or iterator. Retrieve: Member find, takes key. Returns iterator, which is container::end() if not found. Also, insert with hint, takes item and “hint” iterator. Returns iterator to item inserted. Exists so that inserter iterators work with std::set.4 Dec 2009 CS 311 Fall 2009 6ReviewTables in Various Languages — C++ STL: std::mapstd::map<keytype, datatype> m; Table implementation. Holds key-data pairs. Duplicate keys not allowed. Implementation: balanced search tree. Iterators are bidirectional, not mutable (no “*iter = v;”). But can do “(*iter).second = d;”. Iterators & references valid until item is erased.Operations As for std::set. Note: For a map, items and keys are different. Member insert takes an item; members erase and find take keys. Also has bracket operator: Say “m[key] = data;”. Inserts key into map if not present. Thus, can modify map; no const version. Do not use to determine whether a key is present; use find.4 Dec 2009 CS 311 Fall 2009 7ReviewTables in Various Languages — C++ STL: Other STL Tablesstd::multiset<valuetype> ms;std::multimap<keytype, datatype> mm; Like std::set & std::map, respectively, except that duplicate keys are allowed. Retrieve operations return either ranges or counts. Unlike std::map, std::multimap has no bracket operator.Hash Tables Not found in 1998 C++ Standard. Nonstandard versions abound. Upcoming revised standard should have Hash Tables.4 Dec 2009 CS 311 Fall 2009 8ReviewTables in Various Languages — C++ STL: Set AlgorithmsSTL Set Algorithms Deal with sorted sequences specified with iterators. Names: includes, set_union, set_intersection, set_difference, set_symmetric_difference. To send output to a container (set?) use an inserter.std::set_intersection(s1.begin(), s1.end(),s2.begin(), s2.end(),std::inserter(s3, s3.begin()));See usesetalgs.cpp, on the web page.4 Dec 2009 CS 311 Fall 2009 9Tables in Various Languages Other Languages — PythonPython includes a Table type, called a “dictionary” or “dict”. Dictionaries are used for many things in Python. They are used for function look-up, which is done at runtime. Dictionaries are Hash-Table based. Built-in types have hash functions provided. User-defined types can specify their own hash functions. Example:d = { 1:"one", "hi":"ho", "two":2 } # d is a dictx = d[1] # x should now be "one"if 1 in d:print "1 was found"for k in d: # Loop over keysprint("key:", k, "data:", d[k])continued4 Dec 2009 CS 311 Fall 2009 10Tables in Various Languages Other Languages — PerlPerl has had Tables for a long time. A Perl Table implementation is called a “hash”. These are Hash-Table based, of course. Example:$H{1} = "one"; # H is a hash$H{"hi"} = "ho";$H{"two"} = 2;print $H{"hi"}, "\n"; # Prints "ho"@A = keys %H; # Array of keys of hash Hforeach $K (keys %H) # Loop over keys{print "key: ", $K, " data: ", $H{$K}, "\n"}Note: The syntax is different in Perl version 6.4 Dec 2009 CS 311 Fall 2009 11Tables in Various Languages Other Languages — LispLisp has had Tables for a long, long time. Remember that Lisp uses Binary-Tree-based lists of lists for everything. Thus, we cannot expect Lisp to have a special Table type. There are, however conventions for expressing Tables as lists. One kind: property list. Constructed as “( key1 data1 key2 data2 key3 data3 )”. Example: “( 1 one hi ho two 2 )”. Another kind : association list. Something like this: “(( key1 data1 ) ( key2 data2 ))”. I’m told that the implementation uses memory a bit more efficiently, replacing pointers with values. Of course, these do not have very efficient operations. But they also predate much of the intense research on key-based look-up in the 1960’s. So we’ll forgive them. Maybe. Also note that, while there is no efficient built-in Table, one can certainly write one. And people have.4 Dec 2009 CS 311 Fall 2009 12The Rest of the CourseThat’s All …This ends the core material of CS 311.4 Dec 2009 CS 311 Fall 2009 13The Rest of the CourseFrom the First Day of Class: Course Overview — TopicsThe following topics will be covered, roughly in order: Advanced C++ Software Engineering Concepts Recursion Searching Algorithmic Efficiency Sorting Data Abstraction Basic Abstract Data Types & Data Structures: Smart Arrays &


View Full Document
Download Tables in Various Languages External Data
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Tables in Various Languages External Data and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Tables in Various Languages External Data 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?