page246.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 165 行
HTML
165 行
<HTML><HEAD><TITLE>Removing Items</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html4034" HREF="page247.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4032" HREF="page242.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4028" HREF="page245.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4036" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION008644000000000000000">Removing Items</A></H3><P>Removing items from a scatter table usingopen addressing has to be done with some care.The naïve approach would be to locate the item to be removedand then change the state of its location to <tt>EMPTY</tt>.However, that approach does not work!Recall that the <tt>findMatch</tt> method which is used to locate an itemstops its search when it encounters an <tt>EMPTY</tt> cell.Therefore, if we change the state of a cell in the middle of a clusterto <tt>EMPTY</tt>,all subsequent searches in that cluster will stop at the empty cell.As a result, subsequent searches for an object may faileven when the target is still in the table!<P>One way to deal with this is to make use of the third state, <tt>DELETED</tt>.Instead of marking a location <tt>EMPTY</tt>,we mark it <tt>DELETED</tt> when an item is deleted.Recall that that the <tt>findMatch</tt> method was written in such away that it continues past deleted cells in its search.Also, the <tt>findUnoccupied</tt> method was written to stop itssearch when it encounters either an <tt>EMPTY</tt> or a <tt>DELETED</tt> location.Consequently, the positions marked <tt>DELETED</tt> are availablefor reuse when insertion is done.<P>Program <A HREF="page246.html#progopenScatterTablee"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the implementation of the <tt>withdraw</tt>.In addition to <tt>self</tt>,the <tt>withdraw</tt> method takes an objectand removes that object from the scatter table.It does so by first locating the specific object instanceusing <tt>findInstance</tt> and then marking the location <tt>DELETED</tt>.The implementation of <tt>findInstance</tt> has been elided.It is simply a trivial variation of the <tt>findMatch</tt> method.<P><P><A NAME="13665"> </A><A NAME="progopenScatterTablee"> </A> <IMG WIDTH=575 HEIGHT=237 ALIGN=BOTTOM ALT="program13429" SRC="img1008.gif" ><BR><STRONG>Program:</STRONG> <tt>OpenScatterTable</tt> Class <tt>withdraw</tt> method.<BR><P><P>The running time of the <tt>withdraw</tt> method is determinedby that of <tt>findInstance</tt>.In the worst case <tt>findInstance</tt> has to examine every array position.Therefore, the running time of <tt>withdraw</tt> is <IMG WIDTH=109 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62315" SRC="img958.gif" >.<P>There is a very serious problem with the technique of markinglocations as <tt>DELETED</tt>.After a large number of insertions and deletions have been done,it is very likely that there are no cells left that are marked <tt>EMPTY</tt>.This is because, nowhere in any of the methods (except <tt>purge</tt>)is a cell ever marked <tt>EMPTY</tt>!This has the very unfortunate consequence that an unsuccessful search,i.e., a search for an object which is not in the scatter table,is <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62575" SRC="img1009.gif" >.Recall that <tt>findMatch</tt> examines at most <I>M</I> array locationsand only stops its search early when an <tt>EMPTY</tt> location is encountered.Since there are no more empty locations,the search must examine all <I>M</I> locations.<P>If we are using the scatter table in an application in whichwe know <em>a priori</em> that no items will be removed,or perhaps only a very small number of items will be removed,then the <tt>withdraw</tt> method given in Program <A HREF="page245.html#progopenScatterTabled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>will suffice.However, if the application is such that a significant number ofwithdrawals will be made,a better implementation is required.<P>Ideally, when removing an item the scatter table ends upexactly as it would have appearedhad that item never been inserted in the first place.Note that exactly the same constraint is met by the <tt>withdraw</tt>method for the <tt>ChainedScatterTable</tt> class givenin Program <A HREF="page235.html#progchainedScatterTabled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.It turns out that a variation of that algorithm can beused to implement the <tt>withdraw</tt> methodfor the <tt>OpenScatterTable</tt> classas shown in Program <A HREF="page246.html#progopenScatterTableV2a"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="13667"> </A><A NAME="progopenScatterTableV2a"> </A> <IMG WIDTH=575 HEIGHT=466 ALIGN=BOTTOM ALT="program13457" SRC="img1010.gif" ><BR><STRONG>Program:</STRONG> <tt>OpenScatterTableV2</tt> class <tt>withdraw</tt> method.<BR><P><P>The algorithm begins by checking that the scatter table is not empty.Then it calls <tt>findInstance</tt> to determinethe position <tt>i</tt> of the item to be removed.If the item to be removed is not in the scatter table<tt>findInstance</tt> returns -1 and an exception is thrown.Otherwise, <tt>findInstance</tt> falls between 0 and <I>M</I>-1,which indicates that the item was found.<P>In the general case,the item to be deleted falls in the middle of a cluster.Deleting it would create a hole in the middle of the cluster.What we need to do is to find another item further down in the clusterwhich can be moved up to fill in the hole that would be createdwhen the item at position <tt>i</tt> is deleted.The purpose of the loop on lines 11-16is to find the position <tt>j</tt> of an item which can bemoved safely into position <tt>i</tt>.Note the implementation here implicitly assumes thata linear probing sequence is used--the <tt>c</tt> method is not called explicitly.An item at position <tt>j</tt> can be moved safely to position <tt>i</tt>only if the hash value of the item at position <tt>j</tt>is not cyclically contained in the interval between <tt>i</tt> and <tt>j</tt>.<P>If an item is found at some position <tt>j</tt> that can be moved safely,then that item is moved to position <tt>i</tt> on line 19.The effect of moving the item at position <tt>j</tt> to position <tt>i</tt>,is to move the hole from position <tt>i</tt> to position <tt>j</tt> (line 24).Therefore, another iteration of the main loop (lines 9-20) is neededto fill in the relocated hole in the cluster.<P>If no item can be found to fill in the hole,then it is safe to split the cluster in two.Eventually, either because no item can be found to fill in the holeor because the hole has moved to the end of the cluster,there is nothing more to do other than to delete the hole.Thus, on line 21 the entry at position <tt>i</tt> is setto <tt>EMPTY</tt> and the associated <tt>obj</tt> is set to <tt>None</tt>.Notice that the third state <tt>DELETED</tt> is not requiredin this implementation of <tt>withdraw</tt>.<P>If we use the <tt>withdraw</tt> implementation of Program <A HREF="page246.html#progopenScatterTableV2a"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the scatter table entries will only ever be in oneof two two states--<tt>OCCUPIED</tt> or <tt>EMPTY</tt>.Consequently, we can improve the bound on the worst-case for the search from <IMG WIDTH=193 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62571" SRC="img1007.gif" > to <IMG WIDTH=185 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62589" SRC="img1011.gif" >,where <I>n</I> is the number of items in the scatter table.<P>Determining the running time of Program <A HREF="page246.html#progopenScatterTableV2a"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is a little tricky.Assuming the item to be deleted is actually in the table,the running time to find the position of that item (line 6) is <IMG WIDTH=101 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62215" SRC="img932.gif" >,where <IMG WIDTH=72 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline60691" SRC="img663.gif" > is the number of item actually in the scatter table.In the worst case,the scatter table is comprised of a single cluster of <I>n</I> items,and we are deleting the first item of the cluster.In this case,the main loop on lines 9-20 makes a pass through the entire cluster,in the worst case moving the hole to the end of the cluster one positionat at time.Thus, the running time of the main loop is <IMG WIDTH=150 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62599" SRC="img1012.gif" >.The remaining lines require a constant amount of additional time.Altogether, the running time for the <tt>Withdraw</tt> method is <IMG WIDTH=111 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62601" SRC="img1013.gif" > in the worst case.<P><HR><A NAME="tex2html4034" HREF="page247.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4032" HREF="page242.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4028" HREF="page245.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4036" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?