Lazy Shuffle-Algorithmen

Question

Ich habe eine große Liste von Elementen, die ich in zufälliger Reihenfolge durchlaufen möchte. Allerdings kann ich die Liste nicht ändern und ich möchte auch keine Kopie davon erstellen, weil 1) sie groß ist und 2) es erwartet werden kann, dass die Iteration früh abgebrochen wird.

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's all"); 
return t; 

Ich bin für einen Algorithmus der Suche waren der Code oben in O(n) laufen würde (und erfordern vorzugsweise nur O(log n) Raum), so die Elemente zwischenspeichern, die früher hergestellt wurden, ist keine Option. Es ist mir egal, ob der Algorithmus verzerrt ist (solange er nicht offensichtlich ist).

(I verwendet pseudo-Java in meiner Frage, aber Sie können andere Sprachen verwenden, wenn Sie möchten)

Hier ist das Beste, was ich so weit gekommen.

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); 
     } 
    } 
} 

Iterieren alle Elemente in O(n), konstanten Raum, aber offensichtlich voreingenommen, da es nur data.size() Permutationen erzeugen kann.

Answer 1

Die einfachsten Shuffling-Ansätze, die ich kenne, arbeiten mit Indizes. Wenn die List keine ArrayList ist, können Sie mit einem sehr ineffizienten Algorithmus enden, wenn Sie versuchen, eine der folgenden zu verwenden (eine LinkedList hat eine get von ID, aber es ist O (n), so dass Sie am Ende mit O (n^2) Zeit).

Wenn O (n) Raum in Ordnung ist, was ich nicht annehme, würde ich die Fisher-Yates/Knuth shuffle empfehlen, es ist O (n) Zeit und ist einfach zu implementieren. Sie können es optimieren, so dass Sie nur eine einzige Operation ausführen müssen, bevor Sie das erste Element abrufen können. Sie müssen jedoch den Rest der geänderten Liste auf dem aktuellen Stand halten.

Meine Lösung:

Ok, so ist dies überhaupt nicht sehr zufällig, aber ich kann keine bessere Art und Weise sehen, wenn Sie weniger wollen als O (n) Platz.

Es dauert O (1) Raum und O (n) Zeit.

Es kann einen Weg geben, den Speicherplatz ein wenig nach oben zu schieben und mehr zufällige Ergebnisse zu bekommen, aber ich habe das noch nicht herausgefunden.

Es hat mit relative primes zu tun. Die Idee ist, dass, gegeben 2 relative Primzahlen a (der Generator) und b, wenn Sie durch a % b, 2a % b, 3a % b, 4a % b durchlaufen, ..., sehen Sie jede ganze Zahl 0, 1, 2, ..., b-2, b-1, und dies wird auch vor dem zweimaligen Auftreten einer ganzen Zahl passieren. Leider habe ich keinen Link zu einem Beweis (der Wikipedia-Link erwähnt oder deutet darauf hin, ich habe nicht zu sehr ins Detail geschaut).

Ich beginne mit der Erhöhung der Länge, bis wir eine Primzahl erhalten, da dies bedeutet, dass jede andere Zahl eine relative Primzahl ist, die eine ganze Menge weniger einschränkend ist (und einfach eine Zahl überspringen, die größer ist als die ursprüngliche Länge). Erzeugen Sie dann eine Zufallszahl und verwenden Sie diese als Generator.

Ich durchläuft und drucke alle Werte aus, aber es sollte einfach genug sein, um zu modifizieren, um die nächste zu erzeugen, die der aktuellen entspricht.

Hinweis Ich überspringe 1 und len-1 mit meinem nextInt, da diese 1,2,3,... und ...,3,2,1 jeweils produzieren, aber Sie können dazu gehören, aber wahrscheinlich nicht, wenn die Länge unter einem bestimmten Schwellenwert liegt.

Sie können auch eine Zufallszahl erzeugen, um den Generator zu multiplizieren (Länge ändern), um von zu beginnen.

Java-Code:

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); 
} 

Answer 2

Sie können versuchen, einen Puffer dafür zu verwenden. Iterate durch eine begrenzte Menge von Daten und lege sie in einen Puffer. Extrahiere zufällige Werte aus diesem Puffer und sende sie an die Ausgabe (oder wo auch immer du sie brauchst). Iteriere durch den nächsten Satz und überschreibe diesen Puffer. Wiederholen Sie diesen Schritt.

Sie werden mit n + n Operationen enden, die immer noch O (n) ist. Leider wird das Ergebnis nicht zufällig sein. Es wird nahezu zufällig sein, wenn Sie Ihre Puffergröße richtig wählen.

Auf einer anderen Note, überprüfen Sie diese zwei: Python - run through a loop in non linear fashion, random iteration in Python

Vielleicht ein eleganter Algorithmus gibt es diese besser zu machen. Ich bin mir nicht sicher. Ich freue mich auf andere Antworten in diesem Thread.

Answer 3

Dies ist keine perfekte Antwort auf Ihre Frage, aber vielleicht ist es nützlich.

Die Idee ist, einen reversible Zufallszahlengenerator und den üblichen Array-basierten Umordnungsalgorithmus lazily getan zu verwenden: die i ‚th gemischt Einzelteil zu erhalten, tauscht a[i] mit und eine zufällig ausgewählte a[j] wo j in [i..n-1] ist, dann Rückkehr a[i]. Dies kann im Iterator erfolgen.

Nachdem Sie mit dem Iterieren fertig sind, setzen Sie das Array in die ursprüngliche Reihenfolge zurück, indem Sie die umgekehrte Richtung des Zufallsgenerators verwenden.

Der nicht shuffling Reset dauert nie länger als die ursprüngliche Iteration, so dass die asymptotischen Kosten nicht geändert werden. Die Iteration ist immer noch linear in der Anzahl der Iterationen.

Wie baue ich einen reversiblen RNG? Verwenden Sie einfach einen Verschlüsselungsalgorithmus. Verschlüsseln Sie den zuvor generierten Pseudozufallswert, um vorwärts zu gehen, und entschlüsseln Sie, um rückwärts zu gehen. Wenn Sie über einen symmetrischen Verschlüsselungsalgorithmus verfügen, können Sie bei jedem Schritt einen "Salz" -Wert hinzufügen, um einen Zweierzyklus zu vermeiden und ihn für jeden Schritt nach hinten zu subtrahieren. Ich erwähne das, weil RC4 einfach und schnell und symmetrisch ist. Ich habe es schon früher für solche Aufgaben benutzt. Das Verschlüsseln von 4-Byte-Werten und das Berechnen von Mod, um sie in den gewünschten Bereich zu bringen, werden in der Tat schnell sein.

Sie können dies in das Java-Iteratormuster drücken, indem Sie Iterator erweitern, um das Zurücksetzen zuzulassen. Siehe unten. Die Verwendung wird wie folgt aussehen:

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 

Ich weiß, das ist nicht perfekt, aber es wird schnell sein und einen guten Shuffle geben. Beachten Sie, dass der nächste Iterator immer noch ein neuer zufälliger Shuffle ist, wenn Sie nicht reset tun, aber die ursprüngliche Reihenfolge wird für immer verloren gehen. Wenn der Schleifenkörper eine Ausnahme generieren kann, möchten Sie das Zurücksetzen in einem finally Block.

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."); 
     } 
    } 
}