5 ms·
How does this handle files that are gigs in size? It looks to me like you load the entire file into memory and pass it along, shuffled.
by wodenokoto 11y ago
How does this handle files that are gigs in size? It looks to me like you load the entire file into memory and pass it along, shuffled.
- mappu 11y agoIf you have an unknown input size and a finite number of requested output lines, you can still do it in O(n) and no additional memory, by having a steadily-decreasing chance of replacing one of the outputs with the next line.
- sgk284 11y agoSee: reservoir sampling [1] [1] https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling