Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (516)
Games in Android Showcase (122)
games submitted by our members
Games in WIP (577)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  Iterate each element of a collection randomly once only  (Read 9356 times)
0 Members and 1 Guest are viewing this topic.
Offline moogie

JGO Knight


Medals: 13
Projects: 6
Exp: 10 years


Java games rock!


« Posted 2012-06-14 02:50:25 »

Does anyone know of an algorithm that will visit each element of a collection, lets say an array, once only but in a pseudo random manner?

My array has potentially many many elements (i.e. 2^28) so storing which elements that have been visited nor generating a random index sequence are viable options.

I am hoping that there is an algorithm, given a random seed will and the current loop count will give the next element index with the constraint that index returned is unique and thus will achieve coverage over all elements when the loop count == the number of elements in the array.

i.e.

1  
2  
3  
4  
5  
6  
7  
long seed = new Random().nextLong();
for (i=0;array.length;i++)
{
int index = nextIndex(long,i);
Object element = array.get(index);
// use element
}



Offline UprightPath
« Reply #1 - Posted 2012-06-14 03:24:53 »

Well, this method isn't completely random, but it might work for what you need.

1) Ensure that your list's length is a multiple of X (Some value), padding it if you need to.
2) Randomly select an index point in your array. This is your start index.
3) Randomly select an iteration direct (boolean up/down) and a move direction (boolean up/down).
3) Iterate through your list from your start index, jumping X elements in your iteration direction each time, wrapping around start/end when you get there.
4) When you get your start index, move once in your move direction unless you've moved X times, then go back to 3.

So, let's say you pick '3' as your X. And you have an int array {5, 2, 3, 4, 0, 1, 9, 6, 7, 8, 10, 11}.
Start at index 3. Iterate up, move down. currIndex = 3
1) array[3] = 4 (Start)
2) array[6] = 9
3) array[9] = 8
4) array[0] = 5
5) array[2] = 3 (Move one down)
6) array[5] = 1
7) array[8] = 7
Cool array[11] = 11
9) array[1] = 2 (Move one down)
10) array[4] = 0
11) array[7] = 6
12) array[10] = 10 (Over)

If you want to make it more fancy, you can layer this...

I'll update with a pastebin in a moment. ^^;

Offline moogie

JGO Knight


Medals: 13
Projects: 6
Exp: 10 years


Java games rock!


« Reply #2 - Posted 2012-06-14 04:06:41 »

Inspired by your solution, i have come up with a solution that seems to work for odd numbered elements...

