Algorithms for choosing a number uniformly randomly from a subset of integers
Suppose int array a [i] = i, i = 0, 1, 2, ..., N-1. Now, given that every integer will be associated with a bit. I need an algorithm to evenly randomly select an integer from a subset of integers, the appended bit is 0. This assumes that the total number of integers appended bit is 0 is already given in the variable T.
One straight forward solution is to generate r = rand ()% T and then find an r-dimensional integer whose associated bit is 0 (by testing i = 0,1, ...). However, I wonder if there were any decent algorithms for this? Also, given that the associated bits are stored in some long Int variables (which is true in my case), finding the rth integer associated with bit 0 will not be an easy task.
Thanks for your data.
source to share
If the associated bits are irregular, i.e. cannot be deduced from a value i
by a simple formula, it is simply impossible to find a bit r-th '0'
without listing those that precede, unless preprocessing is enabled.
A good solution is to precompile the table, which will store the indexes of the records bit '0'
contiguous and look for that table to record r-th
. (Instead of an index table, you can also populate another array with elements from only a subset.)
Indexing an array of packed bits is not such a big deal. Assuming 64 bits long ints
, the bit in the index i
is in the expression
(PackedBits[i >> 6] >> (i & 63)) & 1
(<< 27> because 64 == (1 << 6)
.)
If you really want to find consistently r-th '0'
, you can speed up the search a bit (x 64) by pre-calculating the count '0's
in each long int so that you can skip 64 entries in the one-shot.
And if you really don't want to precompute anything, you can still speed up the lookup by processing bits 8 by 8 using a static table that associates each byte value (among 256
) with the number of '0'
bits in it. (Or even 16 by 16 if you can afford to use a table of numbers 65536
.)
source to share
You can speed this up by using trade memory for speed.
T must be an array that stores in T [n] the number of integers in [] that have bit n, and this must be precomputed at some point. So, while you are calculating this, keep the indices of all integers that have a given bit cleared in another 2-dimensional array, indexed by the bit number and r.
In C, for example:
#define BITS (64)
#define N (100)
long int a[N];
int T[BITS];
int index[BITS][N];
void init()
{
int i, j;
// clear T:
for(j = 0; j < BITS; j++)
T[j] = 0;
// compute T and the indices for each:
for(i = 0; i < N; i++)
{
for(j = 0; j < BITS; j++)
{
if((a[i] & (1 << j)) == 0)
{
// increment T and store the index
index[j][T[j]++] = i;
}
}
}
}
Then you can find your random number like this:
long number = N[index[bit][rand() % T[bit]];
You could make it more memory efficient by using a less wasteful data structure that only stores as many indices for each bit as there are actual values in [] that bit is cleared.
source to share