Select record uniformly

You need read a lot of records and you don’t know how many records here before you complete it. After you read all those records, you need select one record randomly. In another words, every record has same chance to be selected. The memory is limited, that means you cannot store all those records at one time.

C++:
01 int pickRecord(int* A, int size)
02 {
03     int tmp=A[0];
04     srand(time(0));
05     for(int i=1;i<size;i++){
06 
07         float p=(float)1/(i+1);
08         float q=((float)rand())/((float)RAND_MAX);
09         if(q<p)
10             tmp=A[i];
11     }
12     return tmp;
13 }
Advertisements
This entry was posted in Number trick, Probability. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s