chap18.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

<a name="0849_15e5">18.3-3<a name="0849_15e5"><P>
<a name="0849_15e0"><a name="0849_15e1">Consider an ordinary binary heap data structure with <I>n </I>elements that supports the instructions <FONT FACE="Courier New" SIZE=2>INSERT</FONT> and <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> in <I>O</I>(lg <I>n</I>) worst-case time. Give a potential function <img src="../images/phicap12.gif"> such that the amortized cost of <FONT FACE="Courier New" SIZE=2>INSERT</FONT> is <I>O</I>(lg <I>n</I>) and the amortized cost of <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> is <I>O</I>(1), and show that it works.<P>
<a name="0849_15e6">18.3-4<a name="0849_15e6"><P>
What is the total cost of executing <I>n </I>of the stack operations <FONT FACE="Courier New" SIZE=2>PUSH</FONT>, <FONT FACE="Courier New" SIZE=2>POP</FONT>, and <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT>, assuming that the stack begins with <I>s</I><SUB>0</SUB><I> </I>objects and finishes with <I>s<SUB>n</SUB> </I>objects?<P>
<a name="0849_15e7">18.3-5<a name="0849_15e7"><P>
Suppose that a counter begins at a number with <I>b </I>1's in its binary representation, rather than at 0. Show that the cost of performing <I>n </I><FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operations is <I>O</I>( <I>n</I>) if <I>n </I>= <img src="../images/omega12.gif">(<I>b</I>). (Do not assume that <I>b</I> is constant.)<P>
<a name="0849_15e8">18.3-6<a name="0849_15e8"><P>
Show how to implement a queue with two ordinary stacks (Exercise 11.1-6) so that the amortized cost of each <FONT FACE="Courier New" SIZE=2>ENQUEUE</FONT> and each <FONT FACE="Courier New" SIZE=2>DEQUEUE</FONT> operation is <I>O</I>(1).<P>
<P>


<P>







<h1><a name="084a_15e6">18.4 Dynamic tables<a name="084a_15e6"></h1><P>
<a name="084a_15e2"><a name="084a_15e3">In some applications, we do not know in advance how many objects will be stored in a table. We might allocate space for a table, only to find out later that it is not enough. The table must then be reallocated with a larger size, and all objects stored in the original table must be copied over into the new, larger table. Similarly, if many objects have been deleted from the table, it may be worthwhile to reallocate the table with a smaller size. In this section, we study this problem of dynamically expanding and contracting a table. Using amortized analysis, we shall show that the amortized cost of insertion and deletion is only <I>O</I>(1), even though the actual cost of an operation is large when it triggers an expansion or a contraction. Moreover, we shall see how to guarantee that the unused space in a dynamic table never exceeds a constant fraction of the total space.<P>
We assume that the dynamic table supports the operations <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> and <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>. <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> inserts into the table an item that occupies a single <I><B>slot</I></B>, that is, a space for one item. Likewise, <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> can be thought of as removing an item from the table, thereby freeing a slot. The details of the data-structuring method used to organize the table are unimportant; we might use a stack (Section 11.1), a heap (Section 7.1), or a hash table (Chapter 12). We might also use an array or collection of arrays to implement object storage, as we did in Section 11.3.<P>
<a name="084a_15e4"><a name="084a_15e5">We shall find it convenient to use a concept introduced in our analysis of hashing (Chapter 12). We define the <I><B>load factor</I> </B><img src="../images/alpha12.gif">(<I>T</I>) of a nonempty table <I>T</I> to be the number of items stored in the table divided by the size (number of slots) of the table. We assign an empty table (one with no items) size 0, and we define its load factor to be 1. If the load factor of a dynamic table is bounded below by a constant, the unused space in the table is never more than a constant fraction of the total amount of space.<P>
We start by analyzing a dynamic table in which only insertions are performed. We then consider the more general case in which both insertions and deletions are allowed.<P>





