Geek asks and answers

Lazy Mixing Algorithms

I have a large list of elements that I want to iterate over randomly. However, I cannot modify the list, and I also do not want to create a copy of it, because 1) it is large and 2) iteration can be expected to be canceled earlier.

List<T> data = ...;
Iterator<T> shuffled = shuffle(data);
while (shuffled.hasNext()) {
    T t = shuffled.next();
    if (System.console().readLine("Do you want %s?", t).startsWith("y")) {
        return t;
    }
}
System.out.println("That all");
return t;

I'm looking for an algorithm so that the code above runs in O(n)(and preferably only requires a space O(log n)), so caching elements that were created earlier is not an option. I don't care if the algorithm is biased (so far this is not obvious).

(I use pseudo-Java in my question, but you can use other languages ​​if you want)

Here is the best I have received so far.

Iterator<T> shuffle(final List<T> data) {
    int p = data.size();
    while ((data.size() % p) == 0) p = randomPrime();
    return new Iterator<T>() {
        final int prime = p;
        int n = 0, i = 0;
        public boolean hasNext() { return i < data.size(); }
        public T next() {
            i++; n += prime;
            return data.get(n);
        }
    }
}

O(n), , , data.size().

+5
3

, . List ArrayList, , (a LinkedList get , O (n), O (n ^ 2) ).

O (n) , , , Fisher-Yates/Knuth shuffle, O (n) . , , , .

:

, , , , O (n).

O (1) O (n).

, , .

. , 2 a () b a % b, 2a % b, 3a % b, 4a % b,..., 0, 1, 2,..., b-2, b-1, , . , ( , ).

, , , , , ( , , ), .

, , , .

. 1 len-1 nextInt, 1,2,3,... ...,3,2,1 , , , , , .

, (mod length), .

Java:

static Random gen = new Random();

static void printShuffle(int len)
{
  // get first prime >= len
  int newLen = len-1;
  boolean prime;
  do
  {
     newLen++;
     // prime check
     prime = true;
     for (int i = 2; prime && i < len; i++)
        prime &= (newLen % i != 0);
  }
  while (!prime);

  long val = gen.nextInt(len-3) + 2;
  long oldVal = val;
  do
  {
     if (val < len)
        System.out.println(val);
     val = (val + oldVal) % newLen;
  }
  while (oldVal != val);
}
+4

. . ( , ). . .

n + n , O (n). , . , .

: Python - , Python

, , . . .

+1

, , , .

, : i 'th shuffled item, swap a[i] with a[j], j [i..n-1], a[i]. .

, , reset , "", RNG.

reset , , . - .

RNG? . , . , "" , . , RC4 . . 4- , .

Java, Iterator, . . :

ShuffledList<Integer> lst = new SuffledList<>();

... build the list with the usual operations

ResetableInterator<Integer> i = lst.iterator();
while (i.hasNext()) {
  int val = i.next();

  ... use the randomly selected value

  if (anyConditinoAtAll) break;
}
i.reset();  // Unshuffle the array

I know this is not perfect, but it will be fast and give a good shuffle. Note: if you are not reset, the next iterator will still be a new random shuffle, but the original order will be lost forever. If the loop body can throw an exception, you need to reset in the block finally.

class ShuffledList<T> extends ArrayList<T> implements Iterable<T> {

    @Override
    public Iterator<T> iterator() {
        return null;
    }   

    public interface ResetableInterator<T> extends Iterator<T> {
        public void reset();
    }

    class ShufflingIterator<T> implements ResetableInterator<T> {

        int mark = 0;

        @Override
        public boolean hasNext() {
            return true;
        }

        @Override
        public T next() {
            return null;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not supported.");
        }

        @Override
        public void reset() {
            throw new UnsupportedOperationException("Not supported yet.");
        }
    }
}
+1
source

More articles:


All Articles