page90.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 76 行
HTML
76 行
<HTML><HEAD><TITLE>Array Subscript Calculations</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="tex2html2249" HREF="page91.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2247" HREF="page89.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2241" HREF="page89.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2251" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION004210000000000000000">Array Subscript Calculations</A></H2><P>The memory of a computer is essentially a one-dimensional array--the memory address is the array subscript.Therefore, a natural way to implement a multi-dimensionalarray is to store its elements in a one-dimensional array.In order to do this,we need a mapping from the <I>n</I> subscript expressionsused to access an element of the multi-dimensional arrayto the one subscript expression used to access the one-dimensional array.For example, suppose we wish to represent a <IMG WIDTH=34 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline60465" SRC="img594.gif" > array of <tt>int</tt>s,<tt>a</tt>, using a one-dimensional array like this:<PRE>b = Array(6)</PRE>Then we need to determine which element of <tt>b</tt>, say <tt>b[k]</tt>,will be accessed given a reference of the form <tt>a[i,j]</tt>.That is, we need the mapping <I>f</I> such that <IMG WIDTH=74 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60469" SRC="img595.gif" >.<P>The mapping function determines the way in which the elementsof the array are stored in memory.The most common way to represent an array is in<em>row-major order</em><A NAME=2865> </A>,also known as <em>lexicographic order</em><A NAME=2867> </A>.For example, consider the <IMG WIDTH=34 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline60465" SRC="img594.gif" > two-dimensional array.The row-major layout of this array is shown in Figure <A HREF="page90.html#figrowmajor"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="3084"> </A><A NAME="figrowmajor"> </A> <IMG WIDTH=575 HEIGHT=214 ALIGN=BOTTOM ALT="figure2869" SRC="img596.gif" ><BR><STRONG>Figure:</STRONG> Row-major order layout of a 2D array.<BR><P><P>In row-major layout, it is the right-most subscript expression(the column index) that increases the fastest.As a result, the elements of the rows of the matrixend up stored in contiguous memory locations.In Figure <A HREF="page90.html#figrowmajor"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the first element of the first row is at position <tt>b[0]</tt>.The first element of the <em>second</em> row is at position <tt>b[3]</tt>,since there are 3 elements in each row.<P>We can now generalize this to an arbitrary <I>n</I>-dimensional array.Suppose we have an <I>n</I>-D array <tt>a</tt> with dimensions<P> <IMG WIDTH=320 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath60461" SRC="img597.gif" ><P>Then, the position of the element<tt>a[ <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline60477" SRC="img598.gif" >, <IMG WIDTH=11 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline60479" SRC="img599.gif" >, <IMG WIDTH=16 HEIGHT=2 ALIGN=BOTTOM ALT="tex2html_wrap_inline60481" SRC="img600.gif" >, <IMG WIDTH=29 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline60483" SRC="img601.gif" >]</tt> is given by<P><A NAME="eqnfdsaddress"> </A> <IMG WIDTH=500 HEIGHT=49 ALIGN=BOTTOM ALT="equation3094" SRC="img602.gif" ><P>where<P><A NAME="eqnfdsfactors"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation3099" SRC="img603.gif" ><P><P>The running time required to calculate the position appears to be <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >since the position is the sum of <I>n</I> terms and for each termwe need to compute <IMG WIDTH=12 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline60489" SRC="img604.gif" >, which requires <I>O</I>(<I>n</I>) multiplicationsin the worst case.However, the factors <IMG WIDTH=12 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline60489" SRC="img604.gif" > are determinedsolely from the dimensions of the array.Therefore, we need only compute the factors once.Assuming that the factors have been precomputed,the position calculation can be done in <I>O</I>(<I>n</I>) timeusing the following algorithm:<P><PRE>offset = 0for j in range(n): offset += <IMG WIDTH=11 HEIGHT=17 ALIGN=BOTTOM ALT="tex2html_wrap60457" SRC="img605.gif" > * <IMG WIDTH=10 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap60458" SRC="img606.gif" ></PRE><HR><A NAME="tex2html2249" HREF="page91.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2247" HREF="page89.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2241" HREF="page89.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2251" 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 + -
显示快捷键?