-
- Jeffrey S. Vitter
- Brown Univ., Providence, RI
この論文をさがす
説明
<jats:p> We introduce fast algorithms for selecting a random sample of <jats:italic>n</jats:italic> records without replacement from a pool of <jats:italic>N</jats:italic> records, where the value of <jats:italic>N</jats:italic> is unknown beforehand. The main result of the paper is the design and analysis of Algorithm Z; it does the sampling in one pass using constant space and in <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> (1 + log( <jats:italic>N/n</jats:italic> ))) expected time, which is optimum, up to a constant factor. Several optimizations are studied that collectively improve the speed of the naive version of the algorithm by an order of magnitude. We give an efficient Pascal-like implementation that incorporates these modifications and that is suitable for general use. Theoretical and empirical results indicate that Algorithm Z outperforms current methods by a significant margin. </jats:p>
収録刊行物
-
- ACM Transactions on Mathematical Software
-
ACM Transactions on Mathematical Software 11 (1), 37-57, 1985-03
Association for Computing Machinery (ACM)