This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of TS status.
sample() algorithmSection: 10.3 [fund.ts::alg.random.sample] Status: TS Submitter: Joe Gottman Opened: 2014-12-17 Last modified: 2017-07-30
Priority: 0
View all issues with TS status.
Discussion:
Addresses: fund.ts
According to paragraph 10.1 of the Library Fundamentals 1 draft, the complexity of the new
std::experimental::sample template function is 𝒪(n). Note that n is actually
a parameter of this function, corresponding to the sample size. But both common algorithms for
sampling, the selection algorithm and the reservoir algorithm, are linear with respect to the
population size, which is often many orders of magnitude bigger than the sample size.
[2015-02, Cologne]
AM: I suggest we make this a DR against the Fundamentals TS.
GR: Agreed, this is a no-brainer.
Proposed resolution:
This wording is relative to N4335 in regard to fundamental-ts changes.
Change 10.3 [fund.ts::alg.random.sample] p5 to read:
-5- Complexity: 𝒪(
).nlast - first