page516.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 91 行

HTML
91 行
字号 
<HTML><HEAD><TITLE>Performance Data</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="tex2html7093" HREF="page517.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7091" HREF="page478.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7085" HREF="page515.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html7095" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0015900000000000000000">Performance Data</A></H1><P>In order to better understand the actual performanceof the various sorting algorithms presented in this chapter,it is necessary to conduct some experiments.Only by conducting experiments is it possible to determinethe relative performance of algorithmswith the same asymptotic running time.<P>To measure the performance of a sorting algorithm,we need to provide it with some data to sort.To obtain the results presented here,random sequences of integers were sorted.That is, for each value of <I>n</I>,the <tt>RandomNumberGenerator</tt> class defined in Section&nbsp;<A HREF="page465.html#secalgsrng"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>was used to create a sequence of <I>n</I> integers.In all cases (except for bucket sort)the random numbers are uniformly distributedin the interval  <IMG WIDTH=71 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline69951" SRC="img2139.gif"  >.For the bucket sort the numbers are uniformly distributed in  <IMG WIDTH=70 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline69953" SRC="img2140.gif"  >.<P>Figures&nbsp;<A HREF="page516.html#figsorting1"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, <A HREF="page516.html#figsorting2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and&nbsp;<A HREF="page516.html#figsorting3"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> show the actual running timesof the sorting algorithms presented in this chapter.These running times were measured on an Intel Pentium&nbsp;III,which has a 1&nbsp;GHz clock and 256MB RAMunder the Red Hat Linux 7.1 operating system.The programs were executed using the Python version 2.2.3 interpreter.The times shown are elapsed CPU times, measured in seconds.<P>Figure&nbsp;<A HREF="page516.html#figsorting1"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the running times of the  <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif"  > sortsfor sequences of length <I>n</I>,  <IMG WIDTH=102 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69959" SRC="img2141.gif"  >.Notice that the bubble sort has the worst performanceand that the straight selection sort has the best performance.Figure&nbsp;<A HREF="page516.html#figsorting1"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> clearly shows that, as predicted,binary insertion is better than straight insertion.Notice too that all of the  <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif"  > sorts require more than 25 secondsof execution time to sort an array of 2000 integers.<P><P><A NAME="47007">&#160;</A><A NAME="figsorting1">&#160;</A> <IMG WIDTH=575 HEIGHT=417 ALIGN=BOTTOM ALT="figure46321" SRC="img2142.gif"  ><BR><STRONG>Figure:</STRONG> Actual running times of the  <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif"  > sorts.<BR><P><P>The performance of the  <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif"  > sorts is shown in Figure&nbsp;<A HREF="page516.html#figsorting2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In this case, the length of the sequence varies between <I>n</I>=10and  <IMG WIDTH=74 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70097" SRC="img2143.gif"  >.The graph clearly shows that the  <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif"  > algorithms are significantlyfaster that the  <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif"  > ones.All three algorithms sort 10000 integers in under 8 seconds.Quicksort is clear the best of the three.<P><P><A NAME="47235">&#160;</A><A NAME="figsorting2">&#160;</A> <IMG WIDTH=575 HEIGHT=400 ALIGN=BOTTOM ALT="figure47011" SRC="img2144.gif"  ><BR><STRONG>Figure:</STRONG> Actual running times of the  <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif"  > sorts.<BR><P><P>Figure&nbsp;<A HREF="page516.html#figsorting3"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the actual running times for the bucket sortand radix sort algorithms.Both these algorithms were shown to be <I>O</I>(<I>n</I>) sorts.The graph shows results for <I>n</I> between 10 and  <IMG WIDTH=50 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70265" SRC="img2145.gif"  >.The universe used to test bucket sort was  <IMG WIDTH=105 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70267" SRC="img2146.gif"  >.That is, a total of <I>m</I>=1024 counters (buckets) were used.For the radix sort, 32-bit integers were sorted by using the radix <I>R</I>=256and doing <I>p</I>=4 sorting passes.<P><P><A NAME="47480">&#160;</A><A NAME="figsorting3">&#160;</A> <IMG WIDTH=575 HEIGHT=383 ALIGN=BOTTOM ALT="figure47239" SRC="img2147.gif"  ><BR><STRONG>Figure:</STRONG> Actual running times of the <I>O</I>(<I>n</I>) sorts.<BR><P><P>Clearly, the bucket sort has the better running time.For example, it sorts 100000 10-bit integers in under 5 seconds.Radix sort performs extremely well too.It sorts 100000 32-bit integers in about 35 seconds.Given that the radix sort makes four passes through the data set,we can expect that it will be at least four times slower than the bucket sort.<P><HR><A NAME="tex2html7093" HREF="page517.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7091" HREF="page478.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7085" HREF="page515.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html7095" 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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page516.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page516.html 源码文件，采用 HTML 编程语言编写，共 91 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?