11–15 of 15 posts
My immediate thought before reading the article is that shuffling is the inverse of sorting. To put another way, you can take a sorted list and apply a merge sort on it, but the comparison operation is random. Merge sort can work on data sets that are too large to fit in memory since you sort small sized blocks that do fit in memory, then merge using streaming
Shuffling and sorting don’t seem related at all. Naively, I would expect shuffle to be linear in time complexity.
My immediate thought before reading the article is that shuffling is the inverse of sorting. To put another way, you can take a sorted list and apply a merge sort on it, but the comparison operation is random. Merge sort can work on data sets that are too large to fit in memory since you sort small sized blocks that do fit in memory, then merge using streaming
You can't just randomize the comparison operation, since that'd violate the requirements of a comparison function. MS made that mistake in their browser download dialog, which led to significant biases. You'd need to assign a random number to each item. But then you'd need to figure out a way to store this random number. Also, for in-memory data comparison-based sorting is much slower than shuffling. Both asymptotica…
Earlier quoted context omitted.
Do you have a cheap permutation function for large n? It seems like you still have to do it in two passes if you do this. One reason cited in TFA for the half-shuffled files approach is that it's easy to rotate old data out of and new data into the half-shuffled files.
There are format preserving encryption algorithms which act as a pseudo random permutation of integers with a variable upper bound. These slower than Fisher-Yates for in memory data, but for on disk data the random access overhead should exceed their cost. The advantage of this approach is minimal memory use and no need to modify the data. The downside is that it still needs one random read access per element, so cac…
For example, using the permuted the index mod M rather than random draw in the first pass could avoid the whole issue of oversized piles and the extra wasted space per pile.
My immediate thought before reading the article is that shuffling is the inverse of sorting. To put another way, you can take a sorted list and apply a merge sort on it, but the comparison operation is random. Merge sort can work on data sets that are too large to fit in memory since you sort small sized blocks that do fit in memory, then merge using streaming
You can't just randomize the comparison operation, since that'd violate the requirements of a comparison function. MS made that mistake in their browser download dialog, which led to significant biases. You'd need to assign a random number to each item. But then you'd need to figure out a way to store this random number. Also, for in-memory data comparison-based sorting is much slower than shuffling. Both asymptotica…
Probably performance wouldn't be as good as the OP article though.