如何以随机顺序访问C数组,确保最多访问所有元素一次

Question

假设我有一个非常大的64位整数数组,比如说它们中有一百万像这样定义:

uint64_t myNumbers[1000000];

挑战在于如何随机访问每个元素,确保每个元素都被访问过一次.因此,例如,我可以简单地使用for循环并遍历此数组并将所有数字相加以获得结果(这将溢出,但这并不重要).

我想要做的是重复这一点,但随机访问该数组中的元素,这样我最终得到的结果与普通迭代时的结果相同.

那么我将如何创建另一个指向原始数组元素的指针数组,在迭代它时,它会随机访问每个元素.这不必实时完成,并且设置第二个阵列所花费的时间不必很快.

基本上我想不出一个很好的方法来生成第一个数组中元素的随机指针数组,并且真的可以使用专家的一些见解:)

Answer 1

你想生成一个随机排列(索引数组,或指向原始数组元素的指针数组,或者根据你的使用情况,可能会改变原始数组本身) .

生成随机排列的好方法叫做Knuth shuffle:

To shuffle an array a of n elements (indices 0..n-1):
  for i from n ? 1 downto 1 do
       j ? random integer with 0 ? j ? i
       exchange a[j] and a[i]