<h2><a name="084b_15ec">18.4.1 Table expansion<a name="084b_15ec"></h2><P>
<a name="084b_15e6">Let us assume that storage for a table is allocated as an array of slots. A table fills up when all slots have been used or, equivalently, when its load factor is 1.<SUP>1</SUP> In some software environments, if an attempt is made to insert an item into a full table, there is no alternative but to abort with an error. We shall assume, however, that our software environment, like many modern ones, provides a memory-management system that can allocate and free blocks of storage on request. Thus, when an item is inserted into a full table, we can <I><B>expand</I></B> the table by allocating a new table with more slots than the old table had and then copy items from the old table into the new one.<P>
<SUP>1</SUP>In some situations, such as an open-address hash table, we may wish to consider a table to be full if its load factor equals some constant strictly less than 1. (See Exercise 18.4-2.)<P>
A common heuristic is to allocate a new table that has twice as many slots as the old one. If only insertions are performed, the load factor of a table is always at least 1/2, and thus the amount of wasted space never exceeds half the total space in the table.<P>
In the following pseudocode, we assume that <I>T</I> is an object representing the table. The field <I>table</I>[<I>T</I>] contains a pointer to the block of storage representing the table. The field <I>num</I>[<I>T</I>]contains the number of items in the table, and the field <I>size</I>[<I>T</I>] is the total number of slots in the table. Initially, the table is empty: <I>num</I>[<I>T</I>] = <I>size</I>[<I>T</I>] = 0.<P>
<pre><a name="084b_15e7">TABLE-INSERT(<I>T</I>,<I>x</I>)</sub></sup></pre><P>
<pre>1  <B>if</B> <I>size</I>[<I>T</I>] = 0</sub></sup></pre><P>
<pre>2      <B>then </B>allocate <I>table </I>[<I>T</I>] with 1 slot</sub></sup></pre><P>
<pre>3           <I>size</I>[<I>T</I>] <img src="../images/arrlt12.gif"> 1</sub></sup></pre><P>
<pre>4  <B>if</B> <I>num</I>[<I>T</I>] = <I>size</I>[<I>T</I>]</sub></sup></pre><P>
<pre>5      <B>then</B> allocate <I>new-table</I> with 2 <img src="../images/dot10.gif"> <I>size</I>[<I>T</I>] slots</sub></sup></pre><P>
<pre>6           insert all items in <I>table</I>[<I>T</I>] into <I>new-table</I></sub></sup></pre><P>
<pre>7           free <I>table</I>[<I>T</I>]</sub></sup></pre><P>
<pre>8           <I>table</I>[<I>T</I>] <img src="../images/arrlt12.gif"> <I>new-table</I></sub></sup></pre><P>
<pre>9           <I>size</I>[<I>T</I>] <img src="../images/arrlt12.gif"> 2 <img src="../images/dot10.gif"> <I>size</I>[<I>T</I>]</sub></sup></pre><P>
<pre>10  insert <I>x</I> into <I>table</I>[<I>T</I>]</sub></sup></pre><P>
<pre>11  <I>num</I>[<I>T</I>] <img src="../images/arrlt12.gif"> <I>num</I>[<I>T</I>] + 1</sub></sup></pre><P>
Notice that we have two &quot;insertion&quot; procedures here: the <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> procedure itself and the <I><B>elementary insertion</I></B> into a table in lines 6 and 10. We can analyze the running time of <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> in terms of the number of elementary insertions by assigning a cost of 1 to each elementary insertion. We assume that the actual running time of <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> is linear in the time to insert individual items, so that the overhead for allocating an initial table in line 2 is constant and the overhead for allocating and freeing storage in lines 5 and 7 is dominated by the cost of transferring items in line 6. We call the event in which the <B>then</B> clause in lines 5-9 is executed an <I><B>expansion</I></B>.<P>
Let us analyze a sequence of <I>n</I> <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operations on an initially empty table. What is the cost <I>c<SUB>i</I></SUB> of the <I>i</I>th operation? If there is room in the current table (or if this is the first operation), then <I>c<SUB>i</I></SUB> = 1, since we need only perform the one elementary insertion in line 10. If the current table is full, however, and an expansion occurs, then <I>c<SUB>i</SUB> = i</I>: the cost is 1 for the elementary insertion in line 10 plus <I>i</I> - 1 for the items that must be copied from the old table to the new table in line 6. If <I>n</I> operations are performed, the worst-case cost of an operation is <I>O</I>(<I>n</I>), which leads to an upper bound of <I>O</I>(<I>n</I><SUP>2</SUP>) on the total running time for <I>n</I> operations. <P>
This bound is not tight, because the cost of expanding the table is not borne often in the course of <I>n</I> <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operations. Specifically, the <I>i</I>th operation causes an expansion only when <I>i</I> - 1 is an exact power of 2. The amortized cost of an operation is in fact <I>O</I>(1), as we can show using the aggregate method. The cost of the <I>i</I>th operation is<P>
<img src="369_a.gif"><P>
The total cost of <I>n</I> <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operations is therefore<P>
<img src="369_b.gif"><P>
since there are at most <I>n</I> operations that cost 1 and the costs of the remaining operations form a geometric series. Since the total cost of <I>n</I> <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operations is 3<I>n</I>, the amortized cost of a single operation is 3.<P>
<a name="084b_15e8"><a name="084b_15e9">By using the accounting method, we can gain some feeling for why the amortized cost of a <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operation should be 3. Intuitively, each item pays for 3 elementary insertions: inserting itself in the current table, moving itself when the table is expanded, and moving another item that has already been moved once when the table is expanded. For example, suppose that the size of the table is <I>m</I> immediately after an expansion. Then, the number of items in the table is <I>m</I>/2, and the table contains no credit. We charge 3 dollars for each insertion. The elementary insertion that occurs immediately costs 1 dollar. Another dollar is placed as credit on the item inserted. The third dollar is placed as credit on one of the <I>m</I>/2 items already in the table. Filling the table requires <I>m</I>/2 additional insertions, and thus, by the time the table contains <I>m</I> items and is full, each item has a dollar to pay for its reinsertion during the expansion.<P>
<a name="084b_15ea"><a name="084b_15eb">The potential method can also be used to analyze a sequence of <I>n</I> <FONT FACE="Courier New" SIZE=2>TABLE</FONT>- <FONT FACE="Courier New" SIZE=2>INSERT</FONT> operations, and we shall use it in Section 18.4.2 to design a <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> operation that has <I>O</I>(1) amortized cost as well. We start by defining a potential function <img src="../images/phicap12.gif"> that is 0 immediately after an expansion but builds to the table size by the time the table is full, so that the next expansion can be paid for by the potential. The function<P>
<pre><img src="../images/phicap12.gif">(<I>T</I>) = 2<img src="../images/dot10.gif"><I>num</I>[<I>T</I>] - <I>size</I>[<I>T</I>]</sub></sup></pre><P>
<h4><a name="084b_15ed">(18.4)<a name="084b_15ed"></sub></sup></h4><P>
is one possibility. Immediately after an expansion, we have <I>num</I>[<I>T</I>] = <I>size</I>[<I>T</I>]/2, and thus <img src="../images/phicap12.gif">(<I>T</I>) = 0, as desired. Immediately before an expansion, we have <I>num</I>[<I>T</I>] = <I>size</I>[<I>T</I>], and thus <img src="../images/phicap12.gif">(<I>T</I>) = <I>num</I>[<I>T</I>], as desired. The initial value of the potential is 0, and since the table is always at least half full, <I>num</I>[<I>T</I>] <img src="../images/gteq.gif"> <I>size</I>[<I>T</I>]/2, which implies that <img src="../images/phicap12.gif">(<I>T</I>) is always nonnegative. Thus, the sum of the amortized costs of <I>n</I> <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operations is an upper bound on the sum of the actual costs.<P>
To analyze the amortized cost of the <I>i</I>th <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operation, we let <I>num<SUB>i</I></SUB> denote the number of items stored in the table after the <I>i</I>th operation, <I>size<SUB>i</I></SUB> denote the total size of the table after the <I>i</I>th operation, and <img src="../images/phicap12.gif"><I><SUB>i</I></SUB> denote the potential after the <I>i</I>th operation. Initially, we have num<SUB>0</SUB> = 0, <I>size</I><SUB>0</SUB> =0, and <img src="../images/phicap12.gif"><SUB>0</SUB> = 0.<P>
If the <I>i</I>th <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operation does not trigger an expansion, then <I>size<SUB>i</I></SUB> = <I>size<SUB>i - </I>1</SUB> and the amortized cost of the operation is<P>
<img src="370_a.gif"><P>
If the <I>i</I>th operation does trigger an expansion, then <I>size<SUB>i</I></SUB>/2 = <I>size<SUB>i</I>-1</SUB> = <I>num<SUB>i</I></SUB> - 1, and the amortized cost of the operation is<P>
<img src="370_b.gif"><P>
Figure 18.3 plots the values of <I>num<SUB>i</I></SUB>, <I>size<SUB>i</I></SUB>, and <img src="../images/phicap12.gif"><I><SUB>i</I></SUB> against <I>i</I>. Notice how the potential builds to pay for the expansion of the table.<P>
<P>







<h2><a name="084c_15f0">18.4.2 Table expansion and contraction<a name="084c_15f0"></h2><P>
To implement a <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> operation, it is simple enough to remove the specified item from the table. It is often desirable, however, to <I><B>contract</I></B> the table when the load factor of the table becomes too small, so that the wasted space is not exorbitant. Table contraction is analogous to table expansion: when the number of items in the table drops too low, we allocate a new, smaller table and then copy the items from the old table into the new one. The storage for the old table can then be freed by returning it to the memory-management system. Ideally, we would like to preserve two properties:<P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif">     </FONT>the load factor of the dynamic table is bounded below by a constant, and<P>