Scaling to very large vectors?

[dbolser]

Hi, if I want to shuffle a vector of length 100 million (say 1 billion times), is this a suitable approach? The reason I thought that fisher Yates was a good choice was because I only have a few True values in an otherwise False boolean vector (e.g. from 0.001% to about 1% True). Using this info, I can just shuffle the N True indexes in a single pass with Fisher Yates...

Occasionally I have a vector with, say, 50% True, in which case a 'full shuffle' makes sense... but they are always big 😅.

Huge thanks again,

[RAMitchell]

I think you could probably create a much faster version for your custom use case. Our shuffle assumes that we need to move the items around in memory and this actually is the most expensive step.

As an example if you know the positions of the (few) true values you could just run a bijective function on only those values and write them into a zero'd array. You can actually call the bijective function we provide for power of two length sizes and if the value falls outside of your array size you can feed it back in until you get something inside your range. This will not collide with any other value and is a valid bijection.

[dbolser]

Thanks @RAMitchell, sorry, I didn't get alerted to your reply.

I'm not 100% clear on how I'd implement your idea... I can easily get the indexes of the True values in my vector, but how to shuffle them throughout the entire length?

Sorry if this is a stupid question! I'm only learning C / CUDA to try to solve this problem!

Below is just me thinking out-loud, so you can ignore it.

Looking at one of my smaller cases, I have ~2000 vectors of length 1,000,000. Here is the frequency of the percentage of True values across those 2k vectors:

      2    32
      1    19
      1    18
      5    17
      4    16
      3    15
      2    14
      5    13
      2    12
      4    11
      4    10
     12     9
     11     8
     19     7
     24     6
     27     5
     39     4
     70     3
    160     2
    380     1
   1033     0

e.g. exactly two of the ~2k have 32% true, exactly one of the ~2k has 19% true, etc., but over half of the ~2k (1033 vectors) have < 0.5% True (rounded to 0 in my frequency table above).

So although ~90% of the data have 2.5% true or less ((160+380+1022)/1808), there is a 'heavy tail' of vectors with up to ~20% true....

I guess the approach would be to see where one method out performs the other and implement a flag in the code?

Yup.

[djns99]

Hey @dbolser thanks for reaching out,

I will give a simple example to illustrate

First lets start assume this is your starting state:

Input:   0 0 T T 0 0 T 0
Output:  0 0 0 0 0 0 0 0  // Initialise to all false

First you would run the bijective function f (e.g. PhiloxBijectiveFunction) with index of your first True, and write a True value to that location in the output. Lets assume f(2) gives a value of 5

f(2) = 5
Output:  0 0 0 0 0 T 0 0

We can repeat the above for the remaining trues

f(3) = 1
Output:  0 T 0 0 0 T 0 0

f(6) = 3
Output:  0 T 0 T 0 T 0 0

So our final output would be

Output:  0 T 0 T 0 T 0 0

The code on the CPU would look something like

PhiloxBijectiveFunction f(num_elements, DefaultRandomGenerator{});
std::vector<int> all_positions_of_trues = {...};
std::vector<bool> output(num_elements, false); // All values start false

for(auto true_position : all_positions_of_trues) // In parallel
{
   int destination = f(true_position);
   output[destination] = true;
}

The catch is, PhiloxBijectiveFunction only works if num_elements is a power of two. Fortunately, we can work around this by repeatedly calling the function until the result is in range (this will always give you a valid value eventually):

PhiloxBijectiveFunction f(num_elements, DefaultRandomGenerator{});
std::vector<int> all_positions_of_trues = {...};
std::vector<bool> output(num_elements, false); // All values start false

for(auto true_position : all_positions_of_trues) // In parallel
{
   int destination = f(true_position);
   while(destination >= num_elements) { destination = f(destination); }
   output[destination] = true;
}

I hope this makes sense!

[dbolser]

Thanks @djns99!

I guess I'd simply call it again if my output[destination] is already true?

From what I can see this will be rare in most of my cases, and will be simple enough to check in the while loop...

[RAMitchell]

It will actually never collide. This is why we use these bijective functions.

[dbolser]

It will actually never collide. This is why we use these bijective functions.

Right, sorry, I realised after I posted, if I didn't mind collisions, I wouldn't need a shuffle function 😅