Was ist der Nachteil des naiven Algorithmus der einfachen Zufallsstichprobe?
Es wurden mehrere effiziente Algorithmen für einfache Zufallsstichproben entwickelt. Ein naiver Algorithmus ist der Draw-by-Draw-Algorithmus, bei dem wir bei jedem Schritt das Element in diesem Schritt mit gleicher Wahrscheinlichkeit aus der Menge entfernen und das Element in die Stichprobe aufnehmen. Wir fahren fort, bis wir eine Stichprobe mit der gewünschten Größe haben
�
k. Der Nachteil dieser Methode ist, dass sie einen zufälligen Zugriff auf die Menge erfordert.

Der von Fan et al. 1962 entwickelte Auswahl- und Ablehnungsalgorithmus benötigt nur einen einzigen Durchgang über die Daten; es handelt sich jedoch um einen sequentiellen Algorithmus, der die Kenntnis der Gesamtzahl der Elemente erfordert
�
n, die in Streaming-Szenarien nicht verfügbar ist.

Ein sehr einfacher Zufalls-Sortieralgorithmus wurde 1977 von Sunter bewiesen. Der Algorithmus weist einfach eine Zufallszahl aus einer Gleichverteilung zu
(
0
,
1
)
(0,1) als Schlüssel für jedes Element, sortiert dann alle Elemente anhand des Schlüssels und wählt das kleinste
�
k Artikel aus.

J. Vitter schlug 1985 Algorithmen für das Reservoir Sampling vor, die heute weit verbreitet sind. Dieser Algorithmus erfordert keine Kenntnis der Größe der Grundgesamtheit
�
n im Voraus zu kennen, und verwendet einen konstanten Raum.

Die Stichprobenziehung kann auch beschleunigt werden, indem die Verteilung der Lücken zwischen den Stichproben herangezogen und die Lücken übersprungen werden.
Der Nachteil dieser Methode ist, dass sie einen zufälligen Zugriff auf die Menge erfordert.
What is disadvantage of naive algorithm of simple random sampling?
Several efficient algorithms for simple random sampling have been developed.[3][4] 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[5] 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.[6] 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[7] 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[8] and skipping over the gaps.
The drawback of this method is that it requires random access in the set.