📄 page188.html
字号:
<HTML><HEAD><TITLE>Performance Comparison:OrderedListAsArray vs. ListAsLinkedList</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="tex2html3371" HREF="page189.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3369" HREF="page169.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3363" HREF="page187.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3373" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION007130000000000000000">Performance Comparison:<tt>OrderedListAsArray</tt> vs. <tt>ListAsLinkedList</tt></A></H2><P><A NAME="seclistsperf"> </A><P>The running times calculated for the variousoperations of the two ordered list implementations,<tt>OrderedListAsArray</tt> and <tt>OrderedListAsLinkedList</tt>,are summarized below in Table <A HREF="page188.html#tbllists"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.With the exception of two operations,the running times of the two implementationsare asymptotically identical.<P><P><A NAME="9568"> </A><P> <A NAME="tbllists"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=4 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=LEFT><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=3> ordered list implementation</TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP><P> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>OrderedList-</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>OrderedList-</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> method </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>AsArray</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>AsLinkedList</tt> </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP><tt>__contains__</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>find</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>findPosition</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>__getitem__</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=11 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61127" SRC="img760.gif" ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>insert</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>withdraw</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>Cursor.datum</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>Cursor.insertAfter</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=11 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61127" SRC="img760.gif" ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>Cursor.insertBefore</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <tt>Cursor.withdraw</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Running times of operations on ordered lists.</CAPTION></TABLE></P></DIV><P><P>The two differences are the <tt>__getitem__</tt> methodand the <tt>insertAfter</tt> method.The <tt>__getitem__</tt> operation can be done constant time whenusing an array,but it requires <I>O</I>(<I>n</I>) in a linked list.Conversely, <tt>insertAfter</tt> requires <I>O</I>(<I>n</I>) time when usingan array,but can be done in constant time in the singly-linked list.<P>Table <A HREF="page188.html#tbllists"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> does not tell the whole story.The other important difference between the two implementationsis the amount of space required.Consider first the array implementation, <tt>OrderedListAsArray</tt>.The storage needed for an <tt>OrderedListAsArray</tt>which can hold <em>at most</em> <I>M</I> <tt>ComparableObject</tt>s is given by:<P> <IMG WIDTH=500 HEIGHT=64 ALIGN=BOTTOM ALT="eqnarray9603" SRC="img761.gif" ><P>The storage required for an array was discussed in Chapter <A HREF="page81.html#chapfds"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>:<P> <IMG WIDTH=500 HEIGHT=40 ALIGN=BOTTOM ALT="eqnarray9613" SRC="img762.gif" ><P>Therefore, the storage needed for an <tt>OrderedListAsArray</tt> is:<P> <IMG WIDTH=511 HEIGHT=16 ALIGN=BOTTOM ALT="eqnarray9622" SRC="img763.gif" ><P>Notice that we do not include in this calculationthe space required for the objects themselves.Since we cannot know the types of the contained objects,we cannot calculate the space required by those objects.<P>A similar calculation can also be donefor the <tt>OrderedListAsLinkedList</tt> class.In this case, we assume that the actual number of contained objects is <I>n</I>.The total storage required is given by:<P> <IMG WIDTH=541 HEIGHT=112 ALIGN=BOTTOM ALT="eqnarray9628" SRC="img764.gif" ><P>The storage required for a linked list was discussed in Chapter <A HREF="page81.html#chapfds"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>:<P> <IMG WIDTH=503 HEIGHT=112 ALIGN=BOTTOM ALT="eqnarray9641" SRC="img765.gif" ><P>Therefore, the storage needed for an <tt>OrderedListAsLinkedList</tt> is:<P> <IMG WIDTH=543 HEIGHT=16 ALIGN=BOTTOM ALT="eqnarray9654" SRC="img766.gif" ><P><P>If we assume that integers and object references require four bytes each,the storage requirement for the <tt>OrderedListAsArray</tt> classbecomes 4<I>M</I>+24 bytes;and for the <tt>OrderedListAsLinkedList</tt> class, 12<I>n</I>+20 bytes.That is, the storage needed for the array implementation is <I>O</I>(<I>M</I>),where <I>M</I> is the maximum length of the ordered list;whereas, the storage needed for the linked list implementation is <I>O</I>(<I>n</I>),where <I>n</I> is the actual number of items in the ordered list.Equating the two expressions,we get that the break-even point occurs at <IMG WIDTH=158 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61177" SRC="img767.gif" >.That is, if the array is less than one third full,the array version uses more memory space;and if the array is more than one third full,the linked list version uses more memory space.<P>It is not just the amount of memory space used that should be consideredwhen choosing an ordered list implementation.We must also consider the implications of the existence of the limit <I>M</I>.The array implementation requires <em>a priori</em> knowledgeabout the maximum number of items to be put in the ordered list.The total amount of storage then remains constant during the courseof execution.On the other hand, the linked list version has no pre-determined maximum length.It is only constrained by the total amount of memory available to the program.Furthermore, the amount of memory used by the linked list version variesduring the course of execution.We do not have to commit a large chunk of memoryfor the duration of the program.<P><HR><A NAME="tex2html3371" HREF="page189.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3369" HREF="page169.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3363" HREF="page187.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3373" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -