Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...
Uzunluğu önceden bilinmeyen bir akıştan tek geçişte eşit olasılıklı sabit boyutlu örneklem seçer.
Reservoir sampling, N değerinin bilinmediği veya akışın tamamını bellekte tutmanın mümkün olmadığı durumlarda kullanılır. İlk k eleman reservoir içine alınır; i. eleman için 1..i aralığında rastgele j seçilir ve j <= k ise reservoirdaki j. eleman değiştirilir.
Vitterın çalışması bu problemi “N bilinmeyen kayıtlardan replacement olmadan n örnek seçme” olarak tanımlar ve reservoir algoritmalarının tek geçişli karakterini analiz eder.
Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.
1function reservoirSample(stream: T[], k: number): T[] { 2 const reservoir = stream.slice(0, k);3 for (let index = k; index < stream.length; index += 1) {4 const randomIndex = Math.floor(Math.random() * (index + 1));5 if (randomIndex < k) { reservoir[randomIndex] = stream[index]; }6 }7 return reservoir;8}Akış elemanlarını ve örneklem boyutunu girin. Örnek: a,b,c,d,e,f,g,h; 3
Akış elemanlarını ve örneklem boyutunu girin. Örnek: a,b,c,d,e,f,g,h; 3
En İyi Durum: O(N)
Ortalama Durum: O(N)
En Kötü Durum: O(N)
O(k) - Bu algoritmanın karmaşıklığı belirtilmemiş.
Reservoir Sampling Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar: