5 ms·
You select N from M, in order, where M is "too big" and N fits in memory / swap / disk. You then shuffle your N selections to get random ordering.
by web007 7y ago
You select N from M, in order, where M is "too big" and N fits in memory / swap / disk. You then shuffle your N selections to get random ordering.
- supergarfield 7y agoI understand "you can't use any kind of data structure to remember which cards you've already picked among 2^64 of them" as "N cards don't fit in memory". Or is the relevant distinction memory vs disk, as it's feasible to randomize on-disk data?
- svat 7y agoThe problem asks to find k cards (integers) out of n, in time O(k) and O(1) additional space — this means additional to the k required to store the output. So while holding n items wouldn't fit in memory, it is implicit that k would. But we still want to avoid Ω(k log k) time, or more than a constant amount of additional space.
- aasasd 7y agoNot sure that this qualifies as uniform distribution, even if you spread the N across the M. Because the selection must be predictable, so that any next N don't include the previous ones. That's presuming that the ‘user’ might iterate over M items in total, even if you pick chunks of N internally.