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  (``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.
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.