📄 page38.html
字号:
<HTML><HEAD><TITLE>The Basic Axioms</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="tex2html1648" HREF="page39.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1646" HREF="page37.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1640" HREF="page37.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1650" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION002110000000000000000">The Basic Axioms</A></H2><P>The running time performance of the common language runtimeis given by a set of axioms which we shall now postulate.The first axiom addresses the running timeof simple name binding operations:<P><BLOCKQUOTE> <b>Axiom</b><A NAME="axiomi"> </A>The time required to fetch the identity of a named objectfrom memory is a constant, <IMG WIDTH=35 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57635" SRC="img7.gif" >,and the time required to bind a new name to an objectand store that binding in memory is a constant, <IMG WIDTH=33 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57637" SRC="img8.gif" >.</BLOCKQUOTE><P>According to Axiom <A HREF="page38.html#axiomi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the assignment statement<PRE>y = x</PRE>has running time <IMG WIDTH=88 HEIGHT=18 ALIGN=MIDDLE ALT="tex2html_wrap_inline57639" SRC="img9.gif" >.That is, the time taken to fetch the identityof the object named <tt>x</tt> is <IMG WIDTH=35 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57635" SRC="img7.gif" >and the time taken to bind the name <tt>y</tt> to that objectand store that binding in memory is <IMG WIDTH=33 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57637" SRC="img8.gif" >.<P>We shall apply Axiom <A HREF="page38.html#axiomi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> to manifest constants too:The assignment<PRE>y = 1</PRE>also has running time <IMG WIDTH=88 HEIGHT=18 ALIGN=MIDDLE ALT="tex2html_wrap_inline57639" SRC="img9.gif" >.To see why this should be the case,consider that the constant ``<tt>1</tt>'' names an integer object with value one.Therefore, we can expect the cost of fetching the identityof the object named <tt>1</tt> is the same as thatof fetching the identity of any other object.<P>The next axiom addresses the running time of simplearithmetic operations:<P><BLOCKQUOTE> <b>Axiom</b><A NAME="axiomii"> </A>The times required to perform elementary arithmetic operations,such as addition, subtraction, multiplication, division, and comparison,are all constants.These times are denoted by <IMG WIDTH=16 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline57647" SRC="img10.gif" >, <IMG WIDTH=16 HEIGHT=10 ALIGN=MIDDLE ALT="tex2html_wrap_inline57649" SRC="img11.gif" >, <IMG WIDTH=15 HEIGHT=12 ALIGN=MIDDLE ALT="tex2html_wrap_inline57651" SRC="img12.gif" >, <IMG WIDTH=16 HEIGHT=13 ALIGN=MIDDLE ALT="tex2html_wrap_inline57653" SRC="img13.gif" >, and <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57655" SRC="img14.gif" >, respectively.</BLOCKQUOTE><P>According to Axiom <A HREF="page38.html#axiomii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,all the simple operations can be accomplished in a fixedamount of time.In order for this to be feasible,the number of bits used to represent a value must also be fixed.In Python, a <em>plain integer</em><A NAME=322> </A>can be represented using 32 bits.As long as the operands and the result of an operation are all plain integers,we can say that the running time of the operation is fixed.Python also supports <em>long integers</em><A NAME=324> </A>which can have an arbitrarily large number of digits(subject to available memory).If long integers are used,then the basic arithmetic operations can take an arbitrarilylong amount of time and Axiom <A HREF="page38.html#axiomii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> does not apply.<P>By applying Axioms <A HREF="page38.html#axiomi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page38.html#axiomii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,we can determine that the running time of a statement like<PRE>y = y + 1</PRE>is <IMG WIDTH=132 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline57657" SRC="img15.gif" >.This is because we need to fetch the identities of the two objects named<tt>y</tt> and <tt>1</tt>;add them together giving a new object whose value is the sum;and, bind the name <tt>y</tt> to the result and store the new binding in memory.<P>Python syntax provides an alternative way to express the samecomputation:<PRE>y += 1</PRE>We shall assume that the alternative requires exactly the samerunning time as the original statement.<P>The third basic axiom addresses the method call/return overhead:<BLOCKQUOTE> <b>Axiom</b><A NAME="axiomiii"> </A>The time required to call a method is a constant, <IMG WIDTH=26 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57659" SRC="img16.gif" >,and the time required to return from a method is a constant, <IMG WIDTH=42 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57661" SRC="img17.gif" >.</BLOCKQUOTE><P>When a method is called,certain housekeeping operations need to be performed.Typically this includes saving the return address so thatprogram execution can resume at the correct place after the call,saving the state of any partially completed computationsso that they may be resumed after the call,and the allocation of a new execution context(stack frame<A NAME=335> </A>or activation record<A NAME=336> </A>)in which the called method can be evaluated.Conversely, on the return from a method,all of this work is undone.While the method call/return overhead may be rather large,nevertheless it entails a constant amount of work.<P>In addition to the method call/return overhead,additional overhead is incurred when parameters are passedto the method:<P><BLOCKQUOTE> <b>Axiom</b><A NAME="axiomiv"> </A>The time required to pass an argument to a methodis the same as the time required to bind a new name to an objectand store that binding in memory, <IMG WIDTH=33 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57637" SRC="img8.gif" >.</BLOCKQUOTE><P>The rationale for making the overhead associated with parameter passingthe same as the time to create and store a bindingis that the passing of an argument is conceptually the same asassignment of the actual parameter value to the formal parameterof the method.<P>According to Axiom <A HREF="page40.html#axiomv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the running time of the statement<PRE>y = f(x)</PRE>would be <IMG WIDTH=193 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline57665" SRC="img18.gif" >,where <IMG WIDTH=31 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline57667" SRC="img19.gif" > is the running time of method <tt>f</tt>for input <tt>x</tt>.The first of the two stores is due to the passing of the parameter <tt>x</tt>to the method <tt>f</tt>;the second arises from the assignment to the variable <tt>y</tt>.<P><HR><A NAME="tex2html1648" HREF="page39.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1646" HREF="page37.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1640" HREF="page37.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1650" 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 + -