У чому недолік наївного алгоритму простого випадкового вибірки?
Розроблено кілька ефективних алгоритмів для простого випадкового відбору зразків. Наївний алгоритм - це алгоритм чергування за чергуванням, де на кожному кроці ми з однаковою ймовірністю видаляємо пункт на цьому кроці з набору і вкладаємо пункт в зразок. Продовжуємо, поки не отримаємо зразки бажаного розміру.
І
Недоліком цього методу є те, що він вимагає випадкового доступу в набір.

Алгоритм вибору-відхилення розроблений Fan et al. у 1962 році вимагає єдиного проходження даних; однак, це послідовний алгоритм і вимагає знання загального числа елементів
І
n, яка не доступна в потокових сценаріях.

Дуже простий алгоритм випадкового сортування був доведений Sunter в 1977 році. Алгоритм просто призначає випадкове число, витягнуте з однорідного розподілу
(від
0 0
,
1
)
(0,1) як ключ до кожного елемента, потім сортує всі елементи за допомогою ключа і вибирає найменший
І
з предметами.

У 1985 році Дж. Віттер запропонував алгоритми вибірки резервуарів, які широко використовуються. Цей алгоритм не вимагає знання розміру населення.
І
n заздалегідь і використовує постійний простір.

Використання випадкових зразків також може бути прискорене шляхом вибірки з розподілу прогалин між зразками та пропускання прогалин.
Недоліком цього методу є те, що він вимагає випадкового доступу в набір.