CPS 1001.1Efficient Programmingÿ Designing and building efficient programs efficientlyrequires knowledge and practice Hopefully the programming language helps, it’s notintended to get in the way Object-oriented concepts, and more general programmingconcepts help in developing programs Knowledge of data structures and algorithms helpsÿ Tools of the engineer/scientist programmer A library or toolkit is essential, don’t reinvent the wheel Someone must build the tools Programming is not just art, not just science, not justengineeringCPS 1001.2See readwords.cppÿ This reads words, how c an we count different/unique words?tvector<string> list;string filename,word;cin >> filename;ifstream input(filename.c_str());CTimer timer;timer.Start();while (input >> word) {list.push_back(word);}timer.Stop();cout << "read " << list.size() << " words in ";cout << timer.ElapsedTime() << " seconds" << endl;CPS 1001.3Tracking different/unique wordsÿ We want to know how many times ‘the’ occurs Do search engines do this? D oes the number ofoccurrences of “basketball” on a page raise the priority of awebpage in some search engines?• Downside of this approach for search engines?ÿ Constraints on solving this problem We must read every word in the file (or web page) We must search to see if the word has been read before We must process the word (bump a count, store the word) Are there fundamental limits on any of these operations?Where should we look for data structure and algorithmicimprovements?CPS 1001.4Search: measuring performanceÿ How fast is fast enough?bool search(const tvector<string> & a,const string & key)// pre: a contains a.size() entries// post: return true if and only if key found in a{int k; int len = a.size();for(k=0; k < len; k++)if (a[k] == key) return true;return false;}ÿ C++ details: parameters? Return values? Vectors?ÿ How do we measure performance of code? Of algorithm? Does processor make a difference? PIII, G4, ???CPS 1001.5Structuring data: sortreadwords.cppÿ Search for a word using binary search Differences from sequential/linear search? What’s a precondition for binary search to work?ÿ How can we store new words so that binary search will work? Add to end of vector and sort the vector Add to end of vector and shift (down) until location found Advantages of one method over another?ÿ What about the C++ details in using a struct/class to storedata, how are comparisons made?CPS 1001.6Overloaded operatorsÿ In C++ we can define what operator == and operator < meanfor an object (and many other operators as well) This is syntactically convenient when writing code The C++ details can be cumbersome (see Howto E)ÿ In sortreadwords.cpp there are three overloaded operators What about > and >= ? What about printing, can we overload operator << ? Access to data for a Wcount object, simple because public,but what about a class?ÿ Overloaded operators are not necessary, syntactic sugar.CPS 1001.7Overloaded operators (continued)ÿ Typically operators need access to internal state of an object Relational operators for Date, string, BigInt? Where is “internal state”?ÿ For technical reasons sometimes operators should not bemember functions:BigInt b = enterBigValue();if (b < 2) …if (2 > b) … We’d like to use both if statements, only the first can beimplemented using BigInt::operator < (why?)ÿ Use helper member functions: equals, less, toString Implement overloaded operators using helpersCPS 1001.8From operators to templatesÿ What kind of object can we put in a vector? What kind of object can we sort? What kind of object can we print: cout << t <<endl;ÿ What is a vector? How is it different from the class Date? Container class, what does it contain? Why use it?ÿ Genericity is a good thing, program to a more abstract idearather than something more concrete Sorting function for sorting int, string, double, … In C++ genericity done with templates and sometimeswith inheritance; useful in different situationsCPS 1001.9Selection Sort: The Code (selectsort2.cpp)void SelectSort(tvector<int> & a)// pre: a contains a.size() elements// post: elements of a are sorted in non-decreasing order{int j,k,temp,minIndex,numElts = a.size();// invariant: a[0]..a[k-1] in final positionfor(k=0; k < numElts - 1; k++){ minIndex = k; // minimal element indexfor(j=k+1; j < numElts; j++){ if (a[j] < a[minIndex]){ minIndex = j; // new min, store index}}temp = a[k]; // swap min and k-th elementsa[k] = a[minIndex];a[minIndex] = temp;}}CPS 1001.10What changes if we sort strings?ÿ The parameter changes, the definition of temp changes Nothing else changes, code independent of t ype We can use features of language to capture independenceÿ We can have different versions of function for different arraytypes, with same name but different parameter lists Overloaded function: parameters different so compiler candetermine which function to c all Still problems, duplicated code, new algorithm means …?ÿ With function templates we replace duplicated codemaintained by programmer with compiler generated codeCPS 1001.11Creating a function templatetemplate <class Type>void SelectSort(tvector<Type> & a)// pre: a contains a.size() elements// post: elements of a are sorted in non-decreasing order{int j,k,minIndex,numElts = a.size();Type temp;// invariant: a[0]..a[k-1] in final positionfor(k=0; k < numElts - 1; k++){ minIndex = k; // minimal element indexfor(j=k+1; j < numElts; j++){ if (a[j] < a[minIndex]){ minIndex = j; // new min, store index}}temp = a[k]; // swap min and k-th elementsa[k] = a[minIndex];a[minIndex] = temp;}}ÿ When the user calls this code, differentversions are compiledCPS 1001.12Some template detailsÿ Function templates permit us to write once, use several timesfor several different types of vector Template function “stamps out” real function Maintenance i s s aved, code still large (why?)ÿ What properties must hold for vector elements? Comparable using < operator Elements can be assi gned to each otherÿ Template functions capture property requirements in code Part of generic programming Some languages support this better than othersCPS 1001.13Templates and function objectsÿ In a templated sort function vector elements must have certainproperties (as noted previously) Comparable using operator < Assignable using operator = Ok for int, string,
View Full Document
Unlocking...