instruction: What is disadvantage of naive algorithm of simple random sampling?
output: The drawback of this method is that it requires random access in the set.
input: Several efficient algorithms for simple random sampling have been developed. A naive algorithm is the draw-by-draw algorithm where at each step we remove the item at that step from the set with equal probability and put the item in the sample. We continue until we have sample of desired size 
  �
  k. The drawback of this method is that it requires random access in the set.
  
  The selection-rejection algorithm developed by Fan et al. in 1962 requires a single pass over data; however, it is a sequential algorithm and requires knowledge of total count of items 
  �
  n, which is not available in streaming scenarios.
  
  A very simple random sort algorithm was proved by Sunter in 1977. The algorithm simply assigns a random number drawn from uniform distribution 
  (
  0
  ,
  1
  )
  (0,1) as a key to each item, then sorts all items using the key and selects the smallest 
  �
  k items.
  
  J. Vitter in 1985 proposed reservoir sampling algorithms, which are widely used. This algorithm does not require knowledge of the size of the population 
  �
  n in advance, and uses constant space.
  
  Random sampling can also be accelerated by sampling from the distribution of gaps between samples and skipping over the gaps.