How to shuffle a large data set without touching every row?

Question

Let’s say I have two larges arrays of users with equals number of rows and I want to match them randomly and one to one(one from the first array,one from the second), I will first need to shuffle one of the two sets because I need to do this every x hours, and i don’t want matchs to be the same everytime.The problem is that as said they are large, and I don’t want to do a for loop when implementing a shuffle method. Ideally I would like a fonction that takes an index from the first array, and some random generated key and returns me the matching index.

My problem is that I don’t know how to generate such a key. I don’t even know if it’s possible or what to look for.

Answer 1

If you want a stateless way to shuffle, sorry, but that's impossible. A shuffle needs state. If you're content with random pairings that are independent of previous pairings then that can be stateless but it's not a shuffle. In that case your function is just an evenly distributed random number from 0 to length-1.

If you must have a shuffle, are willing to keep some state, but can't be moving users around in their array I have a solution.

Use indirection. You have arrays of users that you don't want to touch. Fine but they're arrays, so you have random access to them. You don't have to move the users. You just have to shuffle an array of indexes into one of them.

Say you have two arrays of 10 girls and 10 boys. Just add an array of 10 ints. Lets call it partner.

let partner = [0,1,2,3,4,5,6,7,8,9]

partner.shuffle()

Your 'function' is now partner[index]. You could use it like this:

dance(
    girls[index],  
    boys[partner[index]]
)

Also, understand that in many languages, and data structures, if you shuffle your array of users you aren't actually moving around the user data. You're moving around a small little reference that points to the user data. That reference is usually no bigger than an int.

If you're in that situation then the indirection provided by partner is pointless. Just shuffle your array directly. If you can't because you have to preserve the original order you can simply make a copy of the references and shuffle the copy.

So be sure you can't directly sort your array before you add a level of indirection you might not need.

As for the issue of large, if you're up against more references than will fit in memory you might want to not assume you have full random access to the array. IO is slow and works better as a stream.

A two pass shuffle can read the array sequentially (as a stream) and work on a chunk small enough to fit in memory as a full blown random access array. Create files for each chunk. Append to the chunks randomly from the whole stream. Then, one at a time, load up each memory sized chunk and shuffle it now that you have fast random access. After that you can append the shuffled chunk into one file for them all.

Here's an artical on this technique that comes with a rather nice visualization:

Answer 2

What you can do is create an independent array of a data structure containing your index keys (1..N) and a random number. Then sort it on the random number. When you need to re-shuffle, update the random numbers and sort it again. I did this last night on a data set of a couple million rows and the sorting time was negligible. I don't know if it would suffice for real-time graphics rendering, but for most other cases the performance should be fine.