c - 如何以随机顺序访问 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]

Answer 2

如果空间和性能不是问题，我想到的第一个解决方案是：创建一个与要访问的数组大小相同的数组；当您生成随机索引时，如果不存在则将其放入此新数组中，否则将其递增并再次检查

Answer 3

0您可以拥有一个包含从到 的数字的数组length of the array，然后对其进行洗牌，然后使用其元素作为索引对其进行迭代。

void shuffle(int *shuffled, int lenght, int times)
{
    int i,j,k;
    int aux;

    j = k = 0;
    for(i=0;i<times;i++)
    {
        do
        {
            j=rand() % length;
            k=rand() % length;
        } while j==k;

        aux = shuffled[j];
        shuffled[j] = shuffled[k];
        suffled[k] = aux;
    }
}

然后，您可以按随机顺序访问元素。

for(i=0;i<lenght;i++)
{
    myNumbers[shuffled[i]];
}

Answer 4

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#define sz 100
uint64_t myNumbers[sz];
long ind[sz];
void shufle(long r){
    long pick,l,t;
    for(l=0;l<r;l++)ind[l]=l;
    l=r;
    while(--l>0){
        pick=((1LL*random())*l)/RAND_MAX;
        t=ind[l];
        ind[l]=ind[pick];
        ind[pick]=t;
    }
} 

main(){
    //tst;
    long i;
    for(i=0;i<10;i++)myNumbers[i]=i;
    shufle(10);
    for(i=0;i<10;i++)printf("%ld %ld\n",i,myNumbers[ind[i]]);
}

Answer 5

使用 while 循环和一个计数器，伪代码应该是：

 uint64_t myNumbers[1000000];
 uint64_t visited[1000000];

 int counter = 0;
 while (counter!=1000000)
 {
  int r = random(0,1000000);
  if (visited.Contains(r))
      break;
  else
     {
      printf(myNumbers[r]); //the action to be performed on the numbers in your array
      visited.add(r);
      counter++;
      }
 }