1. pick a random positive integer R1
2. create a step interval I by multiplying the next whole integer after dividing the number of elements by 2 and then multiplying that by R1 and then add 1. i.e. R1 = ((int) (Math.max(((double)array.length)/2))*R1 + 1
3. pick a random index as the start point R2
4. set current index to R2. i.e. index = R2
5. the next index will be: index = (index +1 + I ) % array.length;
6. repeat step 5 until all elements visited.

now to see whether i can find one for even numbers.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline davedes
« Reply #3 - Posted 2012-06-14 04:25:24 »

I suppose you can't shuffle the array and then simply walk through it?

Or you could use a "linear congruential generator" -
http://math.stackexchange.com/questions/45288/non-repeating-random-number-generation-with-xi1-xi-increment-mod-m
http://www1.i2r.a-star.edu.sg/~knandakumar/nrg/Tms/Probability/Probgenerator.htm
http://static.usenix.org/event/usenix99/full_papers/deraadt/deraadt_html/node17.html

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 823
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2012-06-14 05:00:33 »

If you really don't want to make a copy of the collection, you can add a layer of indirection.

Create an int[collection.size()] filled with the values: {0,1,2,...,collection.size()-1}. Then shuffle that. Then iterate over your int[] and use the values (indices) to lookup elements in the original collection.

Making a copy of the original collection and shuffling that is a lot easier though.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline sproingie

JGO Kernel


Medals: 202



« Reply #5 - Posted 2012-06-14 05:03:40 »

I am hoping that there is an algorithm, given a random seed will and the current loop count will give the next element index with the constraint that index returned is unique and thus will achieve coverage over all elements when the loop count == the number of elements in the array.

Impossible.  It would require a RNG with perfect distribution equal to its period, which would mean it would be the opposite of random, as each output would depend on all previous ones.

Quickest solution I can think of off the top of my head is walk down the array once and swap each item with a randomly selected one (this may in fact be the algorithm for shuffle, but you can write it by hand for arrays)

Offline UprightPath
« Reply #6 - Posted 2012-06-14 05:30:46 »

Inspired by your solution, i have come up with a solution that seems to work for odd numbered elements...

1. pick a random positive integer R1
2. create a step interval I by multiplying the next whole integer after dividing the number of elements by 2 and then multiplying that by R1 and then add 1. i.e. R1 = ((int) (Math.max(((double)array.length)/2))*R1 + 1
3. pick a random index as the start point R2
4. set current index to R2. i.e. index = R2
5. the next index will be: index = (index +1 + I ) % array.length;
6. repeat step 5 until all elements visited.

now to see whether i can find one for even numbers.

Even looking at this method, I don't believe that it would work. By that, besides the fact that at least one of your method calls listed is incorrect (Math.max(double value)?) Anyway, about 10% of the time when I try this algorithm (If I have it written correctly, hah!) I end up with it repeating the same element each time.
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
   public SemiRandomIteratorOdd(List<?> collection) {
      this.collection = collection;
      r1 = Math.abs(random.nextInt());
      interval = Math.abs((int) Math.ceil((double)collection.size() / 2.0) * r1 + 1);
      r2 = random.nextInt(collection.size());
      currIndex = r2;
      System.out.println("Index: " + currIndex + " interval: " + interval);
   }
   public Object getNext() {
      Object o = collection.get(currIndex);
      currIndex = (currIndex + 1 + interval) % collection.size();
      totalIterations++;
      return o;
   }


Shallow Copy + Shuffling might be the best way you can do it.

I have some code which might work assuming you can figure out two common factors for your list size (IE, it's not a prime). It's here: http://pastebin.java-gaming.org/54a6b9d041c

Offline moogie

JGO Knight


Medals: 13
Projects: 6
Exp: 10 years


Java games rock!


« Reply #7 - Posted 2012-06-14 07:22:26 »

@sproingie: Yep, I kind of thought that a true random sequence is not possible, but fortunately it is not required, only to be "random-looking"

@UprightPath: i think i have found the issue... the interval needs to be a positive prime number. (i have to check this out first). Will have a look at your code shortly.

@Riven: i would like to avoid shuffling... due to memory constraints (two arrays of 2^28 elements is quite alot ) but may have to just shuffle.

@davedes: will investigate those links and see if i can use them. thanks
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #8 - Posted 2012-06-14 07:40:43 »

@Riven: i would like to avoid shuffling... due to memory constraints (two arrays of 2^28 elements is quite alot ) but may have to just shuffle.

Knuth Shuffle is in-place, so I'd go with that (don't know if that's what Collections.shuffle does or if you'll have to implement it yourself though).

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle


Edit: didn't realise you need the original array unchanged afterwards. In that case, then perhaps find a reversible random number generator so you can 'unshuffle' by doing it in reverse.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 823
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2012-06-14 08:01:51 »

@sproingie: Yep, I kind of thought that a true random sequence is not possible, but fortunately it is not required, only to be "random-looking"
Can't you simply chop your collection into interleaved chunks:

0,1,2,3,...,n,0,1,2,3,...,n,0,1,2,3,...,n,0,1,2,3,...,n,0,1,2,3,...,n,etc

Make a temporary list of chunk 0, shuffle it, iterate over them.
Make a temporary list of chunk 1, shuffle it, iterate over them.
Make a temporary list of chunk 2, shuffle it, iterate over them.

It will certainly look random, and returns every element once.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #10 - Posted 2012-06-14 08:25:54 »

What do you really what to do here?  This sounds likes you have a broken problem statement to me.

To answer you question as posed...use a quasi-random number generator.  The simplest would be to rearrange the bits of the index in fixed pattern.  This is easiest when the size in insured to be power-of-two...otherwise it gets trickier.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 823
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2012-06-14 08:27:02 »

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
public class Main {
   public static void main(String[] args) {

      List<String> values = new ArrayList<String>();
      for (int i = 0; i < 1 << 20; i++) {
         values.add(String.valueOf(i));
      }

      final boolean[] found = new boolean[values.size()];
      iterateRandomly(values, new Callback<String>() {
         public void callback(String item) {
            found[Integer.parseInt(item)] = true;
         }
      }, 32);

      for (boolean flag : found) {
         if (!flag) {
            throw new IllegalStateException("missed value");
         }
      }

      System.out.println("OK");
   }

   public static <T> void iterateRandomly(List<T> list, Callback<T> callback, int chunkCount) {
      if (list.size() % chunkCount != 0) {
         throw new IllegalArgumentException("nasty precondition");
      }
     
      int chunkSize = list.size() / chunkCount;

      Random r = new Random();

      T[] tmp = (T[]) new Object[chunkSize];
      for (int k = 0; k < chunkCount; k++) {
         // grab selection with offset and interval
         for (int i = 0; i < tmp.length; i++) {
            tmp[i] = list.get(k + i * chunkCount);
         }

         // destructive shuffle
         for (int i = 0; i < tmp.length; i++) {
            int p = i + r.nextInt(tmp.length - i);

            // iterate
            callback.callback(tmp[p]);

            tmp[p] = tmp[i];
         }
      }
   }
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 823
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #12 - Posted 2012-06-14 08:27:57 »

To answer you question as posed...use a quasi-random number generator.  The simplest would be to rearrange the bits of the index in fixed pattern.  This is easiest when the size in insured to be power-of-two...otherwise it gets trickier.
I was thinking among similar lines: just XOR-ing your POT index. But there will be noticable patterns.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #13 - Posted 2012-06-14 08:40:33 »

Yes...if you need need more random than that..you have to shuffle bits around.

Along the same lines of your suggestion...assuming that the 'in-order' version has no meaning, you could do it two passes.  First walk the data in-order.  Second pass shuffles elements within a bucket size.  Every other set of passes, you offset the bucket boundaries by 1/2 the bucket size, so elements can eventually move anywhere in the array.

(EDIT: shuffling in buckets is to take advantage of caching BTW)

EDIT 2: For large arrays, buckets makes much more sense...collapse the two passes into one, working inside a bucket, and for slightly added randomness the starting point could be chosen by a pseudo-RNG.  But this is all speculation since we don't know the real problem statement.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 823
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #14 - Posted 2012-06-14 09:02:31 »

No more "nasty precondition":
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
public class Main {
   public interface Callback<T> {
      public void callback(T item);
   }

   public static void main(String[] args) {

      List<String> values = new ArrayList<String>();
      for (int i = 0; i < 1 << 20; i++) {
         values.add(String.valueOf(i));
      }

      final int[] histogram = new int[values.size()];

      // test performance for various bucket counts
      for (int bucketCount = 333; bucketCount >= 3; bucketCount--) {
         System.out.println("bucketCount=" + bucketCount);

         // iterate
         iterateRandomly(values, new Callback<String>() {
            public void callback(String item) {
               histogram[Integer.parseInt(item)]++;
            }
         }, bucketCount);

         // verify results
         for (int i = 0; i < histogram.length; i++) {
            if (histogram[i] != 1) {
               throw new IllegalStateException("incorrect number of matches (" + histogram[i] + ") for value " + i);
            }
         }
         Arrays.fill(histogram, 0);
      }

      System.out.println("OK");
   }

   public static <T> void iterateRandomly(List<T> list, Callback<T> callback, int bucketCount) {

      int bucketSize = list.size() / bucketCount;

      Random r = new Random();

      T[] bucket = (T[]) new Object[bucketSize];
      for (int k = 0; k < bucketCount; k++) {
         for (int i = 0, p = k; i < bucket.length; i++, p += bucketCount) {
            bucket[i] = list.get(p);
         }

         iterateRandomlyDestructively(bucket, bucket.length, callback, r);
      }

      if (list.size() % bucketCount != 0) {
         List<T> remainder = new ArrayList<T>();

         if (bucket.length == 0) {
            remainder.addAll(list);
         } else {
            for (int k = 0; k < bucketCount; k++) {
               for (int i = k + bucket.length * bucketCount; i < list.size(); i += bucketCount) {
                  remainder.add(list.get(i));
               }
            }
         }

         Collections.shuffle(remainder);
         for (T item : remainder) {
            callback.callback(item);
         }
      }
   }

   public static <T> void iterateRandomlyDestructively(T[] bucket, int len, Callback<T> callback, Random r) {
      for (int i = 0; i < len; i++) {
         int p = i + r.nextInt(len - i);
         callback.callback(bucket[p]);
         bucket[p] = bucket[i];
      }
   }
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline davedes
« Reply #15 - Posted 2012-06-14 11:11:19 »

@Riven: i would like to avoid shuffling... due to memory constraints (two arrays of 2^28 elements is quite alot ) but may have to just shuffle.
How often are you changing your arrays? What are you doing? Can you read/write to file and "chunk"/stream data so you aren't working with everything in memory?

Offline moogie

JGO Knight


Medals: 13
Projects: 6
Exp: 10 years


Java games rock!


« Reply #16 - Posted 2012-06-14 11:18:39 »

wow, thanks for all the interest. I will have to take time to digest it all Smiley

I shall elaborate why I need to perform random iteration

I have a fixed length input bit stream over which i run an algorithm to find the smallest unique symbol length S (in bits) that when the stream is split in to S bit symbols no symbol is repeated. This S value is used later on in other algorithms.

However these algorithms need S to be 64 bits or less. Normally the bit stream is a compressed data stream so S is < 64 bit but it can occur that uncompressed streams, or streams with uncompressed portions are input. In that case S is likely to be > 64. So to help reduce the impact of such streams I want to pre-process the input stream to reduce the apparent large string of repeated bits.

This pre-processing is envisioned to be a simple XOR for each S bit blocks of the input stream with a random iteration of an imaginary array of sequential long integers. Imaginary as the index into the array is the same as the value in the array. This process is then reversed at a later stage.

The sequential imaginary array is to be used so that the original input stream bit probabilities are not affected by the pre-processing.
Offline moogie

JGO Knight


Medals: 13
Projects: 6
Exp: 10 years


Java games rock!


« Reply #17 - Posted 2012-06-14 13:38:33 »

My hunch seems correct, if the interval is a prime number then a modified version of the algorithm I stated seems to work for all the testing I have performed. I will still look at the other alternatives suggested to see which gives the best speed / memory usage / randomness compromise.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
abstract class RandomIterator {

   public int getStartIndex() {
      return startIndex;
   }

   public int getInterval() {
      return interval;
   }

   public int getCurrIndex() {
      return currIndex;
   }

   private final int startIndex;
   private final int interval;
   private final List<?> collection;
   private final int collectionSize;
   private int currIndex;

   public RandomIterator(List<?> collection, int interval,Random random) {
      this.collection = collection;
      collectionSize = collection.size();
      this.interval=interval;
      startIndex = random.nextInt(collection.size());
      currIndex = startIndex;
   }

   public Object getNext() {
      Object o = collection.get(currIndex);

      currIndex = (interval - (collectionSize - currIndex)) % collectionSize;

      return o;
   }

}

class SemiRandomIteratorPrimeStep extends RandomIterator {


   public SemiRandomIteratorPrimeStep(List<?> collection, Random random) {
      super(collection,createInterval(collection.size(),random),random);

   }
   
   private static int createInterval(int collectionSize, Random random)
   {

      final int bitLength = 24;

      return BigInteger.probablePrime(bitLength, random).intValue();

   }
}

public class RandomIteratorTest {
   /**
    * @param args
    */

   public static void main(String[] args) {
      final int listSize = 86886;
      final int iterations = 100000;
      ArrayList<Object> list = new ArrayList<Object>(listSize);
      for (int i = 0; i < listSize; i++) {
         list.add(new Object());
      }

      HashSet<Object> seenSet = new HashSet<Object>(list.size());
     

      for (int j = 0; j < iterations; j++) {
         seenSet.clear();
         RandomIterator semiRandomIterator = new SemiRandomIteratorPrimeStep(
               list, new Random(j));

         for (int i = 0; i < list.size(); i++) {
            Object obj = semiRandomIterator.getNext();
            if (seenSet.contains(obj)) {
               System.out.println("Collision. Index: "
                     + semiRandomIterator.getCurrIndex() + " interval: "
                     + semiRandomIterator.getInterval()
                     + " startIndex: "
                     + semiRandomIterator.getStartIndex() + " seed: "
                     + j);
               System.exit(1);
            }
            seenSet.add(obj);
         }
      }
      System.out.println("no collisions.");
   }
}
Offline Roquen
« Reply #18 - Posted 2012-06-14 15:49:05 »

Well if randomness is really important, then you can use a linear congruent generator..the trick is that you have to compute the constants each time the length changes, which boils down to performing an extended GCD.  Generating the sequence of values would require a modulo...but walking random memory should hide the cost of the divide.
Offline sproingie

JGO Kernel


Medals: 202



« Reply #19 - Posted 2012-06-14 16:31:51 »

The period of an RNG (which includes a LCG) is the interval for which it doesn't repeat its entire sequence of pseudorandom numbers.  There's no way it keeps from repeating the same individual number in its codomain, because that would be the complete opposite of random.  It'd be like a coin toss that always alternated heads and tails.

Yeesh, just walk the list and swap randomly.  If you need to keep the original list, swap the indexes.  Or do what the database kids do and sort by random() (but that'll hurt doing it with 260+ million elements unless you go mapreduce)
Offline Jono
« Reply #20 - Posted 2012-06-14 18:18:25 »

Quote
My hunch seems correct, if the interval is a prime number then a modified version of the algorithm I stated seems to work for all the testing I have performed. I will still look at the other alternatives suggested to see which gives the best speed / memory usage / randomness compromise.
The interval and length of array have to be relatively prime.

So if the interval is prime, then it also has to not be a factor of the array length. An easy way would be to make the array length a power of two then use any prime number >= 3 as the interval.
Offline moogie

JGO Knight


Medals: 13
Projects: 6
Exp: 10 years


Java games rock!


« Reply #21 - Posted 2012-06-14 23:32:06 »




Don't worry, I will be performing some benchmarking to see whether the iterate and swap is acceptable Smiley and that applies to all suggestions Wink

Perhaps a little more clarification can help understand the problem... In my pervious post I defined S as symbol size in bits. Since the bit steam split into S sized chunks. The count of chunks is going to be less than 2^S. the preprocessing array (imaginary or not) will still need to be of 2^S length even if most elements are not used. So having that array is a bit wasteful and potentially slower due to random memory access than a mor computationally expensive algorithm that generates a non repeating random sequence of indecies into an imaginary array.
Offline Roquen
« Reply #22 - Posted 2012-06-15 08:44:09 »

@sproingie:  A full-period LCG with period P must visit each element of set S = [0,P) exactly once per period..otherwise it could not be full period.
Offline moogie

JGO Knight


Medals: 13
Projects: 6
Exp: 10 years


Java games rock!


« Reply #23 - Posted 2012-06-15 13:05:20 »

@Davedes: Thanks for the links. From reading those articles, I think my algorithm is a form of Linear Congruential Generator.



I have created a simple benchmark using two methods: Riven's Bucket method and my Prime Interval Stepping (PIS) Method. Source at http://www.java-gaming.org/?action=pastebin&id=120

From this simple benchmark, for an array size of 2^20, the PIS method seems to be about 5x faster than the Bucket method when utilising the random indecies sequence only as i will ultimately be doing for my situation.




@UprightPath: can you give a little more info about the constructor parameters of your implementation? I would love to add it to the benchmark but am unsure what values to put in for the "range" and "rangeStart" parameters.

Edit: forgot a class in the paste bin dump
Offline UprightPath
« Reply #24 - Posted 2012-06-15 13:13:20 »

Yes, comments would be helpful, wouldn't they?
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
public SemiRandomIteratorObject(List<?> collection, int range, int rangeStart, int step) {
      this.collection = collection;
      this.range = range;
      this.rangeStart = rangeStart;
      this.rangeEnd = this.rangeStart + range;
      this.startIndex = this.rangeStart + random.nextInt(range);
      this.currIndex = startIndex;
      this.currLoopIndex = this.currIndex;
      this.step = step;
      this.up = random.nextBoolean();
      this.move = random.nextBoolean();
   }

collection: The List in question, instead of writing it as a purely array based, I decided to use lists. Anyway, it'd be fairly easy to change it out.
rangeStart: The index at which you'd like to start the random iteration.
range: The number of elements, from rangeStart to rangeStart + range, you'd like to iterate through.
step: This is just some number that is a factor of range.

Offline Roquen
« Reply #25 - Posted 2012-06-15 14:50:59 »

Just for fun, for power-of-two only:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
/**
 * Computes permuted (random) indices on [0,2<sup>n</sup>) visiting each element exactly once.
 */

public class PermutedSequencePOT
{
  private static java.util.Random rng = new java.util.Random();
 
  private int m;
  private int a;
  private int mask;
  private int v;

  public PermutedSequencePOT(int length)
  {
    setLength(length);
  }

  /** Set the length of the sequence.  Must be a power-of-two.  */
  public void setLength(int length)
  {
    mask = length-1;
    reset();
  }

  /** Create a new permutation of the current length. */
  public void reset()
  {
    // this is all overkill
    m = (rng.nextInt()<<3)|5;   // anything such that (m & 7)==5
    a = (rng.nextInt()<<1)|1;   // any odd value
    v = (rng.nextInt());        // basically sets the offset that zero will appear
  }


  /** Returns the next index. */
  public int next()
  {
    v = (m*v + a) & mask;

    return v;
  }
}
Offline moogie

JGO Knight


Medals: 13
Projects: 6
Exp: 10 years


Java games rock!


« Reply #26 - Posted 2012-06-16 05:41:09 »

It seems we have a new winner with Roquen's POT Permutaed Sequence implementation in the speed category Smiley

On my rig with 100 iterations with a collection size of 2^20 the time taken (in milliseconds:)

Prime Step time taken = 1755
Bucket Riven time taken = 10351
Power of Two Perturbed Sequence by Roquen time taken = 393
Directional by UprightPath time taken = 974

even in the worst case scenario (collection size of 2^20 + 1 ) the POT method still wins:

Prime Step time taken = 1751
Bucket Riven time taken = 10196
Power of Two Perturbed Sequence by Roquen time taken = 1228
Directional by UprightPath time taken = 977

Directional implementation is now the speediest! in this worst case for POT.

Code for the testing can be found at: http://www.java-gaming.org/?action=pastebin&id=125


@UprightPath: thanks for the definitions Smiley Unfortunately I think I might have stuffed up integrating your code (i get infinite recursion) ... Can you have a look over my extensions to see what i did incorrectly? My main changes was always use the collection size /2 as the step. in cases where the collection size is not even, i assume that the collection size is +1 and perform a check to see whether the next "random" index is >= the collection size, if so then ignore it and get the next "random" index. The range is always the size of the Collection (or +1 if odd). The code is included in the above link.

Edit: Updated table to include Directional by UprightPath times
Offline moogie

JGO Knight


Medals: 13
Projects: 6
Exp: 10 years


Java games rock!


« Reply #27 - Posted 2012-06-16 13:24:06 »

I found a handly online randomness testing website: http://www.cacert.at/cgi-bin/rngresults

here are the results of the three methods:

1  
2  
3  
4  
5  
Generator         VendorSpeed PriceEntropy (->Birthday SpacinMatrix Rank6x8 Matrix RankMinimum Distance Test  Random Spheres TestThe Sqeeze TestOverlapping Sums Tes
Prime Step 23bit          B/s  USD    7.932087              0      0.686              0                      0           0.022763              0                   0
bucket shuffle 23bit      B/s  USD    7.999994       0.021025      0.992          0.407               0.787081           0.400642       0.098716            0.000724
ROT 23bit                 B/s  USD    7.936804              0      0.224          0.004                      0           0.472286              0                   0
java random 23bit         B/s  USD    7.999993       0.483173       0.63          0.012               0.674221            0.83216       0.881283             0.00028


The java random 23bit was used to get a reference... it is simply calling Random.nextInt(1<<23) 2^23 times.

These results are not readily understandable other than the order of increasing "randomness" is Prime Step, Power of Twp Permutation, Bucket Shuffle.

This is quite apparent when converting the output each implementation into a 4096x4096 image when given an array of a 24bit sequential integers.



I think Roquen's implementation suites my needs the best. Thanks Smiley

Edit: updated to include UprightPath's Directional Implementation
Offline UprightPath
« Reply #28 - Posted 2012-06-16 15:28:40 »

I looked at what you had and solved the issues that you were having (My original code was written with the intent to be able to pick a subset of a list to perform the function on, rather than always performing it on the whole collection, fixing that...)

Here you go: http://www.java-gaming.org/?action=pastebin&id=126

Hmm, never mind. I just messed around with it using the whole 4096x4096 and the method, as I defined it, doesn't really scramble the list very well.

Anyway, glad you found you answer.

Offline moogie

JGO Knight


Medals: 13
Projects: 6
Exp: 10 years


Java games rock!


« Reply #29 - Posted 2012-06-16 22:48:19 »

Thanks for that Smiley

I have updated the table of results above to include your implementation. The speed is very nice! However I think you are correct... it's apparent randomness is probably not it's strong suit Sad
Pages: [1] 2
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

TehJavaDev (32 views)
2014-10-27 03:28:38

TehJavaDev (26 views)
2014-10-27 03:27:51

DarkCart (41 views)
2014-10-26 19:37:11

Luminem (22 views)
2014-10-26 10:17:50

Luminem (27 views)
2014-10-26 10:14:04

theagentd (33 views)
2014-10-25 15:46:29

Longarmx (61 views)
2014-10-17 03:59:02

Norakomi (58 views)
2014-10-16 15:22:06

Norakomi (47 views)
2014-10-16 15:20:20

lcass (43 views)
2014-10-15 16:18:58
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!