단순 무작위 샘플링의 나이브 알고리즘의 단점은 무엇인가요?
단순 무작위 샘플링을 위한 몇 가지 효율적인 알고리즘이 개발되었습니다. 순진한 알고리즘은 각 단계에서 동일한 확률로 해당 단계의 항목을 세트에서 제거하고 해당 항목을 샘플에 넣는 무승부 알고리즘입니다. 원하는 크기의 샘플을 얻을 때까지 계속합니다.
�
k. 이 방법의 단점은 집합에서 무작위 액세스가 필요하다는 것입니다.

1962년 Fan 등이 개발한 선택-거부 알고리즘은 데이터를 한 번만 통과하면 되지만, 순차적 알고리즘이며 항목의 총 개수에 대한 지식이 필요합니다.
�
n에 대한 지식이 필요하며, 스트리밍 시나리오에서는 사용할 수 없습니다.

1977년 선터에 의해 매우 간단한 랜덤 정렬 알고리즘이 증명되었습니다. 이 알고리즘은 균등 분포에서 추출한 난수를 할당하기만 하면 됩니다.
(
0
,
1
)
(0,1)을 각 항목의 키로 지정한 다음 키를 사용하여 모든 항목을 정렬하고 가장 작은 항목인
�
k 항목을 선택합니다.

J. 1985년 비터는 저수지 샘플링 알고리즘을 제안했으며, 이는 널리 사용되고 있습니다. 이 알고리즘은 모집단의 크기에 대한 지식이 필요하지 않습니다.
�
n을 미리 알 필요가 없으며, 일정한 공간을 사용합니다.

무작위 샘플링은 샘플 사이의 간격 분포에서 샘플링하고 간격을 건너뛰는 방식으로 가속화할 수도 있습니다.
이 방법의 단점은 집합에 무작위 액세스가 필요하다는 것입니다.
What is disadvantage of naive algorithm of simple random sampling?
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.
The drawback of this method is that it requires random access in the set.