
<html xmlns="http://www.w3.org/1999/xhtml"><head> <title></title> <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no"> </head> <body style="font-family:Helvetica;color:#000000;font-size:13px;"><div id="CanaryBody"> <div> Hi!</div><div><br></div><div>The standard algorithm for sampling without replacement is ``O(N)`` expected for ``N < 0.5 * M`` where ``M`` is the length of the original set, but ``O(N^2)`` worst-case. When this is not true, a simple Durstenfeld-Fisher-Yates shuffle [1] (``O(M)``) can be used on the original set and then the first ``N`` items selected. Although this is fast, it uses up a large amount of memory (``O(M)`` extra memory rather than ``O(N)``) and I’m not sure where the best trade off is. It also can’t be used with an arbitrary probability distribution.</div><div><br></div><div>One way to handle this would be to sample a maximum of ``N // 2`` samples and then select the “unselected” samples instead. Although this has a faster expected run-time than the standard algorithm in all cases, it would break backwards-compatibility guarantees.</div><div></div> <div><br></div> </div> <div id="CanarySig"> <div> <div style="font-family:Helvetica;color:#000;font-size:13px;">Best Regards,<div>Hameer Abbasi</div><div><br></div><div>[1] <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle</a></div></div> <div><br></div> </div> </div> <div id="CanaryDropbox"> </div> <blockquote id="CanaryBlockquote"> <div> <div>On Wednesday, Oct 17, 2018 at 7:48 PM, Matthew Brett <<a href="mailto:matthew.brett@gmail.com">matthew.brett@gmail.com</a>> wrote:<br></div> <div>Hi,<br><br>I noticed that numpy.random.choice was very slow, with the<br>replace=False option, and then I noticed it can (for most cases) be<br>made many hundreds of times faster in Python code:<br><br>In [18]: sample = np.random.uniform(size=1000000)<br>In [19]: timeit np.random.choice(sample, 500, replace=False)<br> 42.1 ms ± 214 µs per loop (mean ± std. dev. of 7 runs, 10<br>loops each)<br>IIn [22]: def rc(x, size):<br> ...: n = np.prod(size)<br> ...: n_plus = n * 2<br> ...: inds = np.unique(np.random.randint(0, n_plus+1, size=n_plus))[:n]<br> ...: return x[inds].reshape(size)<br>In [23]: timeit rc(sample, 500)<br>86.5 µs ± 421 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)each)<br><br>Is there a reason why it's so slow in C? Could something more<br>intelligent than the above be used to speed it up?<br><br>Cheers,<br><br>Matthew<br>_______________________________________________<br>NumPy-Discussion mailing list<br>NumPy-Discussion@python.org<br>https://mail.python.org/mailman/listinfo/numpy-discussion<br></div> </div> </blockquote> <img id="6937579613AA7B61E7D7194FA99C4932" width="1px" src="http://pixels.canarymail.io:8100/track/977C99C0645380AF45E168B4CDA443F5_6937579613AA7B61E7D7194FA99C4932.png" height="1px"></body></html>