DOC PREVIEW
Stanford CS 106B - Efficiency and Data Representation

This preview shows page 1-2-3-20-21-40-41-42 out of 42 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Chapter 10Efficiency andData RepresentationTime granted does not necessarily coincide with time thatcan be most fully used.— Tillie Olsen, Silences, 1965Objectives•To learn that different strategies for representing data can have a profound effect onthe efficiency of your code.• To be able to compare the computational complexity of different representationstrategies.• To understand the concept of a linked list and how it can be used to provide a basis forefficient insertion and deletion operations.• To appreciate that representations which are efficient in terms of their execution timemay be inefficient in their use of memory.Data Structures and Efficiency – 342 –This chapter brings together two ideas that might at first seem to have little to do witheach other: the notion of algorithmic efficiency presented in Chapter 8 and the idea ofclasses from Chapter 9. Up to now, efficiency has been closely linked with the study ofalgorithms. If you choose a more efficient algorithm, you can reduce the running time ofa program substantially, particularly if the new algorithm is in a different complexityclass. In some cases, choosing a different underlying representation for a class can havean equally dramatic effect. To illustrate this idea, this chapter looks at a specific classthat can be represented in several different ways and contrasts the efficiency of thoserepresentations.10.1 The concept of an editor bufferWhenever you create a source file or use a word processor to edit text, you are using apiece of software called an editor, which allows you to make changes to a text file.Internally, an editor maintains a sequence of characters, which is usually called a buffer.The editor application allows you to make changes to the contents of the buffer, usuallyby some combination of the following operations:• Moving the cursor to the point in the text at which editing needs to take place.• Typing in new text, which is then inserted at the current cursor position.• Deleting characters using a delete or backspace key.Modern editors usually provide a highly sophisticated editing environment, completewith such fancy features as using a mouse to position the cursor or commands that searchfor a particular text string. Moreover, they tend to show the results of all editingoperations precisely as they are performed. Editors that display the current contents ofthe buffer throughout the editing process are called wysiwyg (pronounced “wizzy-wig”)editors, which is an acronym for “what you see is what you get.” Such editors are veryeasy to use, but their advanced features sometimes make it harder to see how an editorworks on the inside.In the early days of computing, editors were much simpler. Lacking access to a mouseor a sophisticated graphics display, editors were designed to respond to commandsentered on the keyboard. For example, with a typical keyboard-based editor, you insertnew text by typing the command letter I, followed by a sequence of characters.Additional commands perform other editing functions, such as moving the cursor aroundin the buffer. By entering the right combinations of these commands, you can make anydesired set of changes.To make the idea of the editor buffer as concrete as possible, let’s suppose that yourtask is to build an editor that can execute the six commands shown in Table 10-1. Exceptfor the I command, which also takes the characters to be inserted, every editor commandconsists of a single letter read in on a line.Table 10-1 Commands implemented by the editorCommand OperationF Moves the editing cursor forward one character positionB Moves the editing cursor backward one character positionJ Jumps to the beginning of the buffer (before the first character)E Moves the cursor to the end of the buffer (after the last character)Ixxx Inserts the characters xxx at the current cursor positionD Deletes the character just after the current cursor positionData Structures and Efficiency – 343 –The following sample run illustrates the operation of the editor, along with annotationsthat describe each action. In this session, the user first inserts the characters axc and thencorrects the contents of the buffer to abc. The editor program displays the state of thebuffer after each command, marking the position of the cursor with a carat symbol (^) onthe next line.* a x c ^* a x c^* a x c ^* a c ^* a b c ^*This command inserts the three characters ‘a’, ‘x’, and ‘c’, leaving the cursor at the end of the buffer.This command moves the cursor to the beginning of the buffer.This command moves the cursor forward one character.This command deletes the character after the cursor.This command inserts the character ‘b’ . Iaxc J F D Ib 10.2 Defining the buffer abstractionIn creating an editor that can execute the commands from Table 10-1, your main task is todesign a data structure that maintains the state of the editor buffer. This data structuremust keep track of what characters are in the buffer and where the cursor is. It must alsobe able to update the buffer contents whenever an editing operation is performed. Inother words, what you want to do is define a new abstraction that represents the editorbuffer.Even at this early stage, you probably have some ideas about what internal datastructures might be appropriate. Because the buffer is clearly an ordered sequence ofcharacters, one seemingly obvious choice is to use a string or a Vector<char> as theunderlying representation. As long as you have these classes available, either would bean appropriate choice. The goal of this chapter, however, is to understand how the choiceof representation affects the efficiency of applications. That point is difficult to make ifyou use higher-level structures like string and Vector because the inner workings ofthose classes are not visible to clients. If you choose instead to limit your implementationto the built-in data structures, every operation becomes visible, and it is therefore mucheasier to determine the relative efficiency of various competing designs. That logicsuggests using a character array as the underlying, because array operations have nohidden costs.Although using an array to represent the buffer is certainly a reasonable approach tothe problem, there are other representations that offer interesting possibilities. Thefundamental lesson in this chapter—and indeed in much of this book—is that you shouldnot


View Full Document

Stanford CS 106B - Efficiency and Data Representation

Download Efficiency and Data Representation
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 Efficiency and Data Representation 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 Efficiency and Data Representation 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?