### Analyzing algorithms by simulation: variance reduction techniques and simulation speedupsAnalyzing algorithms by simulation: variance reduction techniques and simulation speedups

Access Restriction
Subscribed

 Author Mcgeoch, Catherine Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1992 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Experimental analysis of algorithms ♦ Move-to-front rule ♦ Self-organizing sequential search ♦ Statistical analysis of algorithms ♦ Transpose rule ♦ Variance reduction techniques Abstract Although experimental studies have been widely applied to the investigation of algorithm performance, very little attention has been given to experimental method in this area. This is unfortunate, since much can be done to improve the quality of the data obtained; often, much improvement may be needed for the data to be useful. This paper gives a tutorial discussion of two aspects of good experimental technique: the use of variance reduction techniques and simulation speedups in algorithm studies.In an illustrative study, application of variance reduction techniques produces a decrease in variance by a factor 1000 in one case, giving a dramatic improvement in the precision of experimental results. Furthermore, the complexity of the simulation program is improved from $&THgr;\textit{mn}/H\textit{n})$ to $&THgr;(\textit{m}$ + $\textit{n}$ log $\textit{n})$ (where $\textit{m}$ is typically much larger than $\textit{n}),$ giving a much faster simulation program and therefore more data per unit of computation time. The general application of variance reduction techniques is also discussed for a variety of algorithm problem domains. ISSN 03600300 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1992-06-01 Publisher Place New York e-ISSN 15577341 Journal ACM Computing Surveys (CSUR) Volume Number 24 Issue Number 2 Page Count 18 Starting Page 195 Ending Page 212

#### Open content in new tab

Source: ACM Digital Library