5 ms·
Thanks for the clarification, thats exactly what I was wondering about. I have two questions: - is it a common problem to have, not knowing the set size? - is
by MrBuddyCasino 12y ago
Thanks for the clarification, thats exactly what I was wondering about. I have two questions:
- is it a common problem to have, not knowing the set size?
- is it O(N), or rather O(n)? My intuition tells me it depends on whether or not I have to retrieve every record in the set or not, because I/O should still be much more expensive than random number generation.
- bo1024 12y ago> - is it a common problem to have, not knowing the set size? One motivating case is when the items arrive over time, like you have a website and you want to sample uniformly from your visitors over the course of the next hour. You don't need to know how many people will arrive.
- csl 12y ago> is it a common problem to have, not knowing the set size? Yes. It could be as simple as receiving values from a Python generator (or equivalent mechanism in your favourite language), where you don't know the number of items beforehand (and querying for the length is either impossible or expensive). In such a cases, using reservoir sampling is an elegant solution, because you're probably in a situation where you'll be iterating through all values anyway.
- bradleyjg 12y agoImagine you are writing software to sit on a router to: 1) collect data for some length of time, and 2) thereafter have available for querying the (maybe approximate) 25th, 50th, 95th, and 99th percentile TCP connection bandwidth thresholds, and 3) signal when a connection grows beyond the 95th percentile. You only have a fairly limited amount of memory.
- x0x0 12y agoWhile it's great for medians, reservoir sampling for calculating high or low percentiles, particularly with high dynamic range data, will probably have very high error.