📄 exp_design.html
字号:
<HTML><HEAD>
<TITLE>Data Structures and Algorithms: Experimental Design</TITLE>
<META name="description" content="Data Structures and Algorithms Course Notes,
PLDS210 University of Western Australia">
<META name="keywords" content="data structures,algorithms,abstract data types,
experimental design">
</HEAD>
<BODY BGCOLOR="#ffffff">
<TABLE BGCOLOR="#00c0f0" WIDTH="100%" CELLSPACING=0 CELLPADDING=0>
<TR BGCOLOR="#00f0f0"><TD ALIGN=right>
<FONT FACE=helvetica SIZE=+1><I>Data Structures and Algorithms</I></FONT>
</TD></TR>
<TR><TD><FONT FACE=helvetica SIZE=+2><B>Experimental Design</B></FONT>
</TD></TR>
</TABLE>
<P>
<H3>Designing Experiments</H3>
Designing a good experiment is not a trivial task:
it needs some thought and care if the results of your
work are going to lead to valid conclusions.
While there are many variations of good strategies,
the following basic steps will generally lead to a good
procedure:
<OL>
<LI>Form a <B>hypothesis</B> which your experiment(s) will
test,
<LI>Design some experiments to test this hypothesis,
<LI>Run the experiments and collect the data,
<LI>Analyze your data:
<UL>
<LI>Transform your raw experimental data into a form which
permits readily verifying or disproving the hypothesis,
<LI>Estimate the experimental error in the original data and
transformed data,
<LI>Compare the transformed data with expectations produced
by the hypothesis.
</UL>
<LI>If the experimental data and expected results are in accord
(within the experiment's error limits),
then you have a basis for claiming the original hypothesis
to be true.
<LI>If there is a discrepancy, you have a number of strategies:
<UL>
<LI>Analyse the experiments for sources of error,
<LI>Repeat the experiments to confirm the results (not usually
very profitable for computer based experiments!)
<LI>Re-design the experiments <I>or</I>
<LI>Form a new hypothesis.
</UL>
</OL>
Of course, if you are doing original research (that is,
you are testing some new hypothesis for the first time),
then you now need to form alternative hypotheses and see
whether the experimental data would match them also
and repeat the experiments (or formulate new ones) to
ensure that you can reproduce the original results.
This cycle is potentially never-ending!
<P>
However, for the experiments you will need to do in this course,
the results are well-known and one 'pass' through this process
should suffice!
<H3>Rules</H3>
There are a few very important rules:
<OL>
<LI>You must report <B>all</B> experimental results,
unless they are clearly wrong (<I>eg</I> your program had
an error).
<LI>You may not reject <B>any</B> measurement <I>unless
you can provide an <B>iron-clad</B> argument to
justify its rejection.</I>
</OL>
<P>
An example of an acceptable reason for rejecting or ignoring
a result is:
<BLOCKQUOTE>
The computer's timer has a minimum resolution of 10ms,
so all runs with times less than 1s were ignored
because they could have had errors >1%.
</BLOCKQUOTE>
Of course, a really careful experimenter would not discount
these results either, but confirm that they also matched
the hypothesis - making allowance for the known error.
However, in the interests of efficiency, this level of
precision will not be expected here!
<H4>Reporting results</H4>
It is usual to transform your results to some form which
makes it easy to verify that they conform to the hypothesis.
The most common strategy is linearisation - plotting results
on a graph with axes designed to produce a straight line.
Another good strategy is normalisation - reduction of all
results to a constant value.
This normalisation strategy is a good one to employ here:
assume that you are verifying the time complexity of
quicksort. This is usually a O(nlogn) algorithm.
<UL>
<LI>
Your hypothesis is that quicksort takes <B>n logn</B> time,
or more formally:
<CENTER>
<B>T(n) <= c n log n</B>
</CENTER>
where <B>T(n)</B> is the time to sort <B>n</B> items
and <B>c</B> is a constant.
<LI>
So time a series of sorts of increasingly larger collections
of items.
<LI>
Divide the times by <B>nlogn</B>.
If you have a set of constants, <B>c</B> +/- some suitably small variation,
then the running time may be expressed as:
<CENTER>
<B>T(n) = c n log n</B>
</CENTER>
verifying your hypothesis.
</UL>
Note that you will need to ensure the values of <B>n</B> chosen
for the experiment span a suitably wide range -
so that <B>cn logn</B>, the expected running time also spans
a reasonable range.
For the sort experiment,
this will be satisfied if the largest value of <B>n</B> is
10 times the smallest one - giving times differing by a
factor of ~30 ( 10<B>log<SUB>2</SUB></B>10 ).
<P>
However, if you were timing a search algorithm with <B>O(logn)</B>
time complexity, then values of <B>n</B> ranging over one
order of magnitude will only produce times varying by a factor
of just over 3 (<B>log<SUB>2</SUB>n</B>).
This will generally be insufficient to provide a convincing verification
(over such a small range, other functions of <B>n</B> will also
fit quite well!), so you would need to try to have values of
<B>n</B> ranging over, say, three orders of magnitude, to give
times ranging over one order of magnitude (<B>log<SUB>2</SUB>1000 ~ 10).
<H4>Lecture slides</H4>
You will find some additional points and examples in the
<A HREF="exp_des1.ppt.gz" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ppt/exp_des1.ppt.gz">lecture slides</A>.
<P>
<TABLE CELLPADDING=5 WIDTH="100%" BGCOLOR="#00f0f0" CELLSPACING=4>
<TR><TD WIDTH=50%>
Back to <A HREF="timetable.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Labs/timetable.html">Course Management</A></TD>
<TD>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>, 1998
</SMALL>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -