?? tutorials.html
字號:
<HTML><HEAD>
<TITLE>Data Structures and Algorithms - Tutorials</TITLE>
</HEAD>
<BODY BGCOLOR="#ffffff">
<H1>Data Structures and Algorithms<BR>
Tutorials</H1>
<HR>
<H3>Tutorial 1</H3>
<OL>
<LI><H3>Arrays or Linked Lists?</H3>
An array implementation of a collection requires <B><I>O(n)</I></B>
time to search it (assuming it's not ordered).
A linked list also requires <B><I>O(n)</I></B> time to search.
Yet one of these will be quite a bit faster on a high-performance
modern processor. Which one? Why?
<P>
<I>Hint:</I> Part of the answer is found in the next question and
part in IPS205 - the computer architecture section.
<P>
<LI><H3>Overheads</H3>
The storage requirements for a typical modern RISC processor are:
<CENTER><TABLE BORDER CELLPADDING=4>
<TR>
<TH>Type</TH><TH>Space <I>(bytes)</I></TH>
</TR>
<TR><TD><CENTER>integer</CENTER></TD><TD><CENTER>4</CENTER></TD></TR>
<TR><TD><CENTER>pointer</CENTER></TD><TD><CENTER>4</CENTER></TD></TR>
<TR><TD><CENTER>float</CENTER></TD><TD><CENTER>4</CENTER></TD></TR>
<TR><TD><CENTER>double</CENTER></TD><TD><CENTER>8</CENTER></TD></TR>
</TABLE></CENTER>
A typical implementation of <TT><FONT COLOR=green>malloc</FONT></TT>
will use an extra 4 bytes every time it allocates a block of memory.
Calculate the overheads for storing various numbers of items
of the types listed using the array and list implementations
of our <TT><FONT COLOR=green>collection</FONT></TT> object.
Overhead here means that if a data structure
requires 1140 bytes to store 1000 bytes of data, the overhead is 14%.
Fill in the table:
<CENTER><TABLE BORDER=2>
<TR><TH><CENTER>Item type</CENTER></TH><TH>Number of items</TH>
<TH WIDTH="25%"><CENTER>Array</CENTER></TH>
<TH WIDTH="25%"><CENTER>List</CENTER></TH></TR>
<TR><CENTER><TD ROWSPAN=2><CENTER>integer</CENTER></TD><TD><CENTER>100</CENTER></TD><TD><PRE> </PRE> </TD><TD><PRE> </PRE> </TD></CENTER></TR>
<TR><TD><CENTER>1000</CENTER></TD><TD><PRE> </PRE> </TD><TD><PRE> </PRE> </TD></TR>
<TR><TD ROWSPAN=2><CENTER>double</CENTER></TD><TD><CENTER>100</CENTER></TD><TD><PRE> </PRE> </TD><TD><PRE> </PRE> </TD></TR>
<TR><TD><CENTER>1000</CENTER></TD><TD><PRE> </PRE> </TD><TD><PRE> </PRE> </TD></TR>
<TR><TD ROWSPAN=2><PRE>struct {
int x, y;
double z[20];
}</PRE></TD><TD><CENTER>100</CENTER></TD><TD><PRE> </PRE> </TD><TD><PRE> </PRE> </TD></TR>
<TR><TD><CENTER>1000</CENTER></TD><TD><PRE> </PRE> </TD><TD> <PRE> </PRE> </TD></TR>
</TABLE></CENTER>
<P>
<HR>
<LI><H3>Complexity</H3>
Modern processors have clock speeds in excess of 100MHz. Thus a RISC processor
may be executing more than 1x10<SUP>8</SUP> machine instructions
per second. This means they can process of the order of 1x10<SUP>7</SUP>
"operations" per second. An "operation" is loosely defined here as something
like one iteration of a very simple loop.
<P>
Assuming that you patience allows you to wait
<OL TYPE="a">
<LI>one second,
<LI>one minute,
<LI>one hour,
<LI>one day.
</OL>
Calculate how large a problem you can solve if it is
<OL TYPE="i">
<LI><B>O(log<SUB>2</SUB> <I>n</I>)</B>
<LI><B>O(<I>n</I>)</B>
<LI><B>O(sqrt(<I>n</I>))</B>
<LI><B>O(<I>n</I> log<SUB>2</SUB> <I>n</I>)</B>
<LI><B>O(log<SUP>2</SUP> <I>n</I>)</B>
<LI><B>O(<I>n</I><SUP>2</SUP>)</B>
<LI><B>O(2<SUP><I>n</I></SUP>)</B>
<LI><B>O(<I>n</I>!)</B>
<LI><B>O(<I>n<SUP>n</SUP></I>)</B>
</OL>
<P>
Numbers beyond the range of your calculator can simply be
reported as "> 10<SUP>x</SUP>" or
"< 10<SUP>-x</SUP>", where x is determined by your calculator.
<P>
To try this in reverse,
assume that to be <I>certain</I> of beating Kasparov in the next
"Man vs machine" chess challenge, we would need to look ahead
40 moves.
How long will it take one of today's computers to calculate
each move?
<BR>
For simplicity, assume that, <I>on average</I>, the number of possible
moves is the same for every move: but if you know of any other estimate
for the number of moves in chess, then use that. And if you don't know
western chess, substitute Chinese chess or Go (and the appropriate current
champion's name!).
<P>
</OL>
<P>
<TABLE WIDTH="100%" BGCOLOR="#00f0ff">
<TR><TD>
<FONT FACE=arial,helvetica><A HREF="tut2.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Tutorials/tut2.html">Tutorials <I>(cont)</I></A><BR>
</TD><TD>
<FONT FACE=arial,helvetica>Back to the <A HREF="ds_ToC.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ds_ToC.html">Table of Contents</A>
</TD></TR>
</TABLE>
<SMALL>
© <A HREF=mailto:morris@ee.uwa.edu.au>John Morris</A>, 1996
</SMALL>
</BODY>
</HTML>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -