3r33177. 3r3-31. Reservoir sampling (eng. “Reservoir sampling”) is a simple and effective algorithm for randomly selecting a certain number of elements from the existing vector of large and /or unknown size in advance. I did not find a single article about this algorithm on Habré, so I decided to write it myself. 3r3146.  3r33177. 3r3146.  3r33177. So, what is at stake. Selecting one random element from a vector is an elementary task:
 3r33177. 3r3146.  3r33177.
3r311. //C ++
std :: random_device rd; 3r33177. std :: mt19937 gen (rd ()); 3r33177. std :: uniform_int_distribution <> dis(0, vect.size() — 1);
3r33177. auto result = vect[dis(gen)]; 3r33177. 3r318.
3r3146.  3r33177. The task of “returning K random elements from a vector of size N” is already trickier. Here you can make a mistake - for example, take the K first elements (this violates the requirement of randomness) or take each of the elements with a probability of K /N (this violates the requirement to take exactly K elements). In addition, it is possible to implement a formally correct, but extremely inefficient solution to “randomly mix all the elements and take the first K”. And everything becomes even more interesting if we add the condition that N is a very large number (we don’t have enough memory to save all N elements) and /or not known in advance. For example, imagine that we have some kind of external service that sends us items one by one. We do not know how many of them will come in and cannot save them all, but we want at any time to have a set of exactly K randomly selected elements from those already received. 3r3146.  3r33177. 3r3146.  3r33177. The reservoir sampling algorithm allows us to solve this problem in O (N) steps and O (K) memory. In this case, it is not necessary to know N in advance, and the condition of randomness of the sample of exactly K elements will be clearly observed. 3r3146.  3r33177. Wikipedia article 3r3162.
 3r33177. 3r3-33160. 3r3161. std :: sample on Cppreference
 3r33177.
3r3173. 3r33177. 3r33177. 3r33177. 3r33170. ! function (e) {function t (t, n) {if (! (n in e)) {for (var r, a = e.document, i = a.scripts, o = i.length; o-- ;) if (-1! == i[o].src.indexOf (t)) {r = i[o]; break} if (! r) {r = a.createElement ("script"), r.type = "text /jаvascript", r.async =! ? r.defer =! ? r.src = t, r.charset = "UTF-8"; var d = function () {var e = a.getElementsByTagName ("script")[0]; e.parentNode.insertBefore (r, e)}; "[object Opera]" == e.opera? a.addEventListener? a.addEventListener ("DOMContentLoaded", d,! 1): e.attachEvent ("onload", d ): d ()}}} t ("//mediator.mail.ru/script/2820404/"""_mediator") () (); 3r3171. 3r33177. 3r3173. 3r33177. 3r33177. 3r33177. 3r33177.