3
$\begingroup$

How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place?

If the file had size $2^m$, then we can first split the file into 2-byte chunks, shuffle them individually, then shuffle each set of neighboring 2 chunks and merge, doing this recursively. Merging can be done using constant memory by reading the start of a chunk and swapping them with another.

But if the file size is not $2^m$ then the above doesn't really work, as for a 3-byte file the last byte cannot be in the middle position. (the chunks here are [1, 2] and [3]).

[EDIT] This doesn't generate all permutations as Yuval Filmus points out.

[EDIT 2] The paper "Random permutations on distributed, external and hierarchical memory" seems like a close match. Other refs/ideas welcome.

$\endgroup$
  • 1
    $\begingroup$ To clarify the rules: can we keep pointers to some byte in the file? That requires $O(\log N)$ memory where $N$ is the file size -- can we regard that as "constant memory"? Or are we allowed to move through the file only as a Turing Machine head, for instance? $\endgroup$ – chi Dec 17 '15 at 12:18
  • $\begingroup$ @chi Yes absolutely. $\endgroup$ – simonzack Dec 17 '15 at 14:17
  • $\begingroup$ Looking up "shuffling" on Wikipedia takes you to en.wikipedia.org/wiki/Shuffling, which has a section on algorithms. Don't forget to check resources like this when possible, before asking! $\endgroup$ – D.W. Dec 17 '15 at 22:21
  • 1
    $\begingroup$ @D.W. Thanks but I'm particularly interested in on-disk shuffling, which is a bit harder to find. $\endgroup$ – simonzack Dec 18 '15 at 4:08
5
$\begingroup$

The algorithm you suggest doesn't result in a uniform permutation. An in-place algorithm which works for every file size is the Fisher–Yates shuffle.

$\endgroup$
  • $\begingroup$ Good point, Fisher-Yates would reduce the problem to shuffling each block then all blocks, so we only need the file size to be a multiple of the block size. Do you know how to modify this when it's not? $\endgroup$ – simonzack Dec 17 '15 at 11:28
  • $\begingroup$ No, what you suggest is a bad idea. It doesn't result in a uniform permutation. Use Fisher-Yates to shuffle the bytes rather than the blocks. $\endgroup$ – Yuval Filmus Dec 17 '15 at 11:30
  • $\begingroup$ I would still like to use blocks when possible since there's still a question of efficiency. Why is it not uniform? If the file size is a multiple of the block size, then the chance of $i$ being at position $j$ is the chance it's at the correct block times the chance it's in the correct relative position, which is the same for all $i$. $\endgroup$ – simonzack Dec 17 '15 at 11:33
  • 3
    $\begingroup$ It's not uniform even if you have two blocks of two bytes each - you only get 8 of the 24 possible permutations. Efficiency would have to suffer if you want a uniformly random permutation - a random permutation mixes different blocks a lot. $\endgroup$ – Yuval Filmus Dec 17 '15 at 11:35
2
$\begingroup$

Raw idea:

  1. Divide your file in blocks sized with the available memory. Use Fisher-Yates to shuffle the blocks.

  2. Shuffle merge the blocks by group of 2 (when it remains $N_A$ bytes in block A and $N_B$ bytes in block B, take the byte of block A with probability $N_A/(N_A+N_B)$), for now consider that we are not trying to do that in place and put the result in another file.

  3. Repeat, at each step the size of the block is doubled, until there is only one block. You have your shuffling.

  4. To make it in replace, remark that this is in fact a merge sort using random choice instead of comparison. Thus adapt a in-place merge sort algorithm, using shuffling merge instead of sorting merge for the merge step (IIRC, you'll need $O(\log N)$ file positions for that, but I doubt it will dominate the three disks sectors buffers needed somewhere in the system to make it works)

$\endgroup$
  • 1
    $\begingroup$ I am pretty sure that this algorithm does not result in a uniform permutation, too. Why do you think it does? You try to be very fair an favour the selection of an element of B if a lot o elements of A are already selected ( and so $N_A<N_B$, but thid id very unfair. Also this algorithm seems to be rather inefficient. You copy the file $\log N$ times. $\endgroup$ – miracle173 Dec 17 '15 at 22:37
  • $\begingroup$ @miracle173, The algo to merge two permutations is not from me. I though it was an exercise in TAOCP, but a quick look show that I'm probably mistaken. I must have another source for it, I'll look for it or try to reprove the correctness. $\endgroup$ – AProgrammer Dec 18 '15 at 6:36
  • $\begingroup$ About the copying, if you know something better than copying the file $\log N$ times considering the wide discrepancy between memory and disk, especially for non sequential access, I'd like to know it. (Even in memory, considering how better it is to do a sequential access I'd not be surprised that a sequential algorithm repeated $O(\log N)$ times is not better when you access enough memory that TLB trashing occurs). What I'm sure is that nothing efficient will be oblivious to the memory hierarchy. $\endgroup$ – AProgrammer Dec 18 '15 at 6:37
  • $\begingroup$ I think I was wrong. Using theses probabilities is necessary. $\endgroup$ – miracle173 Dec 19 '15 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.