asked on

efficiently iterating over a array in random order

Say I have an array that is 1000 long, and I want to iterate over it, but in a random order. I want to hit each member exactly once.

What I could do, is store a 1000 long list of booleans (initially set to false), then just keep picking a random number between 0 and 1000, and if the boolean is not true, I will know that I haven't hit this one yet, so operate on it and set the flag to true. Of course, as I get towards the end, I will have far more misses than hits, and it could be quite inefficient.

Alternatively, I could give each member a random value, and then sort the list by this random value. At least this way is more predictable as to how long it will take, but it still seems kinda "brute force".

I suspect there is a better way. Any ideas?

ASKER CERTIFIED SOLUTION

Jaime Olivares

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

manish_regmi

hi,
You can use a structure. I mean an array of structures.
Implementing your boolean idea.
struct m{
int value;
boolean hit;
}

struct m mx[1000];

-->as I get towards the end, I will have far more misses than hits.
Of course if yoy are doing it randomly. You can have misses.

regards manish

catbutt

ASKER

Thanks jaime, that was the kind of thing i was looking for.

Since I don't want to reorder my original array, I think I will use an array of indices, initialize them to have the values 0 to 999, scramble them as you describe, then use them to process my main array. Alternatively I could have an array of pointers to members of the main array and scramble them.

int scrambledIndices[1000];

// initialize
for (i=0; i<1000; i++)
scrambledIndices[i] = i;

// scramble
for (i=0; i<1000; i++)
swap (&scrambledIndices[i], &scrambledIndices[random(1000)]);

// process
for (i=0; i<1000; i++)
process (&mainArray[scrambledIndices[i]]);

(and thanks manish, but I know how to use structures, I was looking for help with the actual algorthm)

brer_vole

An alterative is to write a pseudo random number generator. These sequences repeat after a known length, but no number repeats until that point.

Here is a 4 bit PRNG (Fibonacci implementation), with a sequence length of 15:

BIT_LENGTH= 4, TAP_POS_1 = BIT_LENGTH, TAP_POS_2 = BIT_LENGTH-1
for(i=0;i<20;i++) {
      d_tap1 = (d & (1<< (TAP_POS_1 -1))) ? 1 : 0;
      d_tap2 = (d & (1<< (TAP_POS_2 -1))) ? 1 : 0;
      d_input = !(d_tap1 ^ d_tap2);
      d = ((d << 1) | (d_input) ) & ((1<<BIT_LENGTH)-1);
      printf("%x ", d);
}

Which outputs: 8 0 1 3 7 e d b 6 c 9 2 5 a 4 8 0 1 3 7

Page 12 of the following link shows the tap positions for longer sequence lengths.
http://www.xilinx.com/ipcenter/catalog/logicore/docs/lfsr.pdf