First of all, you're right: an index is probably a bad way to solve your problem. It's still possible, (for example, you could generate the index on disk rather than in memory if you needed to), but other monks have already posted other ideas that you might want to try first.

But what we forget is that an Array in Perl is an array of SCALARs, so, we will use much more memory for each position than just 4 bytes. And randomize this array in Perl will copy the array in the memory and use more meory and will be very slow!

This is off topic, but there's a more efficient way to handle very large arrays in Perl. You don't have to use normal arrays: you can construct a single string of packed bytes (using the pack() command), and access the individual elements using the vec() and unpack() commands.

Also, randomizing the array doesn't need to use a copy of the array. Instead, you can randomize your array "in place", by swapping each array element with a random array element, as you loop over the array. I believe this technique is called the "Fischer-Yates shuffle".

-- AC