1

私が64ビット整数の非常に大きな配列を持っているとしましょう。たとえば、100万個が次のように定義されているとします。

uint64_t myNumbers[1000000];

課題は、これらの各要素にランダムにアクセスして、各要素が1回アクセスされるようにする方法です。したがって、たとえば、forループを使用してこの配列を反復処理し、すべての数値を合計して結果を得ることができます（オーバーフローしますが、これは重要ではありません）。

私がやりたいのはそれを繰り返すことですが、その配列内の要素にランダムにアクセスすることで、最終的には通常の反復の場合と同じ結果になります。

では、元の配列要素へのポインターの別の配列を作成して、それを反復処理するときに各要素にランダムにアクセスするにはどうすればよいでしょうか。これはリアルタイムで実行する必要はなく、2番目のアレイのセットアップにかかる時間も高速である必要はありません。

基本的に、最初の配列の要素へのポインターのランダムな配列を生成する良い方法を考えることはできず、専門家からの洞察を実際に使用することができます:)

4

5 に答える 5

6

ランダム順列を生成したい（インデックスの配列、または元の配列の要素へのポインターの配列のいずれか、またはユースケースに応じて元の配列自体をシャッフルすることはおそらく許容されます） 。

ランダム順列を生成する良い方法は、クヌースシャッフルと呼ばれます。

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]
于 2013-02-20T17:17:13.803 に答える
0

スペースとパフォーマンスが問題にならない場合、私の頭に浮かぶ最初の解決策は次のとおりです。アクセスする配列と同じサイズの配列を作成します。ランダムインデックスを生成するときは、存在しない場合はこの新しい配列に配置し、存在しない場合はインクリメントして再度確認します

于 2013-02-20T17:17:39.320 に答える
0

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]];
}
于 2013-02-20T17:18:43.677 に答える
0 
#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]]);
}
于 2013-02-20T17:39:17.750 に答える
-1

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++;
      }
 }
于 2013-02-20T17:21:40.130 に答える