feedback2.html
来自「Data Structure Ebook」· HTML 代码 · 共 151 行
HTML
151 行
<HTML><HEAD>
<TITLE>Data Structures and Algorithms - Assignment 2</TITLE>
</HEAD>
<BODY BGCOLOR="#ffffff">
<H1>Data Structures and Algorithms</H1>
<HR>
<CENTER><H3><FONT COLOR=red>
Feedback from assignment 2
</FONT></H3></CENTER>
<OL>
<LI><H4>Toolbuilding</H4>
Many of you failed to take note of the suggestion about
building tools for the timing routine in the feedback for
the last assignment. You need to get into the habit of
building <B>transportable</B>, re-usable tools, so that you
can concentrate on the more difficult aspects of the next
problem, rather than repeating machine-specific code in
<I>every</I> program!
<P>
<LI><H4>Post-Conditions</H4>
<B>No-one</B> seems to have noticed that the
post-condition for <TT>AddToCollection</TT> should have
been augmented with a "CollectionSorted" assertion!
This is simply done with an auxillary routine:
<PRE>
int CollectionSorted( collection c ) {
int i;
for( i=0;i<(c->item_cnt-1);i++)
{
/* item i should be less-than or equal item i+1 */
if( !(memcmp(ItemKey(c->items[i]),
ItemKey(c->items[i+1]), c->size) <= 0) )
return FALSE;
}
return TRUE;
}
</PRE>
<P>
<LI><H4>Ordering Items</H4>
The <TT>memcmp( ItemKey(..), ItemKey(..), size )</TT>
approach to defining the order of items makes some assumptions
about the structure of the item's key.
A much more useful approach is to provide an
<TT>ItemCmp</TT> function,
which can provide a general ordering function.
This function can order the items according to any rule -
not just one which assumes lexicographical ordering of
keys of fixed size.
<P>
Note that if you use one ordering function when adding,
you must use exactly the same function when searching.
<P>
<P>
<LI><H4>Adding on the key</H4>
When adding, quite a few of you compared items using the value of <TT>item</TT>
which is the handle (C pointer) for the object.
You must use <TT>ItemKey</TT> and <TT>memcmp</TT> as in
<TT>bin_search</TT> (or <I>better</I>, an <TT>ItemCmp</TT> function).
<P>
<LI><H4>Normalising</H4>
The computer can calculate <B>log n</B> too!
You need to include the <TT><math.h></TT> header and
compile with:
<CENTER>
<TT>gcc ..... -lm</TT>
</CENTER>
The <TT>-lm</TT> loads the math library.
Some trivial modifications to your program enable one run to
do the experiments and process the results for you too!
<LI><H4>Read the textbooks</H4>
Even for a very simple insertion sort, some of you produced
code with double loops, multiple compare calls, etc.
Simple, <B>proven</B> code for standard problems like this
can be found in almost all texts on data structures and
algorithms!
Spend some time reading, <I>before</I> hacking!
<LI><H4>Designing experiments</H4>
<UL>
<LI>Think first<P>
When searching, most of you searched an <B>n</B>-item
collection <B>n</B> times.
The best experiments searched each collection - no matter
how big it was - a constant, <B>m</B> ( !=<B>n</B> ), times.
Then all you have to do is find a value of <B>m</B> large enough
to give a time greater than the timer resolution for the
smallest collection.
This enables you to find quite accurate times even for small
collections (use <B>m</B> >> <B>n</B>).
This helps when trying to verify log relationships as you need
to have values of <B>n</B> spanning quite a wide range of <B>n</B>,
because <B>dlogn/dn</B> <I>decreases</I> with n.
Some of you were 'misled' when <B>T(n)/logn</B> <I>appeared</I>
to become constant.
In fact to verify a log relationship a set of logarithmically
spaced values of <B>n</B> are best:
<B>n = 1000, 2000, 4000, 8000, 16000, 32000, ...</B>
would have given a clear result!
<LI>Perturbing results<P>
When designing <B>any</B> experiment,
it's important to eliminate all sources of error possible.
Here you are timing certain operations (adds, finds, ..):
make sure that you are timing <B>only</B> those operations!
Thus all unnecessary code should be removed.
<UL>
<LI> This includes function calls -
put the timing code <B>inside</B> the <TT>AddAll</TT>, <I>etc</I>
functions.
<LI> Remove all the code that was originally there to <B>verify</B>
the functions, <I>eg</I> the <TT>if ( ip == &list[i] )</TT>
after the <TT>FindInCollection</TT> call.
</UL>
These things don't perturb your results by very much,
but you can eliminate these sources of error trivially, so
why not do it?
<P>
As many of you will have found,
the cache on a modern processor causes your results to
'creep' slowly towards the predicted result.
If you're doing the experiment carefully and want to ensure
that you've actually proven your hypothesis, then you will
need to eliminate <B>all</B> potential sources of error!
</OL>
<P>
<H4>Users of DOS/Windows machines</H4>
Please make sure that the extra CRs needed by DOS, etc, are
removed before you submit.
Unix files should have LFs only at the end of a line.
<P>
The same applies to reports produced by your word processor:
export them as plain text without the extra CRs.
<P>
Reports which are not plain text will not be accepted -
there are a large number of word processors out there:
it's much more productive (and therefore beneficial for you!)
if the tutors spend time marking
your report's content than trying to work out which WP
will read it!
<HR>
<A HREF="ds_ToC.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ds_ToC.html">Table of Contents</A>
<HR>
<SMALL>
© <A HREF=mailto:morris@ee.uwa.edu.au>John Morris</A>, 1996
</SMALL>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?