The Priming Read Is Usually Placed as the First Step Within the Loop.
Loop Patterns
AuthorsOwen Astrachan Eugene Wallingford Department of Calculator Science Department of Informatics Duke University Academy of Northern Iowa Durham, NC 27708 Cedar Falls, IA 50614 ola@cs.duke.edu wallingf@cs.uni.edu
Permission is granted to make copies for PLoP'98.
Background
There are many ways to look at patterns. An especially useful way to think of patterns is every bit a tool for instruction. We don't use patterns blindly; we learn them. Patterns are all about learning successful techniques, agreement when and how to use them. At ChiliPLoP'98, a small group of computer science educators gathered to think about and write patterns appropriate for novices learning to program in the showtime two years of undergraduate didactics. (For more information or to become involved in this ongoing project, visit the unproblematic patterns web folio.)
The patterns contained here were commencement discussed and written as a role of the ChiliPLoP workshop. They are, we hope, the ancestry of what will be a pattern language for helping novice programmers construct loops. Writing loops is the ground for many of the issues students attempt to solve when writing programs in Algol-similar languages. (In functional languages such as Scheme, recursion is typically used for repetition instead of loops. Run across, for example, Roundabout, a design language for recursive programming that was workshopped at PLoP'97.)
We focused our initial efforts on identifying specific problems that students encounter when learning to write loops. This lead us to several specific patterns. At this point, they are merely rather loosely related, merely we hope that they serve as a useful starting point for a more all-encompassing documenting attempt.
- Loops for processing items in a collection
- Searching loops
- Linear Search
- Guarded Linear Search
- Processing all the items in a drove
- Process All Items
- Definite Process All Items
- Iterator Process All Items
- One Loop for Linear Structures
- Farthermost Values
- Process All Items
- Searching loops
- General loop coding
- Loop and a Half
- Polling Loop
- Loop Invariant
Linear Search
You are working with a collection or stream of objects.
How do yous find an object that meets a specific condition?
Suppose that you have a set of students, and you would like to find the first student with an "A" average. In the worst case, yous will look at the whole collection before finding your target. Simply, if you detect a match sooner, y'all would similar to terminate the search and work with the object that you found.
Therefore, construct a Process All Items loop, but provide a fashion to exit the loop early should you observe your target sooner.
Express your student search every bit:
for (i = 0; i < students.size(); i++) if (pupil[i].grade().isAnA()) intermission; // procedure student[i], who has an A
If information technology is possible that you will non find your target, be sure to practise a Guarded Linear Search.
Guarded Linear Search
You are doing a Linear Search.
How do you handle the possibility that no target may exist institute?
What happens if it is possible that no student has an "A" average? Your loop will expect at the entire collection and still not discover a target. Simply the code that follows the loop assumes that student[i] is the target.
Therefore, follow the loop with an Culling Activeness that treats the "non found" state of affairs as a special case.
Express your student search as:
for (i = 0; i < students.size(); i++) if ( student[i].form().isAnA() ) intermission; if (i < students.size()) // found information technology! // process student[i], who has an A else // handle the exception
[Resulting context...]
Process All Items
Y'all are writing code that manipulates a collection.
How do you process all of the items in the drove?
The collection might exist an array, a purse, a hashtable, a stream, or a file--in full general, items stored in some structure and made attainable to the programmer through some drove/iterator interface. Yous desire to process all of the items in an identical manner.
Yous may demand to process all of the items considering in the worst example all items must be processed (Linear Search), or considering all items must be processed even in the best instance, in order to ensure correctness (Farthermost Values).
There are two kinds of process-all-items loops: a definite loop that uses indexing when the number of indexable items in a collection is known in advance, and an iterating loop when an iterating interface is used to admission the items in a collection sequentially.
Therefore choose the appropriate loop and loop pattern for processing all the items in the collection one time.
Definite Process All Items
You are writing a Procedure All Items loop for an indexable collection, the number of items in the collection tin be determined but (in constant time) and indexing is abiding time.
How do you access every indexable item?
The drove might be a vector or a cord where the number of elements in the collection can be determined by a function call, or the number of items might be some other variable associated with the collection, east.yard., as a parameter to a function or a field in a grade.
Therefore use a Definite Procedure All Items for loop to touch evey element in the collection.
Example
The items are stored in a vector. Use a definite loop to procedure all the items, even for algorithms similar Linear Search. In C++:
for(int m=0; k < five.size(); k++) { procedure v[yard] } Iterator Process All Items
You are writing a Process All Items loop for a drove that uses an iterator interface or when constant time indexing of the collection is not possible.How do you lot access every item in the collection?
The items may exist stored in a collection with a standard iterator interface, e.g., a Java enumeration.
The items may be stored in a unproblematic linked list where there is no explicit iterator interface, just (iterating) links must be followed.
Therefore use an iterator process all items while loop that tests the iterator to see if information technology is finished.
Examples
In Java the items may exist accessible via the standard Java 1.i Enumeration interface. Hashtable table = new Hashtable(); // code to put values in tabular array Enumeration e = table.keys(); while (e.hasMoreElements()) { process(table.get(due east.nextElement())); } In C++ processing a linked list requires an iterating pointer variable:
Node* ptr = outset; while (ptr != Nada) { process(ptr->info); ptr = ptr->next; }
The Iterator pattern is widely known from the GOF patterns book, just is mentioned as an idiom in Coplien's Avant-garde C++
Loop and a Half
Yous are writing a Process All Items loop.
How exercise yous construction the loop when the number of items in the collection isn't known in advance and the items are provided one-at-a-time?
For example, you might be reading values from the keyboard or from a file. In general, you are processing all items until a sentinel is reached. The scout may be end-of-file, a valid value for the blazon of data being read, or an exception.
The loop requires priming to read/get the first value, a loop guard to test for the sentinel, and another read/go inside the loop. This leads to duplicate code for the read/get and makes the loop body harder to understand since it turns a read-and-process loop into a procedure-and-read loop.
Therefore, utilize a while-true loop with a break in the loop body to avert indistinguishable code and to match your intuition that the loop is a read-and-procedure loop.
For instance, consider pseudocode for a lookout man loop:
read value while (value != sentinel) process value read value
This can be rewritten as
while (true) read value if (value == sentinel) break; process value
Although the break is essentially a goto and thus violates a catechism of structured programming, it results in lawmaking that information technology easier to develop Roberts. Because in that location is no code duplication the code should be easier to maintain and easier to understand --- see Assign Variables One time and Local Variables Reassigned Above Their Uses.
[Resulting Context: Patterns for writing (compound) Boolean expressions.]
Polling Loop
You are writing a program that asks the user to enter a data value.
How do you poll until the user enters a valid data item?
For example, suppose that we want the user to enter a legal form, between 0 and 100 inclusive.
Many languages provide a exercise...while... construct that allows directly testing of a value subsequently entry. For example:
do { cout << "Enter a grade between 0 and 100, inclusive: "; cin >> grade; } while (class < 0 || grade > 100) This solution gives the same prompt on all requests, and then the user may be confused by the repetition. The exam is negative, which requires students to use DeMorgan'southward laws to write the status.
Instead, you could follow the information entry with an explicit validation loop:
cout << "Enter a grade between 0 and 100, inclusive: "; cin >> form; while (grade < 0 || grade > 100) { cout << "Sorry! That is an illegal value." << endl; cout << "Enter a course between 0 and 100, inclusive: "; cin >> course; } This solution replicates the prompt code. We can lessen the negative event by making the prompt a procedure call. But, the test is all the same written in the negative, which is difficult to do--and undo, for the reader who wants to know what the legal values are.
Both of these solutions stop processing when the negative condition fails, and the prompting sequence is hard.
Therefore, employ a loop and a half. Write a positive condition that stops the repetition when the user enters a legal value.
So, yous might solve your course-inbound equally:
while (one) { cout << "Enter a grade between 0 and 100, inclusive: "; cin >> form; if (grade >= 0 && grade <= 100) pause; cout << "Sorry! That is an illegal value." << endl; } If the condition that stops the loop is compound (or always??), Utilize a Function for a Compound Boolean.
Extreme Values
You lot are writing lawmaking to find extreme values, for example the maximum and minimum in a drove or sequence of values.
What kind of loop do you lot use and how do you initialize the variables that rails the extreme values?
You must procedure all items in the collection to ensure that the correct extreme values are found. The aforementioned forces are at play that help to identify a Definite Process All Items and a Iterator Process All Items loop.
The principle difficulty in writing code to find extreme values is determining initial values for the variables that represent the farthermost value and so far e.chiliad., currentMin and currentMax. The invariant for currentMin is that it represents the minimal value of all the values processed and then far. The best method for establishing this invariant is to employ the first value of the collection for the initialization, merely this can atomic number 82 to the kind of indistinguishable lawmaking seen in the Loop and a Half pattern.
The range of values from which the extreme values are chosen is a strength that affects the algorithm/code. For case, if extreme values are chosen from integers or doubles (floating point numbers) in that location are largest and smallest values; finer in that location are values for infinity and negative infinity. For other types in that location may be no effective values for infinity, e.g., in choosing the largest or smallest string lexicogaphically at that place is no maximal cord value (at that place may be a smallest cord, usually the empty cord "" is less than any non-empty string).
Therefore, apply the appropriate Process All Items loop and initialize extreme values to the beginning value in the collection from which extreme values are adamant (care must exist taken if the collection is empty). If possible, utilise indices, pointers, or references rather than values of objects/variables, i.e., continue track of the index of the current minimum in an array rather than the electric current minimal value. The value tin can be determined from the index, arrow, or reference.
Examples
Find the largest and smallest values in a vector of strings in C++. Use a Definite Process All Items loop and initialize current min and max indexing variables to the outset value in the vector.
It'due south possible to write a generic office that returns the minimal value in a vector/array:
In Java this could be written equally follows:
You are finding the extreme values in a stream of string values using C++. The collection here uses an iterator interface, where the interface is the C++ convention of reading the stream and using the returned state of the stream to indicate when the iteration is finished.
The first values read, if whatever, are used to initialize the extreme values. Information technology is not possible to apply indexes or references to maintain the extreme values, and then the values themselves are stored.
There is duplicated lawmaking for reading values in the lawmaking fragment above. It's possible to avoid duplicated code when the range of values has effective values for positive and negative infinity.
Y'all are finding the extreme values in a stream of double values. Y'all desire to avoid duplicated reading code. Therefore, initialize current min and max to positive and negative infinity (and use <= and >= for comparisons).
Ane Loop for Linear Structures
You are writing Only Understood Code(Gabriel), code whose intent and correctness are not apparent.
How do y'all write code that processes data stored in a linear structure, such every bit an array, list, or file?
Developing such lawmaking is non footling, because you call up that complex control structures are needed to implement the algorithm, or because of special cases.
Algorithmically, a problem may seem to call for multiple loops to match intuition on how control structures are used to programme a solution to the problem, but the data is stored sequentially, east.thou., in an array or a file. Programming based on command leads to more problems than programming based on structure.
Therefore, use the construction of the data to guide the programmed solution: one loop for sequential data with appropriately Guarded Conditionals(?) to implement the control.
The structure of the source of data is the guide for using this pattern, not the structure of how the data is processed or where data is written. For instance, in processing a file representing a black-and-white bitmap stored as run-length encoded zeros and ones, eastward.1000., v three iv represents 000001110000, the structure of the file dictates using one loop while the structure of the image dictates using ii loops. Use one loop because the information is stored in a file.
Examples
You are removing duplicated elements from a sorted array. At kickoff you may call back of writing nested loops: an outer loop to Process All Items and an inner loop to search past duplicated items (alternatively, search for a non-duplicated item). This arroyo can exist a trouble considering a Definite Process All Items loop is chosen for, simply the nested loop approach volition brand updating the indexing variable difficult. Instead, utilise only a Process All Items loop: one loop for linear structures:A more than elabore instance of Quicksort Partition is given in an appendix.
Loop Invariant/Loop Initialization
You are writing a loop whose termination/continuation conditions are determined by values of local variables.
How do you determine the initial values of the variables?
The name of each variable should indicate its role in the loop and the invariant holding that holds for the variable. A comment that expresses the invariant property should accompany each variable whose name does not immediately convey the invariant belongings.
Explicitly identifying the invariant for each variable used in the loop is a start. The invariant helps determine what the initial values are since the invariant must be truthful the first fourth dimension the loop test is evaluated. See the example of removing duplicated elements in the One Loop for Linear Structures pattern.
For example, You are writing code to find the date on which Thanksgiving, the fourth Thursday in November, occurs. Yous decide to start on the first day of the month, and iterate through days counting Thursdays. Your first loop is:
You recognize a problem with this solution: d is incremented as the last statement in the loop so it will exist one day after Thanksgiving when the loop terminates. Yous may make up one's mind to motility d++ earlier the if statement in the loop, or to rewrite the if argument every bit an if/else statement. The problem here is non with the loop torso per se, it is with the initialization of the variable thursdayCount; what does thursdayCount count?
Therefore yous must explicitly place what is tracked/counted, what is the invariant property that holds for thursdayCount. In this case yous want thursdayCount to exist the number of Thursdays in November on or earlier Date d. Yous attempt to verify that the invariant holds the first time the loop test is evaluated and encounter that information technology will not hold when November 1 is a Thursday. You lot could initialize based on what 24-hour interval of the week Nov one falls on every bit shown below, but you lot want to avoid special cases.
To ensure that the invariant holds the showtime time the loop test is evaluated, you initialize d to the last mean solar day in Oct rather than the kickoff twenty-four hour period of November:
External Patterns
We refer to each the post-obit patterns in one or more patterns above. Some are patterns that we intend write in the future, and others are patterns documented by other authors. Links to on-line versions of the patterns are provided where bachelor.
- Apply a Office for a Compound Boolean
- Problem: Even simple Boolean expressions can exist hard to read. More complex Booleans can exist downright intimidating. They interrupt the flow of lawmaking, and readers often cannot determine their meanings very easily.
- Solution: Create a function that returns the value of the Boolean expression. Give the function an Intention Revealing Proper noun.
- Simply Understood Lawmaking (Gabriel)
- Problem: People demand to be comfy reading a piece of code before they feel confident that they empathise it and tin can alter it.
- Solution: "Arrange the important parts of the code and then it fits on one page. Make that code understandable to a person reading it from acme to lesser. Practise not require the lawmaking to be repeatedly scanned in order to understand how data is used and how control moves about."
- Assign Variables One time (Gabriel)
- Problem: If a variable is assigned twice, you might have problem figuring out which consignment provides the value at a particular signal, and your inclination is to retrieve the last consignment saw.
- Solution: Assign local variables only in one case, and, if possible, do that at the identify where the local variable is defined.
- Local Variables Reassigned Above Their Uses (Gabriel)
- Problem: "Sometimes a piece of lawmaking needs to re-assign local variables more than one time. If this is done without paying attention to a person reading the code who is unfamiliar with it, misunderstandings are piece of cake."
- Solution: "A local variable that must be re-assigned should exist re-assigned in a identify that is textually in a higher place where information technology is used or referenced."
- Intention Revealing Name (Chosen "Intention Revealing Selector" by Beck)
- Problem: How exercise you name a process?
- Solution: Name procedures for what they accomplish.
- Composed Procedure (Called "Equanimous Method" by Beck)
- Trouble: How should you lot divide a program into components?
- Solution: "Split up your program into [procedures] that do ane identifiable task. Keep all of the operations in a [process] at the aforementioned level of brainchild. This volition naturally result in programs with many small [procedures], each a few lines long."
- Office Suggesting Temporary Variable Proper noun (Beck)
- Problem: What do you call a temporary variable?
- Solution: "Name temporary variables for the part they play in the ciphering. Use variable naming every bit an opportunity to communicate valuable tactical information to future readers."
- Caching Temporary Variable (Beck)
- Trouble: How do you improve the performance of a method, in the face of repeated expression evaluations?
- Solution: "Set a temporary variable to the value of the expression as soon as it is valid. Use the variable instead of the expression in the remainder of the method."
- An Alternative Activity selects from among two or more actions on the basis of some condition.
Acknowledgements
We would like to give thanks the organizers of ChiliPLoP'98 for the opportunity to assemble and to brainstorm to grade an simple patterns community. We thank especially the other members of our ChiliPLoP workshop for their thoughts on looping patterns: Joe Bergin, Robert Duvall, Ed Epp, and Rick Mercer. Our PLoP shepherd, Marc Bradac, made many suggestions that improved our initial efforts.
References
- Owen Astrachan. Design Patterns: An Essential Component of CS Curricula. SIGCSE Bulletin and Proceedings, Volume thirty(one):153-160, March 1998.
- Kent Beck, Smalltalk Best Practice Patterns, Prentice Hall, New York, 1997.
- Jon L. Bentley and M. Douglas McIlroy. Engineering science a Sort Function. Software Practice and Experience. Book 23(11):1249-1265, November 1993.
- James O. Coplien, Advanced C++: Programming Styles and Idioms, Addison-Wesley, 1992.
- Richard Gabriel, Simply Understood Code, http://c2.com/cgi/wiki?SimplyUnderstoodCode
- Eric S. Roberts. Loop Exits and Structured Programming: Re-opening the Argue. SIGCSE Bulletin and Proceedings, Volume 27(1):268-272, March 1995.
- Sartaj Sahni. Data Structures, Algorithms, and Applications in C++, McGraw-Hill, 1997.
- Eugene Wallingford Roundabout, A Pattern Linguistic communication for Recursive Programming, PLoP-97, http://www.cs.uni.edu/~wallingf/research/patterns/recursion.html
Appendix: The Quicksort Partition
This is a more elaborate example of One Loop for Linear Structures.The sectionalisation stage of quicksort for arrays is a classic example. Most textbooks use a complicated solution in which an outer loop is substantially a Process All Items loop wrapped around ii inner loops that move indices delineating the two sections of the array. This three-loop solution is difficult for students to understand, like shooting fish in a barrel to lawmaking incorrectly, and harder to generalize to a three-phase partitioning required to avoid bad asymptotic operation when indistinguishable elements are stored in an array.
Using One Loop for Linear Structures in conjunction with Procedure All Items leads to the code shown below (taken from Engineering a Sort Office).
The invariant for this can be shown pictorially.
Not only is this lawmaking simpler to empathise than the lawmaking shown in many texts, it is more easily generalized to the three-phase "fat partition" (see Bentley) in which elements equal to the pivot are treated separately and put in their own partition. A fat sectionalization scheme is necessary to avoid O(n2) performance for arrays with many duplicate items. Fat partitioning yields a department of elements equal to the pivot element as well every bit sections less than and greater than the pivot chemical element (ii values are returned from the function and no recursion occurs on the equal department). It is too simple to include a median-of-three partition past swapping the median value into the left-almost entry before the loop begins.
The code below is indicative of partition functions developed without the benefit of the i loop for linear structures pattern, information technology appears in the text by Sahni. On the surface this code is harder to reason most and harder to adapt to the "fat segmentation" scheme.
Code developed with multiple loops can be more efficient. For case, the final, fully-tuned version of partition in Bentley uses the loops-in-a-loop coding style shown in the Sahni instance.
richardforkildney.blogspot.com
Source: https://users.cs.duke.edu/~ola/patterns/plopd/loops.html
0 Response to "The Priming Read Is Usually Placed as the First Step Within the Loop."
Publicar un comentario