Popular in Course
Popular in ComputerScienence
This 50 page Class Notes was uploaded by Vito Kilback on Wednesday September 23, 2015. The Class Notes belongs to CS265 at Drexel University taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/212461/cs265-drexel-university in ComputerScienence at Drexel University.
Reviews for AdvancedProgrammingToolsandTechniques
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/23/15
Interfacesilt Objective To discuss the considerations that must be addressed when designing an interface To illustrate these design issues with a simple yet useful example The essence of design is to balance competing goals and constraints Although there are many tradeoffs when one is writing a small self contained system the rami cations of particular choices remain within the system and affect only the individual programmer But when code is to be used by others decisions have wider repercussions gt The examples in these slides come from Brian W Kernighan and Rob Pike The Practice of Programming AddisonWesley 1999 Themes Interfaces what services and access are provided The interface is in effect a contract between the supplier and the customer The desire is to provide services that are uniform and convenient with enough functionality to be easy to use but not so much as to become unwieldy Themes Information Hiding What information is Visible and What is private An interface must provide straightfoward access to the components While hiding the details of the implementation so they can be changed Without affecting users Themes Resource Management who is responsible for managing memory and other resources Here the main problems are allocating and freeing storage and managing shared copies of information Themes Error handling who detects errors who reports them and how When an error is detected What recovery is attempted Topics CSV Comma separated values CSV Prototype library CSV A library for others CSV A C implementation Topics 0 Interface Principles 1 Hide implementation details 2 Choose a small orthogonal set of primitives 3 Don39t reach behind the user39s back 4 Do the same thing the same way everywhere Resource Management 1 Free a resource in the same layer that allocated it Abort Retry Fail 1 Detect errors at a low level handle them at a high level 2 Use exceptions only for exceptional situations Comma Separated Values CSV Anwm mdMampWuRMMmmmHWM m Each row is a line of text The elds on each line are separated by commas Text format used by many spreadsheets Exmnpb Good Student CSZ65 Advanced Programming Tools and Techniques A Bad Student CSZ65 Advanced Programming Tools and Techniques D Prototype Library plan to throw one away you will anyhow Frederick Brooks It is not usually until you ve built and used a version of the program that you understand the issues well enough to get the design right First version ignore many of the difficulties complete enough to be useful and to gain some familiarity with the problem Prototype char buf200 input line buffer gt char gt f1eld20 elds gt csvgetline read and parse line return eld count gt sample input quotLUquot8625quot1l4l998quotquot2l9PMquot40625 gt int csvgetlineFILE gt f1n int n eld char gt p q if fgetsbuf sizeofbuf n NULL return 1 n eld O for q bu pzsmokma quotanrquot NULL q NULL eldn eld unquotdp return n eld Prototype unquote remove leading and trailing quote gt char gt unquotechar gtl p if p0 39quot39 if pstrlenp l 39quot39 pstrlenpl 39039 p return p csvtest main test csvgetline function gt int mainvoid int i nf while nf csvgetlinestdin l for i O i lt nf i printfquot eldd s39nquot i eldi return 0 Decisions Made in Prototype Doesn t handle long input lines or lots of elds Lines terminated by newlines Fields are separated by commas and surrounding quotes removed no embedded quotes Input line not preserved overwritten when creating elds No data saved from one input line to the next Access to elds through global variable does not prevent access beyond last eld Decisions Made in Prototype Global variables make code unsuitable to multi threaded environment or interleaved calls Caller must open and close les Input and splitting are inextricably linked The return value is the number of elds each line must be split to compute this value Each decision is interwoven into the code There is no way to change any of these properties Without changing the code Speci cation Fields are separated by commas A eld may be enclosed in doublequotes A quoted eld may contain commas but not newlines A quoted eld may contain doublequotes represented by Fields may be empty represent an empty eld 663 and empty string both Leading and trailing White space is preserved Speci cation char csvgetlineFILE f reads one line from open input le f 0 assumes that input lines are terminated by r n rn or EOF returns pointer to line with terminator removed or NULL if EOF occurred line may be of arbitrary length returns NULL if memory limit exceeded line must be treated as readonly storage 0 caller must make a copy to preserve or change contents Speci cation char csv eldint n elds are numbered from O returns nth eld from last line read by csvgetline returns NULL if nlt0 or beyond last eld elds are separated by commas elds may be surrounded by such quotes are 939 66939 removed Within is replaced by and comma is not a separator in unquoted elds quotes are regular characters there can be an arbitrary number of fields of any length returns NULL if memory limit exceeded elds must be treated as readonly storage 0 caller must make a copy to preserve or change contents behavior unde ned if called before csvgetline is called Speci cation int csvn eldvoid returns number of elds on last line read by csvgetline behavior unde ned if called before csvgetline is called Header File extern char csvgetlineFILE f read next input line extern char csv eldint n return eld n extern int csvn eldv0id return number of elds Internal Variables enum NOMEM 2 out of memory signal static char line NULL input chars static char sline NULL line copy used by split static int maXline 0 size of line and sline static char eld NULL eld pointers static int max eld 0 size of eld static int n eld 0 number of elds in eld static char eldsep quotquot eld separator chars Internal Functions endo ine check for and consume r n rn or EOF static int endo ineFILE n int c reset set variables back to starting values static void resetvoid split split line into elds static int splitv0id advquoted quoted eld return pointer to next separator static char advquotedchar p Example abancd j39equotvajjlg9hquot line ab cdquotquotequotquotf39quotghquot39 eld0 ab39 eld1 cd39 eld2 6quotf eld3 quot eld4 gh39 1 2 3 4 5 Main Program include ltstdiohgt include ltstringhgt include ltstdlibhgt include ltasserthgt include quotcsvhquot csvtest main test CSV library gt int mainV0id 1nt 1 char gt line while line csvgetlinestdin NULL printfquot1ine s39nquot line for i O i lt csvn eldO i printfquot eldd s39nquot i csv eldi return 0 csvgetline csvgetline get one line grow as needed gt sample input quotLUquot8625quot1141998quotquot219PMquot40625 char gt csvgetlineFILE gt n 1nt1 c char gt newl gt news if line NULL allocate on rst call gt maxline maX eld 1 line char gt mallocmax1ine sline char gt mallocmaxline eld char gtW mallocmaX eldsizeof e1d0 if line NULL sline NULL eld NULL reset return NULL out of memory gt csvgetline cont for i0 cgetc nEOF ampamp endo ine nc i if 1 gt maxlinel grow line gt maxline 2 double current size gt newl char reallocline maxline news char gt reallocsline maxline if newl NULL news NULL reset return NULL line newl sline news line i c linei 39039 if split NOMEM reset return NULL out of memory gt return c EOF ampamp 1 0 NULL line reset reset set variables back to starting values static void resetv0id freeline frees1ine free e1d line NULL sline NULL eld NULL maxline maX eld n eld 0 freeNULL permitted by ANSI C endo ine endo ine check for and consume r n rn or EOF gt static int endo ineFILE gt n int c int e01 e01 c39r39 c39n39 if c 39r39 c getc n if c 39n39 ampamp c EOF ungetcc n read too far put c back gt return e01 split split split line into elds gt static int splitvoid char gt p newf char gt sepp pointer to temporary separator character gt int sepc temporary separator character gt n eld 0 if 1ine0 39O39 return 0 strcpysline line p sline do if n eld gt maX eld max eld 2 double current size gt 11ve char gt realloc eld maX eld sizeof eld0 if 11ve NULL return NOMEM eld newf if p Z 39quot39 sepp advquotedp skip initial quote gt else sepp p strcspnp eldsep sepc Z sepplol sepp0 39039 eldn eld p p Z sepp 1 terrninate eld gt while sepc 3939 return n eld advquoted advquoted quoted eld return pointer to next separator gt static char gt advquotedchar gt p int ij for i j 0 pH 39039 iaj ifpi ampamp pj quotquot copy up to next separator or O gt int k strcspnpj eldsep memmovepi pj k i k j k break pi pj pi 39039 return p j csv eld amp csvn eld csv eld return pointer to nth eld gt char gt csv eldint n if n lt 0 11 gt n eld return NULL return eldn csvn eld return number of elds gt int csvn eldvoid return n eld C Version Class CSV Use C strings handles storage management issues Use C vectors to store elds Use Class mechanism for information hiding Public Interface class Csv read and parse commaseparated values sample input quotLUquot8625 1141998 219PM 40625 public Csvistreamamp n cin string sep n n eldsepsep int getlinestringamp string get eldint n int getn eldO const return n eld Private Interface private istreamamp n input le pointer string line input line vect0rltstringgt eld eld strings int n eld number of elds string eldsep separator characters int split int endo inechar int advplainconst stringamp line stringamp d int int advquotedconst stringamp line stringamp d int Main Program Csvtest main test Csv class int mainV0id string line Csv csv while csvgetlineline O cout ltlt quotline quot39 ltlt line ltltquot39nquot for inti O i lt csvgetn eld i cout ltlt quot e1dquot ltlt i ltlt quot ltlt csvget eldi ltlt quot39nquot return 0 Performanceilt Objective To learn when and how to optimize the performance of a program The rst principle of optimization is don t Knowing how a program will be used and the environment it runs in is there any bene t to making it faster gt The examples in these slides come from Brian W Kernighan and Rob Pike The Practice of Programming AddisonWesley 1999 Approach The best strategy it to use the simplest cleanest algorithms and data appropriate for the task Then measure performance to see if changes are needed Enable compiler options to generate the fastest possible code Assess What changes to the program will have the most effect pro le the code Make changes one at a time and reassess always retest to verify correctness Consider alternative algorithms Tune the code Consider a lower level language just for time sensitive components Topics A Bottleneck Timing and Pro ling time and clock algorithm analysis prof and gprof gCOV Concentrate on hot spots Strategies for speed Tuning the code A Bottleneck isspam example from the text Heavily used Existing implementation not fast enough in current environment Benchmark Pro le Tune code Change algorithm Timing In Unix environment time command Example time quieksort from Chapter 2 head 10000 lt usrsharedictW0rds shuf e gt in gee 0 sortl sort1c quicksortc time sortl lt in gt deVnull Algorithm Analysis Consider the asymptotic analysis of your program and the algorithms you are using For quicksort let Tn be the runtime as a function of the size of the input array the time will depend on the particular input array The eXpected runtime is nlogn If each partition roughly splits the array in half then the computing time Tn z 2Tn2 cn The worst case is nz If each partition splits the array into two pieces of unequal size in the extreme I and n1 Tn Tnl cn nZ Solving Recurrences By Repeated Substitution Tn 2Tn2 en 22Tn4 cn2 en 4Tn4 en en 22Tn22 Zen 222Tn23 Cn 22 Zen 23Tn23 3cn 2JTn2J jcn Suppose n 2k and Tl c gt Tn 2kT1 ken n cnlgn Solving Recurrences By Repeated Substitution Tn Tnl 11 TnZ Cnl en Tn3 CnZ Cnl en Tnj cnj1 n Suppose Tl c gt Tn Tnn1 cnn11 n T1 c23 n c12 n chcnn12 j1 Worst Case for Quicksort Modify the code to remove the random selection of the pivot This makes it possible to deterministically construct a worst case input this is why randomization was used The worst case will occur for sorted or reverse sorted input For sorted input the number of comparisons Qn as a function of input size satis es Qn Qn1 nL Q0 0 Qn nn12 What does Asymptotic Analysis mean for Actual Runtimes 0 If Tn nz Doubling the input size increases the time by a factor of 4 T2nTn c4n2 on2cn2 on2 which in the limit is equal to 4 on2 means lower order terms 0 If Tn nlogn Doubling the input size roughly doubles the time same as linear T2nTn canog2n onlognnlognonlogn canogn onlogncnlogn onlogn which in the limit is equal to 2 Empirical Con rmation Run and time quieksort Without random pivot on sorted inputs of size 10000 and 20000 and 40000 Compute the ratio of times to see if it is a factor of 4 What if random inputs are used Growth Rates and Limits Suppose Tn fn grows at same rate limitngm Tnfn c a constant gt O Actually this is not true there may be separate limsup and liminf but as a rst approximation you can View it is true Suppose Tn ofn grows slower limitIHm Tnfn 0 Suppose Tn 0fn grows faster limitlHoo Tnfn 00 Determining Growth Rate Empirically Time quicksort with a range of input sizes eg 1000 2000 3000 10000 Write a program that times sort for a range of inputs Use the clock function to time code inside a program T1000 T2000 T3000 T10000 plot times for range of input to Visualize Compute ratios to compare to known functions T100010002 T200020002 T10000100002 Does the ratio approach a constant go to 0 go to 00 Ie is is growing at the same rate faster or slower than the comparison function Obtaining Range of Times sortr 1000 10 1000 sorts and times sorted arrays of size 1000 2000 300010000 Pro ling With gprof Reports on time spent in different functions also gives number of times functions called Shows the hotspots gcc pg sortl c quicksortc o sortl sortl lt in40000 gt deVnull gprof sortl gmonout Pro ling With gcov Uses source code analysis provided by the compiler to analyze the number of times each statement in the source code is executed gcc fpro 1earcs ftestcoverage sortic quicksortic o sorti sorti 10 gcov sortic gcov quicksortic
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'